----- Original Message ----- 
From: "Dave Tweed" <pic@dtweed.com>
To: <piclist@mit.edu>
Sent: Wednesday, April 29, 2009 7:19 AM
Subject: Re: [AVR] divide 48bit number by (constant) 125 ?


> William "Chops" Westfield wrote:
>> I want to calculate:
>>
>>    (ticks * <microsecondsPerTick>) / 1000
>>
>> to return the number of milliseconds elapsed based on a count
>> maintained by a timer ISR.  microsecondsPerTick is a nice constant
>> number like 1024 or 2048, so the multiplication becomes a shift, and
>> factoring out twos I get:
>>
>>    (ticks * (microsecondsPerTick/8)) / 125
>>
>> "ticks" is at least 40 bits, however, and the multiplication MUST NOT
>> OVERFLOW (been there, trying to fix that!), so I'm looking at at at
>> least a 48bit intermediate value.
>
> Do you have access to the ISR? I would be inclined to do the following,
> rather than (or in addition to) simply counting the raw ticks:
>
>    /* microseconds can be a 16-bit integer */
>    microseconds += microsecondsPerTick;
>    while (microseconds >= 1000) {
>        microseconds -= 1000;
>        ++milliseconds;
>    }
>
> -- Dave Tweed
> -- 
> http://www.piclist.com PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist

You can use a trick similar to a binary to decimal
conversion algorithm to convert your value.

A short description of the algorithm:

1: compute ticks * microseconds per tick
2: convert to a mixed radix representation where the low-order 3 (decimal) 
digits of the number are kept in a separate variable from the rest of the 
number.
3: toss out the low-order 3 digits, keeping the number containing the rest 
of the value.

A longer description in pseudo-C

uint16    in_hi;
uint16    in_mid;
uint16    in_low;

uint16    out_hi
uint16    out_mid
uint16    out_low
uint16    out_toss;

out_hi = out_mid = out_low = out_toss = 0;
for (i=0; i < 48; ++i)
{
       // double the output value, taking
       // ...into account its mixed radix
       // ...representation
       out_toss <<= 1;
       carry = 0
       if (out_toss > 1000)
       {
            out_toss -= 1000;
            carry = 1;
       }
       shift [out_hi:out_mid:out_low] left one bit
       shifting 'carry' into lsbit

       // add in the next bit of the input value
       // to the accumulated value. this is
       // simplified by the fact that we know
       // the low-order bit is a zero (after
       // the doubling above)
       shift [in_hi:in_mid:in_low] left one bit;
       if (the bit shifted out is 1)
             out_toss |= 1;
}

// the resulting millisecond count is in
// [out_hi:out_mid:out_low]

This could be very efficiently implemented in PIC assembly code, and I 
imagine it wouldn't be too much different for an AVR. It is a little ugly in 
true C because of the multiword shifts.






-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist