Truncated match.
PICList
Thread
'Challenge'
1996\04\07@194145
by
Andrew Warren

Dudes:
As many of you know, I periodically post programming "challenges"
here... Usually, they're of the "Tell me how this code fragment
works" form.
This time, it's a little different...
The following PIC 16C5x code tests for divisibility by 3, using an
algorithm credited to Lewis Carroll, the dopesmoking mathematician
and author of "Alice in Wonderland". Carroll's algorithm, of course,
was designed for base 10, so it tested for divisibility by 11.
;
; Test for divisibility by 3.
; Enter with the number to be tested in "TEST".
; Exits with W = 0 if the number's not divisible by 3,
; W = 1 if the number IS divisible by 3.
;
DIVBY3: RRF TEST
BNC NODEC
SKPNZ
RETLW 0
DECF TEST
NODEC: SKPZ
GOTO DIVBY3
RETLW 1
This code takes between 7 and 60some cycles, depending upon the
actual value in TEST. Average speed over the whole [0255] range of
inputs is about 48.5 cycles. The following version sacrifices a
couple of bytes of code space for marginally faster execution (45.8
cycles average):
;
; Test for divisibility by 3. Version 2.
; Enter with the number to be tested in "TEST".
; Exits with W = 0 if the number's not divisible by 3,
; W = 1 if the number IS divisible by 3.
;
DIVBY3: RRF TEST
BNC NODEC
SKPNZ
RETLW 0
DECFSZ TEST
GOTO DIVBY3
RETLW 1
NODEC: SKPZ
GOTO DIVBY3
RETLW 1
The challenge is to write a routine that's faster and/or smaller.
I'm not too interested in code that uses 256byte (or even 32byte)
lookup tables; in fact, I considered posting a 16bit version of the
above code to discourage the use of lookup tables in responses to
this challenge. However, I decided not to confuse the algorithm that
way, and instead am just making "no lookup tables" the only
restriction.
Actually, if you come up with a method that uses a short lookup table
in an INNOVATIVE way, that's ok... I just don't want to see a table
of "100100100100100" patterns or "3,6,9,12...". I guess what I'm
saying here is that if you DO use a lookup table, it should be
possible to scale your solution to 16 bits without running out of
codespace in the PIC16C5x.
Normally, the prize for the best response is a beer (or whatever) at
the Embedded Systems Conference, Comdex, CES, or whatever. This is a
slow time of year for West Coast trade shows, though, so your only
reward for THIS challenge will be the admiration of your peers here
on the list.
Andy
Andrew Warren  spam_OUTfastfwdTakeThisOuTix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499
1996\04\07@213835
by
Greg Young

{Quote hidden}>Dudes:
>
>The following PIC 16C5x code tests for divisibility by 3, using an
>algorithm credited to Lewis Carroll, the dopesmoking mathematician
>and author of "Alice in Wonderland". Carroll's algorithm, of course,
>was designed for base 10, so it tested for divisibility by 11.
>
>;
>; Test for divisibility by 3.
>; Enter with the number to be tested in "TEST".
>; Exits with W = 0 if the number's not divisible by 3,
>; W = 1 if the number IS divisible by 3.
>;
>
>DIVBY3: RRF TEST
> BNC NODEC
>
> SKPNZ
> RETLW 0
>
> DECF TEST
>
>NODEC: SKPZ
> GOTO DIVBY3
> RETLW 1
>
...
>Andy
>
>Andrew Warren  .....fastfwdKILLspam@spam@ix.netcom.com
>Fast Forward Engineering, Vista, California
>http://www.geocities.com/SiliconValley/2499
>
I'm not even sure the posted version will work. It begins by performing a
rotation, the results of which is checks for zero/nonzero. Yet, the
initialize state of the carry (which is shifted in bit 7 of TEST) is
unknown. If initially set, it would blow the algorithm (I think)...
For more compact code, why not just add 3 until it overflows or zeroes.
Something like (assuming a 14bit core):
Div3 MOVF TEST,W ; W = Value to Test (Set Z)
:next BTFSC Z ; If Z Set, Divisible by Zero
RETLW 1
ADDLW 3 ; Check Next Iteration
BTFSC C ; Done if Overflow
goto :next ; Continue til Done
RETLW 0 ; Done
I obviously haven't checked this and may have blown a line (or flag) here or
there, but the basic idea should be sound.
Caio.
1996\04\07@215754
by
Andrew Warren

