Offline
Full Member
Karma: 2
Posts: 196


« on: May 24, 2012, 06:18:46 pm » 
I suggest the creation of datatypes for handling fixedpoint binary arithmetic. This would, I suppose, run much more efficiently than floatingpoint 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 floatingpoint binary.
I have a serious application for this, mainly in timekeeping. I suggest keeping track of the current time as a ninebyte fixedpoint 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 binarycoded 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 binarycoded 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.


« Last Edit: May 24, 2012, 06:21:04 pm by odometer »

Logged





Global Moderator
Offline
Brattain Member
Karma: 452
Posts: 18694


« Reply #1 on: May 24, 2012, 07:07:49 pm » 
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.



Logged





Offline
Full Member
Karma: 2
Posts: 196


« Reply #2 on: May 24, 2012, 07:55:01 pm » 
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)



Logged





Global Moderator
Offline
Brattain Member
Karma: 452
Posts: 18694


« Reply #3 on: May 24, 2012, 08:03:40 pm » 
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.



Logged





Offline
Full Member
Karma: 2
Posts: 196


« Reply #4 on: May 24, 2012, 09:47:36 pm » 
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 8bit machine anyway, what is so special about 16bit and 32bit integers, but not, for example, 24bit, 40bit, or 48bit 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/ZeroOneInfinityRule.htmlMy method does not simply "count ticks, then convert for display". It keeps a 9byte 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 9byte 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 9byte 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.



Logged





Global Moderator
Offline
Brattain Member
Karma: 452
Posts: 18694


« Reply #5 on: May 24, 2012, 10:18:28 pm » 
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 8bit machine anyway, what is so special about 16bit and 32bit integers, but not, for example, 24bit, 40bit, or 48bit 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 100digit 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.



Logged





Offline
Full Member
Karma: 2
Posts: 196


« Reply #6 on: May 24, 2012, 10:43:51 pm » 
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 8bit machine anyway, what is so special about 16bit and 32bit integers, but not, for example, 24bit, 40bit, or 48bit 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 100digit 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.



Logged





Global Moderator
Netherlands
Offline
Shannon Member
Karma: 170
Posts: 12465
In theory there is no difference between theory and practice, however in practice there are many...


« Reply #7 on: May 26, 2012, 02:55:58 am » 
@odometer Do you have a fixed point library allready? if so do you have measured its performance? and footprint?



Logged





Offline
Full Member
Karma: 2
Posts: 196


« Reply #8 on: May 26, 2012, 07:43:05 pm » 
@odometer Do you have a fixed point library allready? if so do you have measured its performance? and footprint?
No, I have no fixedpoint 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 fixedpoint binary. For example, if we wanted a 16bit fixed point number, with 1 integer byte and 1 fractional byte, then:  Comparison, addition, and subtraction work exactly as in 16bit integer arithmetic.
 To multiply, treat the operands as 16bit integers, convert each operand to a 32bit integer (even a 24bit 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 16bit integers, convert each operand to a 32bit integer (even a 24bit 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 8bit machine, so anything longer than 8 bits is not native to it anyway; why shouldn't some of these bits be fractional places?



Logged






Offline
Edison Member
Karma: 11
Posts: 1489


« Reply #10 on: June 17, 2013, 07:34:54 am » 
I am working on 64,128,1024 bit fixed point math designed for DSP that has not FPU or any softfloat



Logged





SF Bay Area (USA)
Offline
Tesla Member
Karma: 106
Posts: 6373
Strongly opinionated, but not official!


« Reply #11 on: June 18, 2013, 03:53:04 pm » 
Nick Gammon has ported the gnu "bc" library to Arduino: www.gammon.com.au/forum/?id=11519since the Arduino is an 8bit machine anyway, what is so special about 16bit and 32bit integers, but not, for example, 24bit, 40bit, or 48bit 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 fixedpoint 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 floatingpoint 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 moreorless 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...)



Logged





