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

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.

odometer:
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?

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.

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.

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 ?

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.

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)

odometer:
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

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 up to 128 ticks, then adds a value to this 9-byte accumulator. It then starts counting ticks again, from 0. (Really, you can count ticks as high as you like, but we are only going to use the "low" 7 bits of that count, so a byte datatype will be more than sufficient.)

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.

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

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.

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.

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.

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.

@odometer
Do you have a fixed point library allready?
if so do you have measured its performance?
and footprint?

robtillaart:
@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?

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

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

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.

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, 24mantissa 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...)