Searching \ for 'determine if ' 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=determine
Search entire site for: 'determine if'.

No exact or substring matches. trying for part
PICList Thread
'determine if # divisible by 3'
1997\05\29@193214 by Dwayne Reid

flavicon
face
G'day all!

I am looking for a way to determine if a byte value is divisible by 3 and
was about to appeal for help when I remembered that Andy Warren had started
a discussion on that very topic about a year ago.  I went looking in my mail
archives and found something that looked quite good written by John Payson.
I tried the shorter of the 2 routines that John posted and found problems
with it.  The longer (but faster) routine worked just fine.  I spent a
couple of hours with the problem routine and made changes which seem to work
just fine.

Some really neat concepts came out of that discussion that Andy started back
then.  I learned some really basic math stuff (casting out nines) that I had
never seen before.  Thank you to everyone who contributed.

Here is John's shorter routine:

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

The above routine works on some values, but fails on others (at least when
simulated on MPLAB-SIM 3.22.02).  Single stepping through the problem values
showed that setting bit 4 in both addends so as to force a carry to bit 5
was the problem: sometimes adding both bits was already going to cause a
carry to bit 5 and thus bit 5 needed to be incremented by 2, but was only
incremented by 1.  I'm not sure this makes sense; single step through the
code and you will see what I mean.

John is testing to see if the final bit pair (bits 5&6) is 11.  If it is 11,
then the original number is divisible by 3.  I simply modified the code to
add 1 directly instead of relying on a forced carry from bit 4.  It is the
same length and requires the same number of cycles.

       swapf   Number,w        ; split #, add 2 halves, keep Most Sig Nybble
       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.
       addwf   Number,w        ; If bits 6&7 are 1, # is divisible by 3
       addlw   b'00100000'     ; treat bits 6&7 as 2 bit #, increment
       andlw   b'01000000'
       skpz
        retlw  0               ; Return "nope"
       retlw   1               ; Return "yep"

My thanks again for all the help that I have recieved from piclist members.

Dwayne

Dwayne Reid   <spam_OUTdwaynerTakeThisOuTspamplanet.eon.net>
Trinity Electronics Systems Ltd    Edmonton, Alberta, CANADA
(403) 489-3199 voice     (403) 487-6397 fax


'determine if # divisible by 3 - PDB3WRM'
1997\06\05@193150 by sdattalo
face
flavicon
face
Dwayne Reid wrote:

> I am looking for a way to determine if a byte value is divisible by 3 and
> was about to appeal for help when I remembered that Andy Warren had started
> a discussion on that very topic about a year ago.  I went looking in my mail
> archives and found something that looked quite good written by John Payson.
> I tried the shorter of the 2 routines that John posted and found problems
> with it.  The longer (but faster) routine worked just fine.  I spent a
> couple of hours with the problem routine and made changes which seem to work
> just fine.

I was fascinated with John's algorithm when he first posted it.
However, I did not take the time until last weekend to really understand
how it works. Since there is some interesting number theory, algorithm
analysis, and PIC code, I think there may be several of you who are
interested in the results.

John's "divisible-by-three" algorithm plus Dwayne's modifications is
very similar to the "casting-out-nines" algorithm. The "casting-out-
nines" algorithm tests for whether a number is divisible by 9 by
summing up the individual (base-10) digits of the number and checking
whether the sum is divisible by 9. For example, 2+3+4=9 is divisible
by 9 so we know that 234 is too (and so is 243,342,324,423,432).

A "casting-out-threes" algorithm in base-4 is conceptually identical
to the "casting-out-nines" in base-10. For example, if we had 1221 in
base-4 we know it's divisible by 3 since 1+2+2+1 = 6 is divisible by 3.
Here's the "proof". A base-4 number can be written as:
    ____
    \
N = /___ a_i * 4^i

where the a_i's are the base-4 digits (0,1,2,3) of the number.

    ____
    \
N = /___ (a_i * (4^i - 1) + a_i )

If N is divisible by three, then N mod 3 is equal to 0. So take the
'mod 3' of each side:

          ____
          \
N mod 3 = /___ (((a_i * (4^i - 1)) mod 3) + (a_i mod 3))

Two observations:
a) 4^i - 1 is divisible by 3. This can be seen by re-writing

4^i-1 = 3*4^(i-1) + 3*4^(i-2) + ... + 3*4^0
Since each term in the sum is divisible by three, then the sum
is divisible by three too.

