Searching \ for 'Challenge' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=challenge
Search entire site for: 'Challenge'.

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

face
flavicon
face
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_OUTfastfwdTakeThisOuTspamix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

1996\04\07@213835 by Greg Young

flavicon
face
{Quote hidden}

...
>-Andy
>
>Andrew Warren - .....fastfwdKILLspamspam@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.

1996\04\07@215754 by Andrew Warren

face
flavicon
face
Greg Young <PICLISTspamKILLspamMITVMA.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}

   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 - .....fastfwdKILLspamspam.....ix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

1996\04\08@110234 by Bob Fehrenbach

picon face
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_OUTspamTakeThisOuTexecpc.com

1996\04\08@154036 by Bill Cornutt

flavicon
face
----------

>
>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

flavicon
picon face
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

face
flavicon
face
Bob Fehrenbach <PICLISTspamspam_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@fastfwdKILLspamspamix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

1996\04\08@183339 by Andrew Warren

face
flavicon
face
erik <KILLspamerikKILLspamspamdigits.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 - RemoveMEfastfwdTakeThisOuTspamix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

1996\04\08@200036 by Scott Dattalo

face
flavicon
face
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}

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

1996\04\08@211255 by Andrew Warren

face
flavicon
face
Scott Dattalo <spamBeGonePICLISTspamBeGonespamMITVMA.MIT.EDU> wrote:

{Quote hidden}

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 - TakeThisOuTfastfwdEraseMEspamspam_OUTix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

1996\04\08@214903 by John Payson

flavicon
face
> 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.

1996\04\09@000611 by John Payson

flavicon
face
>     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

picon face
Oh my...
{Quote hidden}

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   (RemoveMEtpetersonspamTakeThisOuTnetins.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: tpetersonEraseMEspam.....netins.net   (include POSTAL mailing address)
===========================================================

1996\04\09@012545 by Andrew Warren

face
flavicon
face
John Payson <EraseMEPICLISTspamMITVMA.MIT.EDU> wrote:

{Quote hidden}

   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 - RemoveMEfastfwdEraseMEspamEraseMEix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

1996\04\09@013832 by Andrew Warren

face
flavicon
face
John Payson <RemoveMEPICLISTspam_OUTspamKILLspamMITVMA.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 - RemoveMEfastfwdTakeThisOuTspamspamix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

1996\04\09@102017 by Bill Cornutt

flavicon
face
----------
{Quote hidden}

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
  EraseMEbillcornspamspamspamBeGoneinfoserv.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

flavicon
picon face
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

flavicon
face
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 (a-b) = 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 mis-spent
hours in my youth trying!

1996\04\10@133008 by R.Radhakrishnan

flavicon
face
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 (a-b) = 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 mis-spent
hours in my youth trying!

1996\04\11@081931 by Martin Nilsson

picon face
"R.Radhakrishnan" <RemoveMEkrishKILLspamspamMCS.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: mnSTOPspamspamspam_OUTsics.se
Box 1263, S-164 28 Kista                 Fax: +46-8-751-7230
Sweden                                   Tel: +46-8-752-1574

More... (looser matching)
- Last day of these posts
- In 1996 , 1997 only
- Today
- New search...