Greg Young <PICLISTKILLspamMITVMA.MIT.EDU> wrote:
> I'm not even sure the posted version will work. It begins by
> performing a rotation, the results of which is checks for
> zero/nonzero. Yet, the initialize state of the carry (which is
> shifted in bit 7 of TEST) is unknown. If initially set, it would
> blow the algorithm (I think)...
Greg:
Yeah, you're right... Thanks for catching that.
There should be a "CLRC" before the "RRF". That'll teach me to
write code online instead of pasting from my text editor, I
guess.
{Quote hidden}> For more compact code, why not just add 3 until it overflows or
> zeroes. Something like (assuming a 14bit core):
>
> Div3 MOVF TEST,W ; W = Value to Test (Set Z)
> :next BTFSC Z ; If Z Set, Divisible by Zero
> RETLW 1
> ADDLW 3 ; Check Next Iteration
> BTFSC C ; Done if Overflow
> goto :next ; Continue til Done
> RETLW 0 ; Done
>
As you obviously realize, your code won't work on a 12bit PIC.
Also, it's a lot slower than the "challenge" code, and it slows
WAY down when it's scaled up to 16 bits.
I guess I worded the challenge unclearly... I should have said:
The challenge is to write a faster routine, or one which
executes at essentially the same speed but is shorter.
Thanks again for pointing out my error...
Andy
Andrew Warren  .....fastfwdKILLspam.....ix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499
1996\04\08@110234
by
Bob Fehrenbach
Andy,
I haven't tested this but adding one line and changing one branch
destination would cause the carry to be cleared only if it were set.
This might provide a small speed advantage.
DIVBY3: BCF STATUS, C ;Omitted in first posting.
NO_C: RRF TEST ;New label
BNC NODEC
SKPNZ
RETLW 0
DECF TEST
BCF STATUS, C ;Added line
NODEC: SKPZ
GOTO NO_C ;Changed destination
RETLW 1
I am curious as to why anyone would want to know if a number were
divisible by three, or is this an academic exercise?

Bob Fehrenbach Wauwatosa, WI EraseMEbfehrenbspam_OUTTakeThisOuTexecpc.com
1996\04\08@154036
by
Bill Cornutt

>
>I am curious as to why anyone would want to know if a number were
>divisible by three, or is this an academic exercise?
>
It is the classic solution to the "one potato, two potato" problem.
Bill C
"If you think there's a solution,
then you're part of the problem."
George Carlin
1996\04\08@174243
by
erik

