32-bit IEEE float multiplication

A

Andy

Thanks for your great answers. As I understand it, as the tick
gets greater then 2^24, then all I'm loosing are the lower 8-bits
of the tick. Then since 256 is only 1 second, the worse thing
that happens is that the result will be rounded to the nearest
second or a little more than that. I will not even loose
anything close to a minute or an hour. Would I?

TIA
Andy
 
A

Andy

Using double is pretty much out of the question. I can tolerate
a stair-step of say less than 1 minute when the number gets huge.
As long as the error is relatively a small percentage of the
actual count. Is the worst case error 250/(2^32)? Or how do
you calculate the worse case error?
By the way, I'm kinda slow replying to the posts because
I'm using the google newfeed service. It has response time
of about 9 hours...

TIA
Andy
 
A

Andy

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?

TIA
Andy
 
E

Eric Sosman

Andy said:
Thanks for your great answers. As I understand it, as the tick
gets greater then 2^24, then all I'm loosing are the lower 8-bits
of the tick. Then since 256 is only 1 second, the worse thing
that happens is that the result will be rounded to the nearest
second or a little more than that. I will not even loose
anything close to a minute or an hour. Would I?

For the benefit of those who (like me) do not entirely
understand exactly what you're trying to do, could you
describe what these "ticks" are supposed to be and what
you are trying to do with them?

... and if you're trying to convert a 256 Hz "tick" to
seconds, multiplying by a floating-point value is surely a
poor way to proceed. Even an integer division is overkill;
a simple shift-and-mask will do all that's necessary. If
you're willing to think about fixed-point arithmetic, even
that tiny amount of work is more than required!

So, what's the goal?
 
C

Christian Bau

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?

Couldn't you just use two separate counters for seconds and ticks?

You are multiplying ticks by 0.004, so every 250 times you would add a
second. You could do something like this:

static unsigned long whole_seconds = 0;
static unsigned int sub_seconds = 0;
static unsigned long last_ticks;

Set last_ticks to ticks when you start. Then whenever you check ticks,
you do the following:


ticks = <calculate current time>
while (last_ticks != ticks) {
++last_ticks;
if (++sub_seconds == 250) { sub_seconds = 0; ++whole_seconds; }
}

No floating point arithmetic; that should be a bit faster on an 8051.
 
J

J. J. Farrell

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?

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.

I confess I'm puzzled by this whole discussion. What are you trying
to achieve? Why are you using FP arithmetic instead of integer -
particularly if CPU cycles are important? Unless I'm really missing
something, you'd get perfect accuracy up to 136 years with integer.

I guess I'm missing something obvious ...
 
A

Andy

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(GCLK_T ticks) {
return(GCLK() - ticks);
}

unsigned long ElapsedSecs(GCLK_T ticks) {
return((float)ElapsedTicks(ticks) * (float)(SECS_PER_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(zMyTicks) > MSECS_TO_TICKS(100)) {
Do100MillisecondTask();
zMyTicks = GCLK();
}
}
}

Hope this helps.
Andy
 
A

Andy

Keeping a seconds counter is out of the question since then
you're forced to increment the ticks at a frequency exactly
divisable by one second. Please see my previous reply to
Eric and maybe you will get a good idea what I'm trying to
accomplish. But the basic idea is to allow the ticks to
be incremented at any frequency because so often, timers
are hard to come by. I do not want to dedicate an entire
timer just for this.
The equation

unsigned long elapsedSeconds;

seconds = (float)elasedSeconds * 0.004;

will always yield a valid number for all 32-bits of
elapsedSeconds, right? I mean it won't give a number that's
hours, days, or years away from the actual value when
elapsedSeconds is greater than 24-bits, right?
If that's the case, then I think I'm happy with it.

Andy
 
A

Andy

I'm sorry, I was thinking of this equation

(float)(ticks / 250) + (float)(ticks % 250)/250.0

posted by another person when I wrote the reply. Please see my
reply to Eric to get an idea of what I'm trying to accomplish.

TIA
Andy
 
A

Andy

How about

float a,b,c;
assert (a > 1.0);
assert (a < pow(2,32)); /* full range (excluding 0) of unsigned long */
assert (b != 0); /* b is some small but representable non-zero value */
assert (b < 1.0);
c = a*b;
assert (c != 0);
assert (!isnan(c))

Please note float instead of double. And also, what kind of
error can I expect out the product of a*b?

TIA
Andy
 
E

Eric Sosman

Andy said:
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(GCLK_T ticks) {
return(GCLK() - ticks);
}

unsigned long ElapsedSecs(GCLK_T ticks) {
return((float)ElapsedTicks(ticks) * (float)(SECS_PER_TICK));
}

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

unsigned long ElapsedSecs(GCLC_T ticks) {
return ticks / TICKS_PER_SEC; // new constant
/* or, if you want rounding: */
return (ticks + TICKS_PER_SEC / 2) / TICKS_PER_SEC;
}
/* has a endless loop with one 100 millisecond task */
void main(void) {

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

Dan Pop

In said:
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.

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
 
E

Eric Sosman

Dan said:
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.

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(GCLK_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;
}
 
J

J. J. Farrell

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(GCLK_T ticks) {
return(GCLK() - ticks);
}

unsigned long ElapsedSecs(GCLK_T ticks) {
return((float)ElapsedTicks(ticks) * (float)(SECS_PER_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(zMyTicks) > MSECS_TO_TICKS(100)) {
Do100MillisecondTask();
zMyTicks = GCLK();
}
}
}

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.
 
D

Dik T. Winter

>
> 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.

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.
> 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(GCLK_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 {
/* the assumption here is: no wrap around... */
> /* Aw, shucks: Do it the hard way. With luck
> * this won't happen very often.
> */
> lastsecs = ticks / TICKS_PER_SEC;
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.
> loticks = lastsecs * TICKS_PER_SEC;
> hiticks = loticks + TICKS_PER_SEC;
> }

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;
 
A

Andy

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
 
D

Dan Pop

In said:
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.

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
 
A

Andy

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
 
E

Eric Sosman

Andy said:
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?

#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;
}
 
G

glen herrmannsfeldt

Andy said:
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?

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
474,125
Messages
2,570,748
Members
47,302
Latest member
MitziWragg

Latest Threads

Top