Title: **Fixed-point arithmetic, and a use for it in timekeeping**

Post by:**odometer** on **May 25, 2012, 01:18 am**

Post by:

I suggest the creation of datatypes for handling fixed-point binary arithmetic. This would, I suppose, run much more efficiently than floating-point arithmetic, as well as freeing up a few more bits for the significand. Such datatypes could, I suppose, be used in many (maybe the majority) of places where we now use floating-point binary.

I have a serious application for this, mainly in timekeeping. I suggest keeping track of the current time as a nine-byte fixed-point number, with exactly five bytes on the "low" side of the radix point, thus:

00 00 00 00.00 00 00 00 00 (in hexadecimal notation)

Every 128 clock ticks, we update this number by simple addition.

Suppose, by way of example, our oscillator is exactly 16 000 000 hertz. Then, 128 ticks of our crystal would equal:

0.00 00 86 37 BD (hexadecimal, and rounded to 5 bytes) seconds

If our oscillator runs fast or slow, we just change this figure to compensate. If we have a temperature sensor, all we need is a lookup table, and presto! Instant Chronodot clone!

Again, assuming a 16 MHz oscillator, 128 ticks is about 8 microseconds. Maybe we want finer resolution than that. So, if we want to check the time between updates, we just take the number of "extra" ticks and add it directly to the 3rd byte to the right of the radix point. What we are doing is using 0.00 00 01 00 00 (hex) as an approximation for 0.00 00 01 0C 6F ... (hex), and though not perfect, we will be within half a microsecond of the correct figure. (Our oscillator need not be*exactly* 16 MHz for this approximation to be useful.)

When coming up with this timekeeping idea, I was thinking of a thread in which I had asked for ideas regarding binary-coded decimal arithmetic. One of the responses I got said, in effect, "Don't bother. Do all math in binary, and convert if you need decimal." I can see where this is coming from: the Arduino has no real support for decimal, or binary-coded decimal, arithmetic. So I thought: if decimal arithmetic is unsupported and therefore to be avoided, why then internally use milliseconds and microseconds, which are*decimal* divisions of a second? Better perhaps to just keep track of seconds, in straight binary, and then if milliseconds or microseconds are needed, then convert, just as is done to convert binary numbers to decimal for display.

I have a serious application for this, mainly in timekeeping. I suggest keeping track of the current time as a nine-byte fixed-point number, with exactly five bytes on the "low" side of the radix point, thus:

00 00 00 00.00 00 00 00 00 (in hexadecimal notation)

Every 128 clock ticks, we update this number by simple addition.

Suppose, by way of example, our oscillator is exactly 16 000 000 hertz. Then, 128 ticks of our crystal would equal:

0.00 00 86 37 BD (hexadecimal, and rounded to 5 bytes) seconds

If our oscillator runs fast or slow, we just change this figure to compensate. If we have a temperature sensor, all we need is a lookup table, and presto! Instant Chronodot clone!