b) a_i mod 3 = a_i or 0 (because a_i = 0,1,2,3). Since we are looking
for the result of N mod 3 = 0, we can replace a_i mod 3 with a_i.

Combining these two observations:

          ____
          \
N mod 3=  /___ a_i    (mod 3)

If this sum is greater than 3, then we can repeat the algorithm.

PDB3WRM algorithm:
Now we are ready to look at John's "divide-by-three" PIC algorithm.
For brevity, let's write the input Number as a generic 4-digit
base-4 number:

Number = a*64 + b*16 + c*4 + d

Here's John's routine with Dwayne's modifications. I've added the
details
of how the routine modifies Number:

>         swapf   Number,w        ; split #, add 2 halves, keep Most Sig Nybble
 W = c*64 + d*16 + a*4 + b

>         addwf   Number,f        ; Note [MSN of Number] % 3 == old Number % 3
 Number = (a+c)*64 + (b+d)*16 + (a+c)*4 + (b+d)

>         rrf     Number,w        ; We want to add what are now upper and lower
 W = (a+c)*32 + (b+d)*8 + (a+c)*2 + (b+d)>>1
 carry = (b+d)&1    ;i.e. lsb of the sum of b and d is in the carry

>         rlf     Number,f        ;   two bits of MSN; 00 or 11 would be good.
 Number = (a+c)*128 + (b+d)*32 + (a+c)*8 + (b+d)*2 + (b+d)&1

>         addwf   Number,w        ; If bits 6&7 are 1, # is divisible by 3
 W = (a+c)*128 + (a+b+c+d)*32 + (a+b+c+d)*8 + (a+b+c+d)*2 +
     (b+d)>>1 + (b+d)&1

>         addlw   b'00100000'     ; treat bits 6&7 as 2 bit #, increment
>         andlw   b'01000000'
>         skpz
>          retlw  0               ; Return "nope"
>         retlw   1               ; Return "yep"

In the last equation it can be seen that the 4 digits are added
together.
Unfortunately, there's complicated interaction between the sums.
Furthermore
there's that annoying business with b and d at the end. However after
closer inspection, it can be shown that there are only 14 unique cases
that
need to be analyzed. 13 cases are due to the sum of the digits ranging
from
0 to 12 (the numbers are in binary):

(a+b+c+d)   |  (a+b+c+d)*32 + (a+b+c+d)*8 + (a+b+c+d)*2
-------------+------------------------------------------
==> 0000     |    00000000
   0001     |    00101010
   0010     |    01010100
==> 0011     |    01111110
   0100     |    10101000
   0101     |    11010010
==> 0110     |    11111100
   0111     |    00100110
   1000     |    01010000
==> 1001     |    01111010
   1010     |    10100100
   1011     |    11001110
==> 1100     |    11111000

All rows marked with '==>' correspond to a sum of base-4 digits that
is divisible by three. The key thing to note is that bits 5 & 6 are
the same value in the second column for those numbers divisible by 3.
The last four lines of the PIC program cleverly detect this.

We have one more case to consider that concerns the expression
 (b+d)>>1 + (b+d)&1
that the PIC algorithm adds to the second column of data in the table.
This expression evaluates to either 0,1,2, or 3. Adding these numbers
to the second column of data only affects bits 5 & 6 for the case
when the sum of the digits is 0011. And even there it has the effect of
changing those bits from highs to lows. So the condition that "bits 5
& 6 are the same" is unchanged.

Oh btw, the state of the carry bit upon entry has no effect on the
result.

One more observation. The expression in the second column of the table
can be re-written:
(a+b+c+d)*32 + (a+b+c+d)*8 + (a+b+c+d)*2 = (a+b+c+d)*42
And the last four steps in the program check bits 5&6 for mod 3'ness.
This can be expressed like so:

Number mod 3 = ((a+b+c+d)*21)/16 mod 3

where Number = a*64+b*16+c*4+d
Which I guess is a concise way of stating the "Payson-divisible-by-3-
with-the-Reid-Modification" or PDB3WRM algorithm.

> Some really neat concepts came out of that discussion that Andy started back
> then.

Yeah, he has a knack for that. Hey Andy, where have you been?


Scott
--
"The problem with television is not the resolution."
                                Hugh. F. Frohbach


'[PICLIST] determine if number is divisible by 3'
2001\03\05@201222 by Dwayne Reid
flavicon
face
Good day to all.

