www.piclist.com/techref/microchip/devices.htm?key=pic

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

addwf M,w

rlf temp,f

addwf H,w

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

addwf temp,f

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

addlw 10

; now the nibble is between 0 and 9

addlw -5 ;if we're between 5 and 9, subtract 5

skpdc

addlw 5

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

movlw 5 ; we add 5 otherwise we add 0

addwf temp,w ; or f

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

there.

Scott

--

http://www.piclist.com hint: PICList Posts must start with ONE topic:

[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

In reply to: <200104061514.RAA02328@mn10.swip.net>

See also: www.piclist.com/techref/microchip/devices.htm?key=pic