piclist 2001\04\07\135904a >
Thread: Rounding to closest 1's multiple, code enclosed :)
www.piclist.com/techref/microchip/devices.htm?key=pic
face
flavicon
face 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
   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


<Pine.LNX.4.21.0104070957080.24639-100000@tempest2.blackhat.net>

In reply to: <200104061514.RAA02328@mn10.swip.net>
See also: www.piclist.com/techref/microchip/devices.htm?key=pic
Reply You must be a member of the piclist mailing list (not only a www.piclist.com member) to post to the piclist. This form requires JavaScript and a browser/email client that can handle form mailto: posts.
Subject (change) Rounding to closest 1's multiple, code enclosed :)

month overview.

new search...