piclist 2001\04\07\135904a >
Thread: Rounding to closest 1's multiple, code enclosed :)
www.piclist.com/techref/microchip/devices.htm?key=pic
BY : Scott Dattalo email (remove spam text)

I'd like to expand on Bob's idea a little.

To recap, we have a 24bit number and we'd like to find a smaller number that is
congruent to it modulo 5. In other words, if we divide the 24 bit number by 5
and the smaller number by 5 we get the same remainder. Perhaps a little table
can illustrate the pattern:

N   N % 5 (modulo operator)
-----------------------------
0   0
1   1
2   2
3   3
4   4
5   0
6   1
7   2
8   3
9   4
10   0
11   1
.
.
.

The right column is the remainder after the left column has been divided by
5. In modulo parlance, we'd say 11 is congruent to 1 modulo 5.

Bob's observation is that a 24 bit number may represented (in base 256) like:

N =  H*256^2 + M*256^1 + L*256^0
=  H*65536 + M*256 + L
=  H*65535 + M*255 + L  + H + M

And as he pointed out, if we want to determine a smaller number congruent to
this modulo 5, then we only need to sum L,M, and H.

Why?

Well take the middle byte:

(M*255 )%5 = (M%5) * (255%5)
= (M%5) * 0
= 0

255 is congruent to 0 mod 5. The same is true for 65535 and the high byte
product.

So the first simplification (again as Bob notes):

N%5 == (H+L+M)%5

But we can continue! The H+L+M sum is less than or equal to 255*3, which is only
a 10 bit number. Split this into a 2-byte number like so:

N%5 == (H+L+M)%5
== (H2:M2)%5
== (256*H2 + M2) %5
== (H2 + M2) %5

This might produce a 9-bit number, but there's an assembly trick to get it back
to 8. So, assume for now that H2+M2 < 256. Now, let's look at nibbles:

N2 = H2+M2
= a*16 + b
= a*15 + a + b

N2%5 == (a+b)%5

This is at most a 5bit number. But again, there's an assembly trick to make it a
nibble. Here's the whole thing in assembly.

; Compute N % 5, where N is a 24-bit number H:M:L

clrf  temp       ; Add the three bytes together
movf  L,w
rlf   temp,f
skpnc
incf temp,f

;; temp = H2, W = L2

addwf temp,f   ;temp = L2+H2, carry has 9'th bit
skpnc
incf temp,f   ;temp is less than 5, so we could return...

; Now for the nibbles

swapf temp,w
skpndc
incf temp,f

At this point, the lower nibble contains a number that is congruent modulo 5 to
the 24 bit number. If we want to convert this to a number between 0 and 5:

movf    temp,w  ;(or we could cause the previous instructions
; to leave the result in W)
addlw   -10     ;If the nibble >=10, then subtract 10
skpdc

; now the nibble is between 0 and 9
addlw   -5      ;if we're between 5 and 9, subtract 5
skpdc

That's 21 instructions to get the modulo 5 of a 24 bit number (in the lower 3
bits of W).

Now it's not too hard to get the 10's digit if we have the 5's. Repeating the
modulo table with the 10's column:

N   N % 5   N % 10
-----------------------------
0     0       0
1     1       1
2     2       2
3     3       3
4     4       4
5     0       5
6     1       6
7     2       7
8     3       8
9     4       9
10     0       0
11     1       1
.
.
.

The trick to note now is that is that if the least significant bits of N and N%5
are different then we can add 5 to N%5 and get N%10 !

So continuing from above:

andlw  b00000111  ;Get rid of the junk
movwf  temp       ;Compare N%5
xorwf  L,w        ; to the low byte
andlw  1          ; - we're only interested in the LSB
skpz              ;If it's set

28 instructions total to get N%10. I reckon there's a trick or two lurking in
there.

Scott

--