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.

> 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