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