32-bit IEEE float multiplication

[Eric Sosman]

Re: 32-bit IEEE float multiplication

Andy wrote:[color=blue]
>
> Eric,
> My goal is to provide a generic timing device which would
> provide accuracy (although not exact) from days down to
> milliseconds. The idea is to have a free running 32-bit
> timer (tick) that all others compare for timing. I'm using
> multiplication because the idea is to not limit the
> free running tick counter to 1 frequence (as in my previous
> examples 4 milliseconds). Maybe a concrete example would help.
>
> typedef unsigned long GCLK_T;
> GCLK_T gzFreeTicks; /* this gets incremented in an ISR */
> GCLK_T GCLK(void); /* provides atomic read of gzFreeTicks */
>
> #define SECS_PER_TICK 0.004 /* seconds for each tick */
> #define MSECS_TO_TICKS( MSECS) xxxx /* converting milliseconds to ticks */
>
> GCLK_T ElapsedTicks(GC LK_T ticks) {
> return(GCLK() - ticks);
> }
>
> unsigned long ElapsedSecs(GCL K_T ticks) {
> return((float)E lapsedTicks(tic ks) * (float)(SECS_PE R_TICK));
> }[/color]

Since you only care about the whole seconds, why bother
with floating-point at all?

unsigned long ElapsedSecs(GCL C_T ticks) {
return ticks / TICKS_PER_SEC; // new constant
/* or, if you want rounding: */
return (ticks + TICKS_PER_SEC / 2) / TICKS_PER_SEC;
}
[color=blue]
> /* has a endless loop with one 100 millisecond task */
> void main(void) {[/color]

This is the first time I've seen `void main' used
properly.

--
Eric.Sosman@sun .com

[Dan Pop]

Re: 32-bit IEEE float multiplication

In <5c04bc56.03120 51449.5d69bb22@ posting.google. com> jjf@bcs.org.uk (J. J. Farrell) writes:
[color=blue]
>bikejog@hotmai l.com (Andy) wrote in message news:<aed59298. 0312050738.38f1 3268@posting.go ogle.com>...[color=green]
>> Christian Bau <christian.bau@ cbau.freeserve. co.uk> wrote in message news:<christian .bau-2F3655.22593304 122003@slb-newsm1.svr.pol. co.uk>...[color=darkred]
>> >
>> > Is there a good reason why you don't write
>> >
>> > ticks / 250[/color]
>>
>> Yes. I do not want to wast CPU cycles. My intend is not really
>> to cover all the integral values when the number gets huge. If I
>> only loose one second for anything greater than 2^24 (that's >18 hours
>> BTW), then that's ok. With 32-bits, I should be able to cover
>> something like 198 days and if the error is even one minute out
>> of 180 days, then that's fine, but one day is not. What's the
>> maximum error I can expect?[/color]
>
>Excuse me if this point is stupid, as I know next to nothing
>about FP arithmetic. I don't see how ((float)ticks * 0.004f) can
>possibly use fewer cycles than (float)(ticks / 250), particularly
>on a system without hardware floating point arithmetic.[/color]

A system without hardware floating point arithmetic may not have hardware
support for 32-bit integer division, either. This is, indeed, the
case with the OP's system. So, if you perform integer division on
ticks, you have to perform 32-bit integer division. If you perform
single precision floating point multiplication, you have to actually
perform 24-bit integer multiplication plus a few other simple operations.
Also keep in mind that multiplication algorithms are usually faster than
division algorithms.

But the OP doesn't need any form of multiplication or division for
what he wants to achieve, everything can be done with integer addition,
using a tick counter and a second counter. When the tick counter reaches
the value 250, it is reset and the second counter is incremented. And
the tick counter can be a single byte, which is very convenient for an
8-bit microcontroller .

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Dan.Pop@ifh.de

[Eric Sosman]

Re: 32-bit IEEE float multiplication

Dan Pop wrote:[color=blue]
>
> But the OP doesn't need any form of multiplication or division for
> what he wants to achieve, everything can be done with integer addition,
> using a tick counter and a second counter. When the tick counter reaches
> the value 250, it is reset and the second counter is incremented. And
> the tick counter can be a single byte, which is very convenient for an
> 8-bit microcontroller .[/color]

It's not clear to me that he gets access to each tick
as it occurs (if it does, keeping a pair of counters for
"seconds" and "ticks since last second" is easy). The
usage he showed involved reading an arbitrary tick value
and converting to seconds; division seems the straightforward
approach.

If even integer division is really expensive *and* if
the conversions are usually performed on tick values that
are "close together," a simple cache might help:

unsigned long ElapsedSecs(GCL K_T ticks) {
static unsigned long lastsecs = 0;
static GCLK_T loticks = 0;
static GCLK_T hiticks = TICKS_PER_SEC;

if (loticks <= ticks && ticks < hiticks) {
/* Still in the same second as last time;
* no arithmetic required.
*/
}
else if (hiticks <= ticks && ticks < hiticks + TICKS_PER_SEC) {
/* Advanced to the next second; the arithmetic
* is very simple.
*/
loticks = hiticks;
hiticks += TICKS_PER_SEC;
++lastsecs;
}
else {
/* Aw, shucks: Do it the hard way. With luck
* this won't happen very often.
*/
lastsecs = ticks / TICKS_PER_SEC;
loticks = lastsecs * TICKS_PER_SEC;
hiticks = loticks + TICKS_PER_SEC;
}

return lastsecs;
}

--
Eric.Sosman@sun .com

[J. J. Farrell]

Re: 32-bit IEEE float multiplication

bikejog@hotmail .com (Andy) wrote in message news:<aed59298. 0312051931.60d2 b7e8@posting.go ogle.com>...[color=blue]
>
> My goal is to provide a generic timing device which would
> provide accuracy (although not exact) from days down to
> milliseconds. The idea is to have a free running 32-bit
> timer (tick) that all others compare for timing. I'm using
> multiplication because the idea is to not limit the
> free running tick counter to 1 frequence (as in my previous
> examples 4 milliseconds). Maybe a concrete example would help.
>
> typedef unsigned long GCLK_T;
> GCLK_T gzFreeTicks; /* this gets incremented in an ISR */
> GCLK_T GCLK(void); /* provides atomic read of gzFreeTicks */
>
> #define SECS_PER_TICK 0.004 /* seconds for each tick */
> #define MSECS_TO_TICKS( MSECS) xxxx /* converting milliseconds to ticks */
>
> GCLK_T ElapsedTicks(GC LK_T ticks) {
> return(GCLK() - ticks);
> }
>
> unsigned long ElapsedSecs(GCL K_T ticks) {
> return((float)E lapsedTicks(tic ks) * (float)(SECS_PE R_TICK));
> }
>
> /* has a endless loop with one 100 millisecond task */
> void main(void) {
> GCLK_T zMyTicks;
>
> zMyTicks = GCLK();
> while(1) {
> /* this provides a very fast compare */
> if (ElapsedTicks(z MyTicks) > MSECS_TO_TICKS( 100)) {
> Do100Millisecon dTask();
> zMyTicks = GCLK();
> }
> }
> }[/color]

You seem to be talking about a straightforward tick-based timer
system. I've seen many implementations done in a variety of ways,
but I've never seen anyone bring FP into it before.

I suggest stepping back and rethinking exactly what you are trying
to achieve. Depending on the granularity required, you can almost
certainly do everything you need with integer multiplication and
division. More likely than not, you can do it efficiently with
integer addition and subtraction. For example, your ISR could
keep a count of milliseconds by having another counter to hold
milliseconds and wrapping the tick counter to zero each time it
crosses a millisecond boundary. If your ISR timing is so tight
that this can't be done in the ISR, you could have some lower
priority code (or even the routines that use the counter) watch
for the tick count passing the millisecond boundary and do the
carry arithmetic by iterative subtraction from the tick count
(with suitable interlocking with the ISR). There are any number
of variants depending on your exact requirements and constraints,
but you shouldn't need to pain yourself with the overheads and
inaccuracies inherent in FP arithmetic done in software.

There are lots of examples of this sort of thing available on
the net - the clock and timer routines in some of the free UNIX-
like OSes (such as OpenBSD) might be useful.

[Dik T. Winter]

Re: 32-bit IEEE float multiplication

In article <3FD4BE60.3409B 68A@sun.com> Eric.Sosman@Sun .COM writes:[color=blue]
> Dan Pop wrote:[color=green]
> >
> > But the OP doesn't need any form of multiplication or division for
> > what he wants to achieve, everything can be done with integer addition,
> > using a tick counter and a second counter. When the tick counter reaches
> > the value 250, it is reset and the second counter is incremented. And
> > the tick counter can be a single byte, which is very convenient for an
> > 8-bit microcontroller .[/color]
>
> It's not clear to me that he gets access to each tick
> as it occurs (if it does, keeping a pair of counters for
> "seconds" and "ticks since last second" is easy). The
> usage he showed involved reading an arbitrary tick value
> and converting to seconds; division seems the straightforward
> approach.[/color]

Indeed, that is also the way I did read it (and I think he later did
confirm this). So he has in his hand a 32 bit tick counter, and he
wants to divide it by 250.
[color=blue]
> If even integer division is really expensive *and* if
> the conversions are usually performed on tick values that
> are "close together," a simple cache might help:
>
> unsigned long ElapsedSecs(GCL K_T ticks) {
> static unsigned long lastsecs = 0;
> static GCLK_T loticks = 0;
> static GCLK_T hiticks = TICKS_PER_SEC;
>
> if (loticks <= ticks && ticks < hiticks) {
> /* Still in the same second as last time;
> * no arithmetic required.
> */
> }
> else if (hiticks <= ticks && ticks < hiticks + TICKS_PER_SEC) {
> /* Advanced to the next second; the arithmetic
> * is very simple.
> */
> loticks = hiticks;
> hiticks += TICKS_PER_SEC;
> ++lastsecs;
> }
> else {[/color]
/* the assumption here is: no wrap around... */[color=blue]
> /* Aw, shucks: Do it the hard way. With luck
> * this won't happen very often.
> */
> lastsecs = ticks / TICKS_PER_SEC;[/color]
Better do the calculations with 'ticks - hiticks'. When this is fairly
small it may be done using only a few shifts and adds on 16-bit values.[color=blue]
> loticks = lastsecs * TICKS_PER_SEC;
> hiticks = loticks + TICKS_PER_SEC;
> }[/color]

Rewriting the body:
if (loticks <= ticks && ticks < hiticks) {
return lastsecs;
}
if (ticks < loticks) {
/* wraparound, do not know what to do now */
}
if (ticks >= hiticks) {
/* going a harder way, more than one second. */
if (ticks - hiticks <= 32765) {
unsigned short i = ticks - highticks;
unsigned short j, diff;
j = (i >> 5) - (i >> 7);
diff = (i + j) >> 8;
/* at most one too small. */
lastsecs += diff;
diff = (diff << 8) - (diff << 2) - (diff << 1);
loticks += diff;
hiticks += diff;
} else {
/* a bit more brute force here. only when the
difference can exceed 131 seconds. can be done
in a similar way with 32 bit values. */
}
}
if (ticks >= hiticks) {
loticks = hiticks;
hiticks += TICKS_PER_SEC;
++lastsecs;
}
return lastsecs;
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Andy]

Re: 32-bit IEEE float multiplication

Yeah maybe you're right. All I need is a 32-bit millisecond
counter. That would give me almost 50 days. More than enough
for my needs.

Thanks
Andy

jjf@bcs.org.uk (J. J. Farrell) wrote in message news:<5c04bc56. 0312081537.799d aa8b@posting.go ogle.com>...[color=blue]
> bikejog@hotmail .com (Andy) wrote in message news:<aed59298. 0312051931.60d2 b7e8@posting.go ogle.com>...[color=green]
> >[/color]
>
> You seem to be talking about a straightforward tick-based timer
> system. I've seen many implementations done in a variety of ways,
> but I've never seen anyone bring FP into it before.
>
> I suggest stepping back and rethinking exactly what you are trying
> to achieve. Depending on the granularity required, you can almost
> certainly do everything you need with integer multiplication and
> division. More likely than not, you can do it efficiently with
> integer addition and subtraction. For example, your ISR could
> keep a count of milliseconds by having another counter to hold
> milliseconds and wrapping the tick counter to zero each time it
> crosses a millisecond boundary. If your ISR timing is so tight
> that this can't be done in the ISR, you could have some lower
> priority code (or even the routines that use the counter) watch
> for the tick count passing the millisecond boundary and do the
> carry arithmetic by iterative subtraction from the tick count
> (with suitable interlocking with the ISR). There are any number
> of variants depending on your exact requirements and constraints,
> but you shouldn't need to pain yourself with the overheads and
> inaccuracies inherent in FP arithmetic done in software.
>
> There are lots of examples of this sort of thing available on
> the net - the clock and timer routines in some of the free UNIX-
> like OSes (such as OpenBSD) might be useful.[/color]

[Dan Pop]

Re: 32-bit IEEE float multiplication

In <HpLuDq.4CC@cwi .nl> "Dik T. Winter" <Dik.Winter@cwi .nl> writes:
[color=blue]
>In article <3FD4BE60.3409B 68A@sun.com> Eric.Sosman@Sun .COM writes:[color=green]
> > Dan Pop wrote:[color=darkred]
> > >
> > > But the OP doesn't need any form of multiplication or division for
> > > what he wants to achieve, everything can be done with integer addition,
> > > using a tick counter and a second counter. When the tick counter reaches
> > > the value 250, it is reset and the second counter is incremented. And
> > > the tick counter can be a single byte, which is very convenient for an
> > > 8-bit microcontroller .[/color]
> >
> > It's not clear to me that he gets access to each tick
> > as it occurs (if it does, keeping a pair of counters for
> > "seconds" and "ticks since last second" is easy). The
> > usage he showed involved reading an arbitrary tick value
> > and converting to seconds; division seems the straightforward
> > approach.[/color]
>
>Indeed, that is also the way I did read it (and I think he later did
>confirm this). So he has in his hand a 32 bit tick counter, and he
>wants to divide it by 250.[/color]

The OP mentioned the 8051 microcontroller . The thing doesn't have any
kind of 32-bit hardware tick counter, hence my assumption that this
counter is implemented in software.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Dan.Pop@ifh.de

[Andy]

Re: 32-bit IEEE float multiplication

Yes, the tick is incremented in an ISR. All this discussion about
using integer arithmetic is fine as long the tick resolution
is even multiples of a second, but happens say if you need to increment
the tick once every 17.321 milliseconds? How would you do that using
integer?
I guess what I'm interested in is what is the maximum error
can I expect for the formula

fElapsedSecs = ulElapsedTicks * 0.004;

If I'm correct, the max error is very small like < 1e-4% for
the full range of 32-bit value of ulElapsedTicks. Correct??

TIA
Andy

Dan.Pop@cern.ch (Dan Pop) wrote in message news:<br4f5r$2v v$3@sunnews.cer n.ch>...[color=blue]
> The OP mentioned the 8051 microcontroller . The thing doesn't have any
> kind of 32-bit hardware tick counter, hence my assumption that this
> counter is implemented in software.
>
> Dan[/color]

[Eric Sosman]

Re: 32-bit IEEE float multiplication

Andy wrote:[color=blue]
>
> Yes, the tick is incremented in an ISR. All this discussion about
> using integer arithmetic is fine as long the tick resolution
> is even multiples of a second, but happens say if you need to increment
> the tick once every 17.321 milliseconds? How would you do that using
> integer?[/color]

#define USECS_PER_TICK 17321
static unsigned long seconds = 0, excess = 0;

/* At each tick: */
excess += USECS_PER_TICK;
if (excess >= 1000000) {
excess -= 1000000;
++seconds;
}


--
Eric.Sosman@sun .com

[glen herrmannsfeldt]

Re: 32-bit IEEE float multiplication

Andy wrote:[color=blue]
> Yes, the tick is incremented in an ISR. All this discussion about
> using integer arithmetic is fine as long the tick resolution
> is even multiples of a second, but happens say if you need to increment
> the tick once every 17.321 milliseconds? How would you do that using
> integer?[/color]

Multiply by one integer, generating a product that might take more
bits than the original number, then divide by a second number.

Last I knew, the 8051 didn't have floating point, but the above
method is my preference, even for processors that do.

-- glen

[glen herrmannsfeldt]

Re: 32-bit IEEE float multiplication

Eric Sosman wrote:
[color=blue]
> Andy wrote:
>[color=green]
>>Yes, the tick is incremented in an ISR. All this discussion about
>>using integer arithmetic is fine as long the tick resolution
>>is even multiples of a second, but happens say if you need to increment
>>the tick once every 17.321 milliseconds? How would you do that using
>>integer?[/color][/color]
[color=blue]
> #define USECS_PER_TICK 17321
> static unsigned long seconds = 0, excess = 0;
>
> /* At each tick: */
> excess += USECS_PER_TICK;
> if (excess >= 1000000) {
> excess -= 1000000;
> ++seconds;
> }[/color]

Even better than the multiply/divide I suggested.

Just like a phase accumulator.

-- glen

[Andy]

Re: 32-bit IEEE float multiplication

That's good stuff Eric. I'm tempted to use this
method to keep a milliseconds counter, but the problem
is that if I do that, then I'll end up using unsigned
long divisions to convert the milliseconds count
to seconds. This requires 200 bytes more ROM
space than if I were to use float division. (I'm
working with 8K ROM at the present). Do you
know another way to divide an unsigned long value by
1000 using say, short or unsigned short operations?

TIA
Andy


Eric Sosman <Eric.Sosman@su n.com> wrote in message news:<3FD62116. 4EFE5007@sun.co m>...[color=blue]
> Andy wrote:[color=green]
> >
> > Yes, the tick is incremented in an ISR. All this discussion about
> > using integer arithmetic is fine as long the tick resolution
> > is even multiples of a second, but happens say if you need to increment
> > the tick once every 17.321 milliseconds? How would you do that using
> > integer?[/color]
>
> #define USECS_PER_TICK 17321
> static unsigned long seconds = 0, excess = 0;
>
> /* At each tick: */
> excess += USECS_PER_TICK;
> if (excess >= 1000000) {
> excess -= 1000000;
> ++seconds;
> }[/color]

[glen herrmannsfeldt]

Re: 32-bit IEEE float multiplication

Andy wrote:
[color=blue]
> That's good stuff Eric. I'm tempted to use this
> method to keep a milliseconds counter, but the problem
> is that if I do that, then I'll end up using unsigned
> long divisions to convert the milliseconds count
> to seconds. This requires 200 bytes more ROM
> space than if I were to use float division. (I'm
> working with 8K ROM at the present). Do you
> know another way to divide an unsigned long value by
> 1000 using say, short or unsigned short operations?[/color]

(snip)
[color=blue][color=green]
>> #define USECS_PER_TICK 17321
>> static unsigned long seconds = 0, excess = 0;
>>
>> /* At each tick: */
>> excess += USECS_PER_TICK;
>> if (excess >= 1000000) {
>> excess -= 1000000;
>> ++seconds;
>> }[/color][/color]

Yes, the trick is to use a power of 2, or of 256, for the unit, so
that the long division is by a power of 2 or 256.

Instead of microseconds per tick, use a unit if 1/16777216 of a second.

At each tick, add 290598 to the accumulator, seconds will accumulate
three bytes from the least significant byte.

Though the above code doesn't require a division. The seconds are
incremented at the appropriate time, such that they are the result
of dividing a large number by 1000000, and excess is the remainder.

Using add with carry it is very easy to add multibyte numbers.

-- glen

[Dan Pop]

Re: 32-bit IEEE float multiplication

In <aed59298.03120 91809.77467f1@p osting.google.c om> bikejog@hotmail .com (Andy) writes:
[color=blue]
>That's good stuff Eric. I'm tempted to use this
>method to keep a milliseconds counter, but the problem
>is that if I do that, then I'll end up using unsigned
>long divisions to convert the milliseconds count
>to seconds.[/color]

I'm afraid I don't understand your problem. What millisecond count are
you talking about and why do you need to convert it to seconds?

Eric's code has a microsecond count and a second count. Do you need to
deal with fractions of a second or what?

Dan
[color=blue]
>Eric Sosman <Eric.Sosman@su n.com> wrote in message news:<3FD62116. 4EFE5007@sun.co m>...[color=green]
>> Andy wrote:[color=darkred]
>> >
>> > Yes, the tick is incremented in an ISR. All this discussion about
>> > using integer arithmetic is fine as long the tick resolution
>> > is even multiples of a second, but happens say if you need to increment
>> > the tick once every 17.321 milliseconds? How would you do that using
>> > integer?[/color]
>>
>> #define USECS_PER_TICK 17321
>> static unsigned long seconds = 0, excess = 0;
>>
>> /* At each tick: */
>> excess += USECS_PER_TICK;
>> if (excess >= 1000000) {
>> excess -= 1000000;
>> ++seconds;
>> }[/color][/color]
--
Dan Pop
DESY Zeuthen, RZ group
Email: Dan.Pop@ifh.de

[Andy]

Re: 32-bit IEEE float multiplication

What would you do then if you needed to know the milliseconds?
I'm lost...

TIA
Andy

glen herrmannsfeldt <gah@ugcs.calte ch.edu> wrote in message news:<ykwBb.792 9$8y1.37484@att bi_s52>...
[color=blue]
> Yes, the trick is to use a power of 2, or of 256, for the unit, so
> that the long division is by a power of 2 or 256.
>
> Instead of microseconds per tick, use a unit if 1/16777216 of a second.
>
> At each tick, add 290598 to the accumulator, seconds will accumulate
> three bytes from the least significant byte.
>
> Though the above code doesn't require a division. The seconds are
> incremented at the appropriate time, such that they are the result
> of dividing a large number by 1000000, and excess is the remainder.
>
> Using add with carry it is very easy to add multibyte numbers.
>
> -- glen[/color]