piclist 2006\08\03\065022a >
Thread: 16 bit Mod 7 Math
techref.massmind.org/techref/microchip/math/index.htm?key=math
face
flavicon
face BY : Scott Dattalo email (remove spam text)



On Wed, 2006-08-02 at 13:35 -0700, Brooke Clarke wrote:

{Quote hidden}

Maybe a better way to think about the problem is in terms of number
bases and modulo arithmetic. For example, your goal is to compute DOW
mod 7 where DOW is the 16-bit representation of the day of the
week. You can write this as:

 DOW = DOW_HI*256 + DOW_LO

 DOW%7 = (DOW_HI*256 + DOW_LO) % 7
       = ((DOW_HI*256)%7  + (DOW_LO % 7)) %7
       = ((DOW_HI%7 * 256%7)  + (DOW_LO%7)) %7
       = ((DOW_HI%7 * 4)  + (DOW_LO%7)) %7

Expressed in this manner, you can separately compute the modulo 7
result for the high and low bytes. Multiply the result for the high by
4 and add it to the low and then finally compute result modulo 7.

Computing the mod 7 result of an 8-bit number can be performed in a
similar fashion. You can write an 8-bit number in octal like so:

  X = a*64 + b*8 + c

Where a, b, and c are 3-bit numbers.

  X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
      = (a%7 + b%7 + c%7) % 7
      = (a + b + c) % 7

since 64%7 = 8%7 = 1

Of course, a, b, and c are

  c = X & 7
  b = (X>>3) & 7
  a = (X>>6) & 7  (actually, a is only 2-bits).

The largest possible value for a+b+c is 7+7+3 = 17. So, you'll need
one more octal step. The complete (untested) C version could be
written like:

unsigned char Mod7Byte(unsigned char X)
{
 X = (X&7) + ((X>>3)&7) + (X>>6);
 X = (X&7) + (X>>3);

 return X==7 ? 0 : X;
}

I spent a few moments writing a PIC version. The actual implementation
is slightly different than described above



Mod7Byte:
       movwf        temp1        ;
       andlw        7        ;W=c
       movwf        temp2        ;temp2=c
       rlncf   temp1,F        ;
       swapf        temp1,W ;W= a*8+b
       andlw   0x1F
       addwf        temp2,W ;W= a*8+b+c
       movwf        temp2   ;temp2 is now a 6-bit number
       andlw   0x38    ;get the high 3 bits == a'
       xorwf        temp2,F ;temp2 now has the 3 low bits == b'
       rlncf   WREG,F  ;shift the high bits right 4
       swapf   WREG,F  ;
       addwf        temp2,W ;W = a' + b'

 ; at this point, W is between 0 and 10


       addlw        -7
       bc      Mod7Byte_L2
Mod7Byte_L1:
       addlw        7
Mod7Byte_L2:
       return



Here's a liitle routine to test the algorithm


       clrf    x
       clrf    count

TestLoop:
       movf        x,W
       RCALL   Mod7Byte
       cpfseq count
        bra    fail

       incf        count,W
       xorlw   7
       skpz
        xorlw        7
       movwf   count

       incfsz        x,F
       bra        TestLoop
passed:


Finally, for the 16-bit result (which I have not tested), you could
write:

uint16 Mod7Word(uint16 X)
{
 return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}


Scott
<62424.71.139.28.43.1154585257.squirrel@ruckus.brouhaha.com> 7bit

In reply to: <44D10CA1.4070603@pacific.net>
See also: techref.massmind.org/techref/microchip/math/index.htm?key=math

month overview.

new search...