This is a re-visit of something discussed a few years ago - determine if a
number contained in an 8 bit register is divisible by 3.

The background is: I've got a timebase with a 20 second period as part of a
60 minute timer.  Due to changing client requirements, I needed to come up
with a 1 minute timer.

The obvious technique was to simply use 2 bits in a register configured as
a divide by 3 counter.

Simple code to do this:
;generate 1 min tick.  uses upper 2 bits of FLAG3 as divide by 3 counter
    movlw       b'01000000'
    addwf       FLAG3,F
    btfsc       FLAG3,7         ;count seq: 00, 01, 10
      goto      Tic1MinExit

    addwf       FLAG3,F         ;inc cntr from 10 to 11: turns 4/ into /3
    bsf         _T1MIN          ;1 min flag
Tic1MinExit

But at the time that I was coding that project, RAM was tight (the target
was a 16c71 with only 35 bytes of RAM.  I posed the question to the list -
Andy Warren and John Payson came to the rescue with one of those magical
little snippets.

I'm bringing this up because I am making more changes to that project.  In
doing so, I saw a way to shave 1 instruction / cycle from that magical
little snippet.

;determine if # is evenly divisible by 3.  Enters with # in TMP, exits with
TMP trashed
;Concept by John Payson, this version by Jophn Payson & Dwayne Reid
    swapf       TMP,w           ;split #, add 2 halves, keep MSN
    addwf       TMP,f           ;Note [MSN of ADRES] % 3 == old ADRES % 3
    rrf         TMP,w           ;We want to add what are now upper and lower
    rlf         TMP,f           ;  two bits of MSN; 00 or 11 would be good.
    addwf       TMP,w           ;If bits 5&6 are 1, # is divisible by 3
    addlw       b'00100000'     ;treat bits 5&6 as 2 bit #, increment
    btfss       TMP,6           ;if bit 6 is 0, number is divisible by 3
      bsf       _T1MIN          ;1 minute flag


The following is another of Scott Dattalo's excellent explanations of how
this snippet works:

<copy starts>

Dwayne Reid wrote:

> I am looking for a way to determine if a byte value is divisible by 3 and
> was about to appeal for help when I remembered that Andy Warren had started
> a discussion on that very topic about a year ago.  I went looking in my mail
> archives and found something that looked quite good written by John Payson.
> I tried the shorter of the 2 routines that John posted and found problems
> with it.  The longer (but faster) routine worked just fine.  I spent a
> couple of hours with the problem routine and made changes which seem to work
> just fine.

I was fascinated with John's algorithm when he first posted it.
However, I did not take the time until last weekend to really understand
how it works. Since there is some interesting number theory, algorithm
analysis, and PIC code, I think there may be several of you who are
interested in the results.

John's "divisible-by-three" algorithm plus Dwayne's modifications is
very similar to the "casting-out-nines" algorithm. The "casting-out-
nines" algorithm tests for whether a number is divisible by 9 by
summing up the individual (base-10) digits of the number and checking
whether the sum is divisible by 9. For example, 2+3+4=9 is divisible
by 9 so we know that 234 is too (and so is 243,342,324,423,432).

A "casting-out-threes" algorithm in base-4 is conceptually identical
to the "casting-out-nines" in base-10. For example, if we had 1221 in
base-4 we know it's divisible by 3 since 1+2+2+1 = 6 is divisible by 3.
Here's the "proof". A base-4 number can be written as:
     ____
     \
 N = /___ a_i * 4^i

where the a_i's are the base-4 digits (0,1,2,3) of the number.

     ____
     \
 N = /___ (a_i * (4^i - 1) + a_i )

If N is divisible by three, then N mod 3 is equal to 0. So take the
'mod 3' of each side:

           ____
           \
 N mod 3 = /___ (((a_i * (4^i - 1)) mod 3) + (a_i mod 3))

Two observations:
a) 4^i - 1 is divisible by 3. This can be seen by re-writing

 4^i-1 = 3*4^(i-1) + 3*4^(i-2) + ... + 3*4^0
Since each term in the sum is divisible by three, then the sum
is divisible by three too.

b) a_i mod 3 = a_i or 0 (because a_i = 0,1,2,3). Since we are looking
for the result of N mod 3 = 0, we can replace a_i mod 3 with a_i.

Combining these two observations:

           ____
           \
 N mod 3=  /___ a_i    (mod 3)