Hi,
I'm new to the list, and dont have a definitive answer to the challenge,
but I do (maybe) have an idea that someone with more patience (and coding
skill!) can use to solve the problem:
In the Decimal system, there is a very easy technique for testing ANY number
for divisibility by 9. Its called "casting out nines" and can be best
illustrated with an example;
Take the number you want to test, lets say 12345, and add its digits
together;
1+2+3+4+5=15
then add the digits of the answer
1+5=6
Now because the answer is not 9 then the number 12345 is not divisible
by 9 (but, say, 123453 would be)
The basic proceedure of adding the digits is followed for ANY
length of test candidate, but you can take a short cut: any time you get
a 9 in the intermediate results you can discard it. Hence the name
"casting out nines". You continue adding until only one digit remains.
Now my idea: This method will work with any test number THAT IS ONE LESS
THAN THE RADIX. So to test for divisibility by 3, we could "cast out 3's"
if we were working to base 4. (or cast out 7's in octal or cast out
F's in hex)
That leaves the problem of converting the
number to be tested to base 4. A look at the binary equivalent of hex numbers
shows that a "tetrical" (or whatever you'd call base 4!) interpretation of
a number wouldn't be too hard to derive.
Sorry no code, like I said, I'm new...

Erik Grannells
1996\04\08@175945
by
Andrew Warren

Bob Fehrenbach <PICLISTspam_OUTMITVMA.MIT.EDU> wrote:
> I haven't tested this but adding one line and changing one branch
> destination would cause the carry to be cleared only if it were set.
> This might provide a small speed advantage.
>
>
> DIVBY3: BCF STATUS, C ;Omitted in first posting.
> NO_C: RRF TEST ;New label
> BNC NODEC
>
> SKPNZ
> RETLW 0
>
> DECF TEST
> BCF STATUS, C ;Added line
> NODEC: SKPZ
> GOTO NO_C ;Changed destination
> RETLW 1
Bob:
Yes, this cuts about 2.5 cycles (on average) from the execution
time.
Good call.
> I am curious as to why anyone would want to know if a number were
> divisible by three, or is this an academic exercise?
Bill Cornutt's answer ("It is the classic solution to the 'one
potato, two potato' problem") would, of course, be the USUAL
reason, but my need for the routine is a little different:
The "divisible by 3" routine is only the first step of a much
larger process: I'm trying to see if the input number is EQUAL
to 3.
Here's how it works:
First, I check for divisibility by 3. If the number passes that
test, I then make sure that it's not also divisible by 2. After
that, I use Eric Smith's routine for checking whether a number's
within a certain range... I start with a range of [0255], then
progressively narrow the range, one step at a time, to [24].
At this point, if the input number's passed all those tests, I'm
pretty sure that it may be equal to 3. To make ABSOLUTELY sure,
though, I check bits 27 of the number individually, verifying
that each is clear, then I check bits 0 and 1 and verify
that they're both set.
Since this is a very critical aplication, though, even THIS
isn't enough. To get that last little bit of certainty, I
divide 4,294,967,296 by the input number. If the answer's
1,431,655,765, (with no remainder), I asume that the input
number was indeed equal to 3.
Finally, I doublecheck my assumption using the following code:
XORLW 3
BZ ITS_EQUAL_TO_3
Andy
Andrew Warren  @spam@fastfwdKILLspamix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499
1996\04\08@183339
by
Andrew Warren

erik <KILLspamerikKILLspamdigits.demon.co.uk> wrote:
> In the Decimal system, there is a very easy technique for testing
> ANY number for divisibility by 9. Its called "casting out nines"
> ....
> This method will work with any test number THAT IS ONE LESS THAN
> THE RADIX. So to test for divisibility by 3, we could "cast out
> 3's" if we were working to base 4. (or cast out 7's in octal or
> cast out F's in hex)
Erik:
Good thinking. Lewis Carroll's technique, illustrated by my code)
works on any divisor that is one GREATER than the radix, so it could
also be used to test for divisibility by 5 in a basefour system.
Actually, my favorite quickanddirty test for divisibility by 11 (in
base 10) is different from Carroll's and similar to the "casting out
nines" algorithm:
As long as the test number contains more than one digit, do the
following:
Sum every other digit of the test number. Call this A.
Sum the remaining digits. Call this B.
Subtract the smaller of these sums from the larger, and
assign the result to the test number.
When the test number finally collapses to a single digit, the
original number is divisible by 11 only if the single remaining
digit is 0.
For example:
TEST = 40320760241556466902873580897805.
A = 4+3+0+6+2+1+5+4+6+0+8+3+8+8+8+5 = 71.
B = 0+2+7+0+4+5+6+6+9+2+7+5+0+7+0 = 60.
TEST = A  B = 11.
A = 1.
B = 1.
TEST = A  B = 0.
Viola! 40,320,760,241,556,466,902,873,580,897,805 IS divisible
by 11. How 'bout that.
Actually, this was the first approach I used to test for
divisibility by 3. Unfortunately, the PIC's instruction set was
just slightly limiting enough that I couldn't make it run as
quickly as the Carroll algorithm.
Andy
P.S. The real reason for my needing this routine (my previous
message to the contrary) was as part of a testforprime
function.
Andrew Warren  RemoveMEfastfwdTakeThisOuTix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499
1996\04\08@200036
by
Scott Dattalo

erik wrote:
>
> Hi,
>
> I'm new to the list, and dont have a definitive answer to the challenge,
> but I do (maybe) have an idea that someone with more patience (and coding
> skill!) can use to solve the problem:
Anyone willing to write code in assembly has been blessed with patience.
{Quote hidden}> In the Decimal system, there is a very easy technique for testing ANY number
> for divisibility by 9. Its called "casting out nines" and can be best
> illustrated with an example;
>
> Take the number you want to test, lets say 12345, and add its digits
> together;
> 1+2+3+4+5=15
> then add the digits of the answer
> 1+5=6
> Now because the answer is not 9 then the number 12345 is not divisible
> by 9 (but, say, 123453 would be)
>
> The basic proceedure of adding the digits is followed for ANY
> length of test candidate, but you can take a short cut: any time you get
> a 9 in the intermediate results you can discard it. Hence the name
> "casting out nines". You continue adding until only one digit remains.
>
> Now my idea: This method will work with any test number THAT IS ONE LESS
> THAN THE RADIX. So to test for divisibility by 3, we could "cast out 3's"
> if we were working to base 4. (or cast out 7's in octal or cast out
> F's in hex)
>
> That leaves the problem of converting the
> number to be tested to base 4. A look at the binary equivalent of hex numbers
> shows that a "tetrical" (or whatever you'd call base 4!) interpretation of
> a number wouldn't be too hard to derive.
>
> Sorry no code, like I said, I'm new...
>
> 
Damn, you beat me to it Erik! But I have some code...
This is exactly the idea I had too. I'll give a couple of examples pertinent
to the specific problem. First note that the "digits" in our divideby3 case
are really pairs of binary bits. If we had the number 33 in base ten then the
hex and binary numbers are:
33 = 0x11 = 00100001b
Rewrite the binary number to show how the bits are paired to form digits:
00 10 00 01
Sum up the 4 "digits": 00 + 10 + 00 + 01 = 11b
which of course is divisible by three.
Here are a couple more examples
006 = 0x06 = 00 00 01 10 ==> 11b yes
012 = 0x0c = 00 00 11 00 ==> 11b yes
099 = 0x63 = 01 10 00 11 ==> 01 10 ==> 11b yes
254 = 0xfe = 11 11 11 10 ==> 10 11 ==> 01 00 ==> 01b no
255 = 0xff = 11 11 11 11 ==> 11 00 ==> 11b yes
Note that the last few examples had to go through more than one iteration.
Here's the code that will do it.
DIVBY3: CLRF t1 ;Temporary variable to keep track of
;the sum of digits
a1 MOVF test,W ;Get the test pattern
SKPNZ ;If it is zero, then all bits have
goto a2 ; been shifted out
ANDLW 3 ;Get the two lsb's
ADDWF t1,F ;Sum of digits (note C=0 after this inst)
RRF test,F ;Get rid of the two lsb's: first one
CLRC ;CYA
RRF test,F ; second one
goto a1 ;See if there are any more bits
a2 MOVF t1,W ;Get the sum of digits
MOVWF test ;Save in case we have to loop some more
ANDLW 0xfc ;Is the sum >= 4?
SKPZ
goto DIVBY3 ;Yes, loop some more
RRF test,W ;Move b1 to b0
XORWF test,F ;b0 = b0 ^ b1
BTFSC test,0 ;If b0 is set then sum of digits is 01b or 10b
RETLW 0 ; Not divisble by three
RETLW 1 ;Sum of digits is either 00b or 11b
;note that 00b is possible only if test
;equal zero upon entry.
Best case execution is 15 cycles, worst case is 71. I don't know the average.
It doesn't beat Andy's original posting in either performance or code length,
but it is a slightly different implementation.
Guess we'll have to split a lite Beer, Erik.
Scott
1996\04\08@211255
by
Andrew Warren

Scott Dattalo <spamBeGonePICLISTspamBeGoneMITVMA.MIT.EDU> wrote:
{Quote hidden}> Here's the code that will do it.
>
> DIVBY3: CLRF t1 ;Temporary variable to keep track of
> ;the sum of digits
> a1 MOVF test,W ;Get the test pattern
> SKPNZ ;If it is zero, then all bits have
> goto a2 ; been shifted out
>
> ANDLW 3 ;Get the two lsb's
> ADDWF t1,F ;Sum of digits (note C=0 after this
> ;inst)
> RRF test,F ;Get rid of the two lsb's: first one
> CLRC ;CYA
> RRF test,F ; second one
> goto a1 ;See if there are any more bits
>
> a2 MOVF t1,W ;Get the sum of digits
> MOVWF test ;Save in case we have to loop some more
> ANDLW 0xfc ;Is the sum >= 4? SKPZ
> goto DIVBY3 ;Yes, loop some more
>
> RRF test,W ;Move b1 to b0
> XORWF test,F ;b0 = b0 ^ b1
> BTFSC test,0 ;If b0 is set then sum of digits is 01b
> ;or 10b
> RETLW 0 ;Not divisble by three
> RETLW 1 ;Sum of digits is either 00b or 11b
> ;note that 00b is possible only if test
> ;equal zero upon entry.
>
> Best case execution is 15 cycles, worst case is 71. I don't know the
> average. It doesn't beat Andy's original posting in either
> performance or code length, but it is a slightly different
> implementation.
>
> Guess we'll have to split a lite Beer, Erik.
Scott:
Yeah, I guess so, unless someone comes up with an even better way.
Here's a faster implementation of the "Erik & Scott" algorithm:
DIVBY3: MOVF TEST,W
ANDLW 00110011B
MOVWF T1
RRF TEST
RRF TEST,W
ANDLW 00110011B
ADDWF T1
SWAPF T1,W
ADDWF T1,W
ANDLW 00001111B
SKPNZ
RETLW 1
XORLW 3
SKPNZ
RETLW 1
XORLW 6^3
SKPNZ
RETLW 1
XORLW 9^6
SKPNZ
RETLW 1
XORLW 12^9
SKPNZ
RETLW 1
RETLW 0
This code executes in 1326 cycles, significantly faster than the
code I originally posted. I haven't profiled it to see what the
average execution time is, or whether that average can be lowered by
rearranging the order of the final XORLWs (it probably can).
If the above code is rewritten using a table, it takes even less
code space AND it executes faster... Only 14 cycles per input:
DIVBY3: MOVF TEST,W
ANDLW 00110011B
MOVWF T1
RRF TEST
RRF TEST,W
ANDLW 00110011B
ADDWF T1
SWAPF T1,W
ADDWF T1,W
ANDLW 00001111B
ADDWF PC
RETLW 1
RETLW 0
RETLW 0
RETLW 1
RETLW 0
RETLW 0
RETLW 1
RETLW 0
RETLW 0
RETLW 1
RETLW 0
RETLW 0
RETLW 1
Can anyone do better than THIS?
Andy
P.S. The above code was written online... I haven't tested it yet,
so if you find any errors, please let me know.
Andrew Warren  TakeThisOuTfastfwdEraseMEspam_OUTix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499
1996\04\08@214903
by
John Payson

> Damn, you beat me to it Erik! But I have some code...
>
> This is exactly the idea I had too. I'll give a couple of examples pertinent
> to the specific problem. First note that the "digits" in our divideby3 case
> are really pairs of binary bits. If we had the number 33 in base ten then the
> hex and binary numbers are:
> 33 = 0x11 = 00100001b
>
> Rewrite the binary number to show how the bits are paired to form digits:
> 00 10 00 01
>
> Sum up the 4 "digits": 00 + 10 + 00 + 01 = 11b
> which of course is divisible by three.
Actually, I think it's easier to observe that 16%3=1 and do something like
either this:
swapf Number,w
addwf Number,f ; Note [MSN of Number] % 3 == old Number % 3
rrf Number,w ; We want to add what are now upper and lower
rlf Number,f ; two bits of MSN; 00 or 11 would be good.
bsf Number,4 ; By setting prev two bit of both addends,
iorlw $10 ; we turn 00 and 11 into 01 and 00.
addwf Number,f ; Now we're interested in Number:6
btfss Number,6 ; If set, not multiple of three
retlw 0 ; Return "nope"
retlw 1 ; Return "yep"
11 cycles constant execution time in 10 words, including the retlw. Let's
see a demo... [column headings are starting values in num]
Inst 00 01 02 03 90 A8 F5 FF
swap 00 10 20 30 09 8A 5F FF
add. 00 11 22 33 99 32 54 FE
rrf 00 08 11 29 4C 99 AA FF
rlf 00 23 44 67 33 64 A8 FD
bsf 10 33 54 77 33 74 B8 FD
bsf 10 18 11 39 5C 99 BA FF
add 20 4B 65 B0 8F 1D 72 FC
Res. yup nope nope yup yup yup nope yup
Slightly faster but bigger:
swapf Number,w
addwf Number,f
swapf Number,w
andlw $0F
addwf PC
db 1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1 ; retlw's
8 cycles, 21 words.
1996\04\09@000611
by
John Payson
> Bill Cornutt's answer ("It is the classic solution to the 'one
> potato, two potato' problem") would, of course, be the USUAL
> reason, but my need for the routine is a little different:
>
> The "divisible by 3" routine is only the first step of a much
> larger process: I'm trying to see if the input number is EQUAL
> to 3.
Hmm... this sounds similar in concept to the Leeland (sp?) sort:
[1] Check to see if first item is less than second, second less than third,
etc.
[2] If all checks pass, sort is complete. Otherwise...
[3] Randomly shuffle the numbers and go back to step [1].
1996\04\09@010609
by
Todd Peterson

Oh my...
{Quote hidden}> I'm trying to see if the input number is EQUAL
> to 3.
>
> Here's how it works:
>
> First, I check for divisibility by 3. If the number passes that
> test, I then make sure that it's not also divisible by 2. After
> that, I use Eric Smith's routine for checking whether a number's
> within a certain range... I start with a range of [0255], then
> progressively narrow the range, one step at a time, to [24].
>
> At this point, if the input number's passed all those tests, I'm
> pretty sure that it may be equal to 3. To make ABSOLUTELY sure,
> though, I check bits 27 of the number individually, verifying
> that each is clear, then I check bits 0 and 1 and verify
> that they're both set.
>
> Since this is a very critical aplication, though, even THIS
> isn't enough. To get that last little bit of certainty, I
> divide 4,294,967,296 by the input number. If the answer's
> 1,431,655,765, (with no remainder), I asume that the input
> number was indeed equal to 3.
>
> Finally, I doublecheck my assumption using the following code:
>
> XORLW 3
> BZ ITS_EQUAL_TO_3
>
> Andy
Andy:
You forgot to subtract three from the original input value and then check
the zero flag.
Only then can you ABSOLUTELY sure.
Todd Peterson
===========================================================
*** Developers of the PICPlus(TM) Microcontroller Board ***
Todd Peterson, Computer Engineer (RemoveMEtpetersonTakeThisOuTnetins.net)
ELAB Digital Engineering, Inc.
P.O. Box 246
Lawton, IA 510300246
(712) 9445344
Visit us at: http://www.netins.net/showcase/elab/
EMail Now for Your Free PICPlus(TM) Information Packet!
TO: tpetersonEraseME.....netins.net (include POSTAL mailing address)
===========================================================
1996\04\09@012545
by
Andrew Warren

John Payson <EraseMEPICLISTMITVMA.MIT.EDU> wrote:
{Quote hidden}> Actually, I think it's easier to observe that 16%3=1 and do
> something like either this:
>
> swapf Number,w
> addwf Number,f ; Note [MSN of Number] % 3 == old
> ; Number % 3
> rrf Number,w ; We want to add what are
> ; now upper and lower
> rlf Number,f ; two bits of MSN; 00 or 11 would
> ; be good.
> bsf Number,4 ; By setting prev two bit of both
> ; addends, we turn 00 and 11 into
> iorlw $10 ; 01 and 00.
> addwf Number,f ; Now we're interested in Number:6
> btfss Number,6 ; If set, not multiple of three
> retlw 0 ; Return "nope"
> retlw 1 ; Return "yep"
>
> 11 cycles constant execution time in 10 words, including the retlw.
>
> Slightly faster but bigger:
> swapf Number,w
> addwf Number,f
> swapf Number,w
> andlw $0F
> addwf PC
> db 1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1 ; retlw's
>
> 8 cycles, 21 words.
John:
I'm impressed... And tempted to call this the winning entry.
Anyone else have better code?
Andy
P.S. By the way, MPASM's "DT" directive will create that table of
RETLWs automatically.
Andrew Warren  RemoveMEfastfwdEraseMEEraseMEix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499
1996\04\09@013832
by
Andrew Warren
John Payson <RemoveMEPICLISTspam_OUTKILLspamMITVMA.MIT.EDU> wrote:
> Hmm... this sounds similar in concept to the Leeland (sp?) sort:
>
> [1] Check to see if first item is less than second, second less than
> third, etc.
>
> [2] If all checks pass, sort is complete. Otherwise...
>
> [3] Randomly shuffle the numbers and go back to step [1].
John:
I think it's closer to "Burns' HogWeighing Method":
[1] Carefully balance a wooden plank on a fulcrum.
[2] Place the hog to be weighed at one end of the plank.
[3] Pile rocks on the other end until they exactly balance the hog.
[4] Weigh the rocks.
Andy
Andrew Warren  RemoveMEfastfwdTakeThisOuTspamix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499
1996\04\09@102017
by
Bill Cornutt


{Quote hidden}>Dudes:
>
>As many of you know, I periodically post programming "challenges"
>here... Usually, they're of the "Tell me how this code fragment
>works" form.
>
>This time, it's a little different...
>The following PIC 16C5x code tests for divisibility by 3, using an
>algorithm credited to Lewis Carroll, the dopesmoking mathematician
>and author of "Alice in Wonderland". Carroll's algorithm, of course,
>was designed for base 10, so it tested for divisibility by 11.
>
>;
>; Test for divisibility by 3.
>; Enter with the number to be tested in "TEST".
>; Exits with W = 0 if the number's not divisible by 3,
>; W = 1 if the number IS divisible by 3.
>;
The following is what I call the "one potato, two potato" method.
; *********************************************
list p=16c54
TEST equ 9
STATUS equ 3
CBIT equ 0
ZBIT equ 2
WREG equ 0
TRUE equ 1
FALSE equ 0
start call divby3
nop
nop
; start of routine
divby3 movf TEST,WREG ;into w reg
btfsc STATUS,ZBIT ;test for inital zero
retlw FALSE ;yes, can't devide zero
; main loop aa10 is if no need to clear carry
loop bcf STATUS,CBIT ;clear carry
aa10 movf TEST,WREG ;see if done
btfsc STATUS,ZBIT ;is w zerO
retlw TRUE ;yes, so good and done
rrf TEST ;look for next bit
btfss STATUS,CBIT ;not the bit?
goto aa10 ;yes, didn't find first bit
; got a bit, look for another good bit
aa20 bcf STATUS,CBIT ;clear carry
aa22 rrf TEST ;look for good bit
btfsc STATUS,CBIT ;found bit?
goto loop ;yes
; no good bit, look for bad bit
aa30 movf TEST,WREG ;see if done
btfsc STATUS,ZBIT ;is w zerO
retlw FALSE ;yes, so bad and done
rrf TEST ;look for bad bit
btfss STATUS,CBIT ;not a bad bit?
goto aa20 ;yes, so go back for good bit
; got a bad bit, now next bit is bad, then good
bcf STATUS,CBIT ;clear carry
goto aa30 ;look for offsetting bad bit
end
; *****************************************************************

Bill Cornutt
EraseMEbillcornspamspamBeGoneinfoserv.com
Located in Ione California USA.
A small town in Northern California.
Sitting against the foothills of the Mother Lode.

1996\04\09@185507
by
erik
Errrrh,
I had a look in an old maths book I have, and theres an easier way than
all that "casting out nines" and base 4 stuff I told you about earlier:
Apparently if you add the digits of the number to be tested, sucessively
until theres only 1 digit left, then if, and only if, the result is 3 or
6 or 9 then the original number was divisible by 3.
e.g. Is 12345 divisible by 3?
1+2+3+4+5 = 15
1+5 = 6
so yes 12345 is divisible by 3.
Now, about that code...

erik
1996\04\10@132334
by
R.Radhakrishnan
After following this thread with interest for a while, may I point out the
following tests:
Divisible (evenly) by: Test
2 Last digit even
3 sum of all digits (recursively) divisibl
e by 3
4 Last 2 digits divisible by 4
5 Last digit 0 or 5
6 test 2 & 3
7 see below...
8 Last 3 digits divisible by 8
9 sum of all digits (recursively) divisibl
e by 9
10 that's an easy one!
11 this one is interesting 
sum up alternate digits starting with first  call this a
sum up alternate digits starting with the second  call this b
if (ab) = 0 or 11, the number is evenly divisible by 11!
I never found a way to test for divisibility by 7, though i spent many misspent
hours in my youth trying!
1996\04\10@133008
by
R.Radhakrishnan
After following this thread with interest for a while, may I point out the
following tests:
Divisible (evenly) by: Test
2 Last digit even
3 sum of all digits (recursively)
divisible by 3
4 Last 2 digits divisible by 4
5 Last digit 0 or 5
6 test 2 & 3
7 see below...
8 Last 3 digits divisible by 8
9 sum of all digits (recursively)
divisible by 9
10 that's an easy one!
11 this one is interesting 
sum up alternate digits starting with first  call this a
sum up alternate digits starting with the second  call this b
if (ab) = 0 or 11, the number is evenly divisible by 11!
I never found a way to test for divisibility by 7, though i spent many misspent
hours in my youth trying!
1996\04\11@081931
by
Martin Nilsson

"R.Radhakrishnan" <RemoveMEkrishKILLspamMCS.COM>:
> After following this thread with interest for a while, may I point out the
> following tests:
>
> Divisible (evenly) by: Test
...
> I never found a way to test for divisibility by 7, though i spent many
misspent
> hours in my youth trying!
Group the digits six and six, and add them up. If the result is divisible by
7, so is the original number. Example: 123456789 > 123 + 456789 = 456912 =
65273 * 7 + 1, so 123456789 is not divisible by 7.
A sixdigit number can be checked for divisibility by 7 as follows:
Subtract the first three digits from the last three: 456912 > 912456 = 456.
Multiply the first digit by 9 and the second digit by 3, add them up, and
repeat until obviously divisible or indivisible by 7.
456 > 9*4+3*5+6 = 36+15+6 = 57 > 3*5 + 7 = 22 > 3*2+1 > 8 = 7+1.
In general, suppose the period of the rational number 1/n is p (p=6
for n=7). You can test for divisibility by n by taking groups of p
digits and adding them up. Mathematically, the idea is that x mod n =
(x mod (10^p1)) mod n, since n is a divisor of 10^p1.
We don't have to use exactly 10^p1, but any modulus that is divisible
by n can be used. The example above for seven used the moduli
999999, 1001 (=143*7), and 7.
Incidentally, divisibility by 7 is much simpler in binary than base 10 since
1/7 = 0.001001001001... binary, and p=3, so checking is very easy.
Cheers,
 Martin
Martin Nilsson http://www.sics.se/~mn/
Swedish Institute of Computer Science Email: mnSTOPspamspam_OUTsics.se
Box 1263, S164 28 Kista Fax: +4687517230
Sweden Tel: +4687521574
More... (looser matching)
 Last day of these posts
 In 1996
, 1997 only
 Today
 New search...