Again, assuming a 16 MHz oscillator, 128 ticks is about 8 microseconds. Maybe we want finer resolution than that. So, if we want to check the time between updates, we just take the number of "extra" ticks and add it directly to the 3rd byte to the right of the radix point. What we are doing is using 0.00 00 01 00 00 (hex) as an approximation for 0.00 00 01 0C 6F ... (hex), and though not perfect, we will be within half a microsecond of the correct figure. (Our oscillator need not be

When coming up with this timekeeping idea, I was thinking of a thread in which I had asked for ideas regarding binary-coded decimal arithmetic. One of the responses I got said, in effect, "Don't bother. Do all math in binary, and convert if you need decimal." I can see where this is coming from: the Arduino has no real support for decimal, or binary-coded decimal, arithmetic. So I thought: if decimal arithmetic is unsupported and therefore to be avoided, why then internally use milliseconds and microseconds, which are

Title: **Re: Fixed-point arithmetic, and a use for it in timekeeping**

Post by:**nickgammon** on **May 25, 2012, 02:07 am**

Post by:

So I thought: if decimal arithmetic is unsupported and therefore to be avoided, why then internally use milliseconds and microseconds, which aredecimaldivisions of a second?

This is a small amount of tweaking of the clock in the millis() function, because the clock ticks every 1.024 mS, so it adjusts the number to give us "decimal" milliseconds.

But you can run Timer 1 or Timer 2 and count "straight" ticks if you want to.

Quote

Better perhaps to just keep track of seconds, in straight binary, and then if milliseconds or microseconds are needed, then convert, just as is done to convert binary numbers to decimal for display.

Yes but the conversion would result in a division wouldn't it? So that could potentially be slower than just tweaking the clock output on the fly.

Title: **Re: Fixed-point arithmetic, and a use for it in timekeeping**

Post by:**odometer** on **May 25, 2012, 02:55 am**

Post by:

Quote

This is a small amount of tweaking of the clock in the millis() function, because the clock ticks every 1.024 mS, so it adjusts the number to give us "decimal" milliseconds.

But you can run Timer 1 or Timer 2 and count "straight" ticks if you want to.

Count up to how many ticks? More than 2**32 ?

Quote

QuoteBetter perhaps to just keep track of seconds, in straight binary, and then if milliseconds or microseconds are needed, then convert, just as is done to convert binary numbers to decimal for display.

Yes but the conversion would result in a division wouldn't it? So that could potentially be slower than just tweaking the clock output on the fly.

No division, only multiplication. To convert fractional values between bases, you multiply.

Example: Convert 0.BA5E (hex) to decimal, to 4 decimal places.

Procedure: Begin by writing "0." (zero, then decimal point).

0xBA5E * 10 = 0x747AC. Copy initial digit "7" from result, then delete this digit.

0x47AC * 10 = 0x2CCB8. Copy initial digit "2" from result, then delete this digit.

0xCCB8 * 10 = 0x7FF30. Copy initial digit "7" from result, then delete this digit.

0xFF30 * 10 = 0x9F7E0. Copy initial digit "9" from result, then delete this digit.

Result: 0.BA5E (hex) = 0.7279 (decimal, to 4 digits, truncated)

If you want correct rounding, then examine the 0xF7E0 left at the end, note that it is greater than 0x8000, which tells us to round up.

Result: 0.BA5E (hex) = 0.7280 (decimal, to 4 digits, rounded)

Title: **Re: Fixed-point arithmetic, and a use for it in timekeeping**

Post by:**nickgammon** on **May 25, 2012, 03:03 am**

Post by:

Count up to how many ticks? More than 2**32 ?

As many as you want. Do what the millis() timer does. When the timer overflows, add 1 to an unsigned long. So the "current time" is the contents of that overflow counter, plus whatever the timer value currently is. If you want more than 2**32 have two unsigned longs, or a long long.

Title: **Re: Fixed-point arithmetic, and a use for it in timekeeping**

Post by:**odometer** on **May 25, 2012, 04:47 am**

Post by:

Count up to how many ticks? More than 2**32 ?

As many as you want. Do what the millis() timer does. When the timer overflows, add 1 to an unsigned long. So the "current time" is the contents of that overflow counter, plus whatever the timer value currently is. If you want more than 2**32 have two unsigned longs, or a long long.

So what happens after 2**64 ticks? Do I need a third counter?

What I don't understand is this: since the Arduino is an 8-bit machine anyway, what is so special about 16-bit and 32-bit integers, but not, for example, 24-bit, 40-bit, or 48-bit integers? Why are there byte, int, and long types, rather than int8, int16, int24, int32, int40, and so on?

http://www.catb.org/jargon/html/Z/Zero-One-Infinity-Rule.html (http://www.catb.org/jargon/html/Z/Zero-One-Infinity-Rule.html)

My method does not simply "count ticks, then convert for display". It keeps a 9-byte register. I don't suppose it matters much whether you use two longs and a byte, or an array of nine bytes, or an int72, or what. It counts ticks

This 9-byte register will go through the following sequence of values:

After 0 total ticks: 00 00 00 00.00 00 00 00 00

After 128 total ticks: 00 00 00 00.00 00 86 37 BD

After 256 total ticks: 00 00 00 00.00 01 0C 6F 7A

After 384 total ticks: 00 00 00 00.00 01 92 A7 37

After 512 total ticks: 00 00 00 00.00 02 18 DE F4

......

After 15999872 total ticks: 00 00 00 00.FF FF 79 BD 6B

After 16000000 total ticks: 00 00 00 00.FF FF FF F5 28

After 16000128 total ticks: 00 00 00 01.00 00 86 2C E5 (first full second)

......

After 68719476909499904 total ticks: FF FF FF FF.FF FF 9A E0 9C

After 68719476909500032 total ticks: 00 00 00 00.00 00 21 18 59 (overflow after about 136 years)

If 136 years isn't enough, use 10 bytes.

Title: **Re: Fixed-point arithmetic, and a use for it in timekeeping**

Post by:**nickgammon** on **May 25, 2012, 05:18 am**

Post by:

So what happens after 2**64 ticks? Do I need a third counter?

After 36558 years? Yeah, I suppose. I won't be around to care.

Quote

What I don't understand is this: since the Arduino is an 8-bit machine anyway, what is so special about 16-bit and 32-bit integers, but not, for example, 24-bit, 40-bit, or 48-bit integers? Why are there byte, int, and long types, rather than int8, int16, int24, int32, int40, and so on?

Good question. And really, things like the BigNumber library have arbitrary precision, so you can have a 100-digit number if you want to. Usually you don't need it.

I suppose it's C legacy stuff.

At the assembly level you can implement as many bits as you want. Remember you don't have a heap of RAM - mostly people are trying to keep variables as small as possible.

Title: **Re: Fixed-point arithmetic, and a use for it in timekeeping**

Post by:**odometer** on **May 25, 2012, 05:43 am**

Post by:

Quote

Quote

So what happens after 2**64 ticks? Do I need a third counter?

After 36558 years? Yeah, I suppose. I won't be around to care.

Whoops! I was confusing ticks with something else.

Quote

QuoteWhat I don't understand is this: since the Arduino is an 8-bit machine anyway, what is so special about 16-bit and 32-bit integers, but not, for example, 24-bit, 40-bit, or 48-bit integers? Why are there byte, int, and long types, rather than int8, int16, int24, int32, int40, and so on?

Good question. And really, things like the BigNumber library have arbitrary precision, so you can have a 100-digit number if you want to. Usually you don't need it.

I suppose it's C legacy stuff.

At the assembly level you can implement as many bits as you want. Remember you don't have a heap of RAM - mostly people are trying to keep variables as small as possible.

I think BigNumber is decimal, and therefore slow. If I remember correctly, it is also a memory hog: one byte per decimal digit.

As for my timekeeping idea, I really don't know a lot about assembly language, and I have a feeling that if I tried to use it myself, I would only foul things up. What I came up with in my original post was more or less an algorithm. I can only hope that some kind soul will implement it.

Title: **Re: Fixed-point arithmetic, and a use for it in timekeeping**

Post by:**robtillaart** on **May 26, 2012, 09:55 am**

Post by:

@odometer

Do you have a fixed point library allready?

if so do you have measured its performance?

and footprint?

Do you have a fixed point library allready?

if so do you have measured its performance?

and footprint?

Title: **Re: Fixed-point arithmetic, and a use for it in timekeeping**

Post by:**odometer** on **May 27, 2012, 02:43 am**

Post by:

@odometer

Do you have a fixed point library allready?

if so do you have measured its performance?

and footprint?

No, I have no fixed-point library.

I don't know much about C++, and I know even less about assembler, but I do know a thing or two about arithmetic, and I am thinking that whatever algorithms exist for integer arithmetic could be extended to fixed-point binary.

For example, if we wanted a 16-bit fixed point number, with 1 integer byte and 1 fractional byte, then:

- Comparison, addition, and subtraction work exactly as in 16-bit integer arithmetic.
- To multiply, treat the operands as 16-bit integers, convert each operand to a 32-bit integer (even a 24-bit integer format will do here), then multiply and keep the middle 16 bits of the product as the result.
- To divide, treat the operands as 16-bit integers, convert each operand to a 32-bit integer (even a 24-bit integer format will do here), then shift the dividend ("top" number of a fraction) leftwards 8 bits, then divide and keep the low 8 bits of the quotient as the result.

What I am suggesting is to have these as datatypes on the same low level as "int" and "long". The reason is, the Arduino is an 8-bit machine, so anything longer than 8 bits is not native to it anyway; why shouldn't some of these bits be fractional places?

Title: **Re: Fixed-point arithmetic, and a use for it in timekeeping**

Post by:**Coding Badly** on **May 27, 2012, 02:47 am**

Post by:

Before you (or anyone else) embarks on a development effort I strongly suggest spending some time with Google...

https://www.google.com/search?q=avr+fixed+point+math+library

Title: **Re: Fixed-point arithmetic, and a use for it in timekeeping**

Post by:**westfw** on **Jun 18, 2013, 10:53 pm**

Post by:

Nick Gammon has ported the gnu "bc" library to Arduino: www.gammon.com.au/forum/?id=11519

The Arduino runs C/C++, which is a Standardized language that defines certain data types. And it's a language that isn't specifically designed for 8bit CPUs, so the "8bit anyway" argument loses weight. Very recent versions of gcc support "fixed point" ("GNU C supports fixed-point types as defined in the N1169 draft of ISO/IEC DTR 18037.") But I think that only means adding an implicit decimal point to the existing integer types (up to 64bits), and I'm unsure of the status of AVR support for this in the form of libraries/etc. Also, Arduino doesn't currently use "very recent" versions of the compiler.

Unfortunately, it doesn't quite work that way. The meme that "floating point is slower than fixed point" assumes that the fixed point arithmetic is done in a native size using more-or-less single instructions. Since multiply and divide are already "not native" to AVR, the speed is more proportional to number of bits in the operands rather than "type", and a floating point divide is somewhat faster than a 32bit fixed point divide.

(floating point: subtract exponents, 24*mantissa bitwise divide loop, normalize. Fixed point: 32* bitwise divide loop.) Floating Addition and subtraction will incur additional overhead by being function calls rather than inline, and the "normalize" step becomes more significant, and the difference between 24 bits and 32bits add is much less (one byte vs 8 bits...)

Quote

since the Arduino is an 8-bit machine anyway, what is so special about 16-bit and 32-bit integers, but not, for example, 24-bit, 40-bit, or 48-bit integers?

The Arduino runs C/C++, which is a Standardized language that defines certain data types. And it's a language that isn't specifically designed for 8bit CPUs, so the "8bit anyway" argument loses weight. Very recent versions of gcc support "fixed point" ("GNU C supports fixed-point types as defined in the N1169 draft of ISO/IEC DTR 18037.") But I think that only means adding an implicit decimal point to the existing integer types (up to 64bits), and I'm unsure of the status of AVR support for this in the form of libraries/etc. Also, Arduino doesn't currently use "very recent" versions of the compiler.

Quote

This would, I suppose, run much more efficiently than floating-point arithmetic

Unfortunately, it doesn't quite work that way. The meme that "floating point is slower than fixed point" assumes that the fixed point arithmetic is done in a native size using more-or-less single instructions. Since multiply and divide are already "not native" to AVR, the speed is more proportional to number of bits in the operands rather than "type", and a floating point divide is somewhat faster than a 32bit fixed point divide.

(floating point: subtract exponents, 24*mantissa bitwise divide loop, normalize. Fixed point: 32* bitwise divide loop.) Floating Addition and subtraction will incur additional overhead by being function calls rather than inline, and the "normalize" step becomes more significant, and the difference between 24 bits and 32bits add is much less (one byte vs 8 bits...)