If this sum is greater than 3, then we can repeat the algorithm.

PDB3WRM algorithm:
Now we are ready to look at John's "divide-by-three" PIC algorithm.
For brevity, let's write the input Number as a generic 4-digit
base-4 number:

Number = a*64 + b*16 + c*4 + d

Here's John's routine with Dwayne's modifications. I've added the
details
of how the routine modifies Number:

>         swapf   Number,w        ; split #, add 2 halves, keep Most Sig
Nybble
  W = c*64 + d*16 + a*4 + b

>         addwf   Number,f        ; Note [MSN of Number] % 3 == old Number % 3
  Number = (a+c)*64 + (b+d)*16 + (a+c)*4 + (b+d)

>         rrf     Number,w        ; We want to add what are now upper and
lower
  W = (a+c)*32 + (b+d)*8 + (a+c)*2 + (b+d)>>1
  carry = (b+d)&1    ;i.e. lsb of the sum of b and d is in the carry

>         rlf     Number,f        ;   two bits of MSN; 00 or 11 would be good.
  Number = (a+c)*128 + (b+d)*32 + (a+c)*8 + (b+d)*2 + (b+d)&1

>         addwf   Number,w        ; If bits 6&7 are 1, # is divisible by 3
  W = (a+c)*128 + (a+b+c+d)*32 + (a+b+c+d)*8 + (a+b+c+d)*2 +
      (b+d)>>1 + (b+d)&1

>         addlw   b'00100000'     ; treat bits 6&7 as 2 bit #, increment
>         andlw   b'01000000'
>         skpz
>          retlw  0               ; Return "nope"
>         retlw   1               ; Return "yep"

In the last equation it can be seen that the 4 digits are added
together.
Unfortunately, there's complicated interaction between the sums.
Furthermore
there's that annoying business with b and d at the end. However after
closer inspection, it can be shown that there are only 14 unique cases
that
need to be analyzed. 13 cases are due to the sum of the digits ranging
from
0 to 12 (the numbers are in binary):

 (a+b+c+d)   |  (a+b+c+d)*32 + (a+b+c+d)*8 + (a+b+c+d)*2
-------------+------------------------------------------
==> 0000     |    00000000
    0001     |    00101010
    0010     |    01010100
==> 0011     |    01111110
    0100     |    10101000
    0101     |    11010010
==> 0110     |    11111100
    0111     |    00100110
    1000     |    01010000
==> 1001     |    01111010
    1010     |    10100100
    1011     |    11001110
==> 1100     |    11111000

All rows marked with '==>' correspond to a sum of base-4 digits that
is divisible by three. The key thing to note is that bits 5 & 6 are
the same value in the second column for those numbers divisible by 3.
The last four (now 3) lines of the PIC program cleverly detect this.

We have one more case to consider that concerns the expression
  (b+d)>>1 + (b+d)&1
that the PIC algorithm adds to the second column of data in the table.
This expression evaluates to either 0,1,2, or 3. Adding these numbers
to the second column of data only affects bits 5 & 6 for the case
when the sum of the digits is 0011. And even there it has the effect of
changing those bits from highs to lows. So the condition that "bits 5
& 6 are the same" is unchanged.

Oh btw, the state of the carry bit upon entry has no effect on the
result.

One more observation. The expression in the second column of the table
can be re-written:
(a+b+c+d)*32 + (a+b+c+d)*8 + (a+b+c+d)*2 = (a+b+c+d)*42
And the last four (3) steps in the program check bits 5&6 for mod 3'ness.
This can be expressed like so:

 Number mod 3 = ((a+b+c+d)*21)/16 mod 3

where Number = a*64+b*16+c*4+d
Which I guess is a concise way of stating the "Payson-divisible-by-3-
with-the-Reid-Modification" or PDB3WRM algorithm.

<end of copy>

I hope this is usable for someone else.

dwayne


Dwayne Reid   <.....dwaynerKILLspamspam@spam@planet.eon.net>
Trinity Electronics Systems Ltd    Edmonton, AB, CANADA
(780) 489-3199 voice          (780) 487-6397 fax

Celebrating 17 years of Engineering Innovation (1984 - 2001)

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Do NOT send unsolicited commercial email to this email address.
This message neither grants consent to receive unsolicited
commercial email nor is intended to solicit commercial email.

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.


2001\03\06@120239 by Dwayne Reid

flavicon
face
re-send to the list because of missing tag.

