Post by thread:Challenge

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 dope-smoking 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 60-some cycles, depending upon the actual value in TEST. Average speed over the whole [0-255] 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 256-byte (or even 32-byte) lookup tables; in fact, I considered posting a 16-bit 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 code-space 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

{Quote hidden}>Dudes: > >The following PIC 16C5x code tests for divisibility by 3, using an >algorithm credited to Lewis Carroll, the dope-smoking 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/non-zero. 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 14-bit 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.

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/non-zero. 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 14-bit 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 12-bit 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

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

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 [0-255], then progressively narrow the range, one step at a time, to [2-4]. 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 2-7 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 double-check 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

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 base-four system. Actually, my favorite quick-and-dirty 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 test-for-prime function. Andrew Warren - RemoveMEfastfwdTakeThisOuTix.netcom.com Fast Forward Engineering, Vista, California http://www.geocities.com/SiliconValley/2499

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 divide-by-3 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

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 13-26 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 on-line... 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

> 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 divide-by-3 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.

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 [0-255], then > progressively narrow the range, one step at a time, to [2-4]. > > 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 2-7 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 double-check 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) E-LAB Digital Engineering, Inc. P.O. Box 246 Lawton, IA 51030-0246 (712) 944-5344 Visit us at: http://www.netins.net/showcase/elab/ E-Mail Now for Your Free PICPlus(TM) Information Packet! TO: tpetersonEraseME.....netins.net (include POSTAL mailing address) ===========================================================

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

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' Hog-Weighing 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

---------- {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 dope-smoking 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. ----------------------------------------------------

"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 mis-spent > 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 -> 912-456 = 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^p-1)) mod n, since n is a divisor of 10^p-1. We don't have to use exactly 10^p-1, 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 E-mail: mnSTOPspamspam_OUTsics.se Box 1263, S-164 28 Kista Fax: +46-8-751-7230 Sweden Tel: +46-8-752-1574