Good day to all.

This is a re-visit of something discussed a few years ago - determine if a
number contained in an 8 bit register is divisible by 3.

The background is: I've got a timebase with a 20 second period as part of a
60 minute timer.  Due to changing client requirements, I needed to come up
with a 1 minute timer.

The obvious technique was to simply use 2 bits in a register configured as
a divide by 3 counter.

Simple code to do this:
;generate 1 min tick.  uses upper 2 bits of FLAG3 as divide by 3 counter
    movlw       b'01000000'
    addwf       FLAG3,F
    btfsc       FLAG3,7         ;count seq: 00, 01, 10
      goto      Tic1MinExit

    addwf       FLAG3,F         ;inc cntr from 10 to 11: turns 4/ into /3
    bsf         _T1MIN          ;1 min flag
Tic1MinExit

But at the time that I was coding that project, RAM was tight (the target
was a 16c71 with only 35 bytes of RAM.  I posed the question to the list -
Andy Warren and John Payson came to the rescue with one of those magical
little snippets.

I'm bringing this up because I am making more changes to that project.  In
doing so, I saw a way to shave 1 instruction / cycle from that magical
little snippet.

;determine if # is evenly divisible by 3.  Enters with # in TMP, exits with
TMP trashed
;Concept by John Payson, this version by Jophn Payson & Dwayne Reid
    swapf       TMP,w           ;split #, add 2 halves, keep MSN
    addwf       TMP,f           ;Note [MSN of ADRES] % 3 == old ADRES % 3
    rrf         TMP,w           ;We want to add what are now upper and lower
    rlf         TMP,f           ;  two bits of MSN; 00 or 11 would be good.
    addwf       TMP,w           ;If bits 5&6 are 1, # is divisible by 3
    addlw       b'00100000'     ;treat bits 5&6 as 2 bit #, increment
    btfss       TMP,6           ;if bit 6 is 0, number is divisible by 3
      bsf       _T1MIN          ;1 minute flag


The following is another of Scott Dattalo's excellent explanations of how
this snippet works:

<copy starts>

Dwayne Reid wrote:

> I am looking for a way to determine if a byte value is divisible by 3 and
> was about to appeal for help when I remembered that Andy Warren had started
> a discussion on that very topic about a year ago.  I went looking in my mail
> archives and found something that looked quite good written by John Payson.
> I tried the shorter of the 2 routines that John posted and found problems
> with it.  The longer (but faster) routine worked just fine.  I spent a
> couple of hours with the problem routine and made changes which seem to work
> just fine.

I was fascinated with John's algorithm when he first posted it.
However, I did not take the time until last weekend to really understand
how it works. Since there is some interesting number theory, algorithm
analysis, and PIC code, I think there may be several of you who are
interested in the results.

John's "divisible-by-three" algorithm plus Dwayne's modifications is
very similar to the "casting-out-nines" algorithm. The "casting-out-
nines" algorithm tests for whether a number is divisible by 9 by
summing up the individual (base-10) digits of the number and checking
whether the sum is divisible by 9. For example, 2+3+4=9 is divisible
by 9 so we know that 234 is too (and so is 243,342,324,423,432).

A "casting-out-threes" algorithm in base-4 is conceptually identical
to the "casting-out-nines" in base-10. For example, if we had 1221 in
base-4 we know it's divisible by 3 since 1+2+2+1 = 6 is divisible by 3.
Here's the "proof". A base-4 number can be written as:
     ____
     \
 N = /___ a_i * 4^i

where the a_i's are the base-4 digits (0,1,2,3) of the number.

     ____
     \
 N = /___ (a_i * (4^i - 1) + a_i )

If N is divisible by three, then N mod 3 is equal to 0. So take the
'mod 3' of each side:

           ____
           \
 N mod 3 = /___ (((a_i * (4^i - 1)) mod 3) + (a_i mod 3))

Two observations:
a) 4^i - 1 is divisible by 3. This can be seen by re-writing

 4^i-1 = 3*4^(i-1) + 3*4^(i-2) + ... + 3*4^0
Since each term in the sum is divisible by three, then the sum
is divisible by three too.

b) a_i mod 3 = a_i or 0 (because a_i = 0,1,2,3). Since we are looking
for the result of N mod 3 = 0, we can replace a_i mod 3 with a_i.

Combining these two observations:

           ____
           \
 N mod 3=  /___ a_i    (mod 3)

If this sum is greater than 3, then we can repeat the algorithm.

PDB3WRM algorithm:
Now we are ready to look at John's "divide-by-three" PIC algorithm.
For brevity, let's write the input Number as a generic 4-digit
base-4 number:

Number = a*64 + b*16 + c*4 + d

Here's John's routine with Dwayne's modifications. I've added the
details
of how the routine modifies Number:

>         swapf   Number,w        ; split #, add 2 halves, keep Most Sig
Nybble
  W = c*64 + d*16 + a*4 + b

>         addwf   Number,f        ; Note [MSN of Number] % 3 == old Number % 3
  Number = (a+c)*64 + (b+d)*16 + (a+c)*4 + (b+d)

>         rrf     Number,w        ; We want to add what are now upper and
lower
  W = (a+c)*32 + (b+d)*8 + (a+c)*2 + (b+d)>>1
  carry = (b+d)&1    ;i.e. lsb of the sum of b and d is in the carry

>         rlf     Number,f        ;   two bits of MSN; 00 or 11 would be good.
  Number = (a+c)*128 + (b+d)*32 + (a+c)*8 + (b+d)*2 + (b+d)&1

>         addwf   Number,w        ; If bits 6&7 are 1, # is divisible by 3
  W = (a+c)*128 + (a+b+c+d)*32 + (a+b+c+d)*8 + (a+b+c+d)*2 +
      (b+d)>>1 + (b+d)&1

>         addlw   b'00100000'     ; treat bits 6&7 as 2 bit #, increment
>         andlw   b'01000000'
>         skpz
>          retlw  0               ; Return "nope"
>         retlw   1               ; Return "yep"

In the last equation it can be seen that the 4 digits are added
together.
Unfortunately, there's complicated interaction between the sums.
Furthermore
there's that annoying business with b and d at the end. However after
closer inspection, it can be shown that there are only 14 unique cases
that
need to be analyzed. 13 cases are due to the sum of the digits ranging
from
0 to 12 (the numbers are in binary):

 (a+b+c+d)   |  (a+b+c+d)*32 + (a+b+c+d)*8 + (a+b+c+d)*2
-------------+------------------------------------------
==> 0000     |    00000000
    0001     |    00101010
    0010     |    01010100
==> 0011     |    01111110
    0100     |    10101000
    0101     |    11010010
==> 0110     |    11111100
    0111     |    00100110
    1000     |    01010000
==> 1001     |    01111010
    1010     |    10100100
    1011     |    11001110
==> 1100     |    11111000

All rows marked with '==>' correspond to a sum of base-4 digits that
is divisible by three. The key thing to note is that bits 5 & 6 are
the same value in the second column for those numbers divisible by 3.
The last four (now 3) lines of the PIC program cleverly detect this.

We have one more case to consider that concerns the expression
  (b+d)>>1 + (b+d)&1
that the PIC algorithm adds to the second column of data in the table.
This expression evaluates to either 0,1,2, or 3. Adding these numbers
to the second column of data only affects bits 5 & 6 for the case
when the sum of the digits is 0011. And even there it has the effect of
changing those bits from highs to lows. So the condition that "bits 5
& 6 are the same" is unchanged.

Oh btw, the state of the carry bit upon entry has no effect on the
result.

One more observation. The expression in the second column of the table
can be re-written:
(a+b+c+d)*32 + (a+b+c+d)*8 + (a+b+c+d)*2 = (a+b+c+d)*42
And the last four (3) steps in the program check bits 5&6 for mod 3'ness.
This can be expressed like so:

 Number mod 3 = ((a+b+c+d)*21)/16 mod 3

where Number = a*64+b*16+c*4+d
Which I guess is a concise way of stating the "Payson-divisible-by-3-
with-the-Reid-Modification" or PDB3WRM algorithm.

<end of copy>

I hope this is usable for someone else.

dwayne


Dwayne Reid   <dwaynerspamKILLspamplanet.eon.net>
Trinity Electronics Systems Ltd    Edmonton, AB, CANADA
(780) 489-3199 voice          (780) 487-6397 fax

Celebrating 17 years of Engineering Innovation (1984 - 2001)

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Do NOT send unsolicited commercial email to this email address.
This message neither grants consent to receive unsolicited
commercial email nor is intended to solicit commercial email.

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email .....listservKILLspamspam.....mitvma.mit.edu with SET PICList DIGEST in the body


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