7 ms·

Fixed Point Arithmetic

79 points by vha3 5y ago

TheNewAndy 5y ago
Don't use stdfix.h if you are doing this though. As soon as you need to change your headroom (even temporarily within an algorithm), it will be a pain. Just use the boring C90 types (possibly typedeffed to something else) and write the operators you need.
vha3 5y ago
Prepared as a lecture supplement for ECE 4760 (Digital System Design Using Microcontrollers) at Cornell.
- hausen 5y ago
  Nice explanation! May I suggest a tiny addition to the text? Fixed point (in decimal) is also useful to make sure 1 trillion dimes are 100 billion dollars instead of $99,999,997,952.
galangalalgol 5y ago
Fixed point was still normal instruction in mandatory classes when I was in school. It is a pity, but I feel like we stopped teaching it at some point.
anthk 5y ago
That would be easier with Forth :).
analognoise 5y ago
Fixed point is critical reading for a lot of FPGA work.
- Osiris 5y ago
  For those of us unfamiliar with FPGA work, can you elaborate?
  - tails4e 5y ago
    FPGAs let you define the structure of the hardware, and implementing fixed point is a lot simpler in terms of logic gages used and usually higher performance. You absolutely could use floating point, but the HW cost would be high, so most folks convert to fixed and use that. Then the question becomes how many bits, as you can have arbitrary width fixed point, so must choose at the design time depending on the application requirements.
zanethomas 5y ago
I used fixed-point for all the 3d code in The Virtual Reality Playhouse (1992). That was the last time I wrote any significant assembler code. Good times.
- zanethomas 5y ago
  By the way ... that was the first VR program one could run at home. I drove liquid crystal classes with the modem control lines. Switching left/right was synchronized to the monitor's vertical retrace. Even better times. :)
the__alchemist 5y ago
I'm using fixed point for real-time DSP on cortex-M. Faster than floating. Using the CMSIS-DSP Q31 functions, in particular. On Rust `i32`s.
- vha3 5y ago
  On the PIC32, fixed add is ~2 cycles and floating point is is ~60. And about a 2x increase for multiplies. On architectures with floating point hardware some of the advantage is lost, but it's fantastic for DSP on microcontrollers.
  - remram 5y ago
    Do you have numbers for x86? A web search didn't give me a clear answer, especially for non-vectorized code.
    - vha3 5y ago
      I don't unfortunately. I came up with those numbers by using the timers on the PIC32 to measure execution time, in case that's helpful. Or alternatively (and often more simply) by setting and clearing a GPIO pin before/after the operation being timed, and then using the oscilloscope to measure execution time
    - klodolph 5y ago
      There are half a million x86 microarchitectures. You can look up a particular microarchitecture in Agner Fog’s instruction tables (link below). There will be both throughput and latency values for different instructions (or something else, depending on microarchitecture). Keep in mind that x86 has both x87 and SSE floating-point, it sounds like what you want is the single precision, non-vectorized SSE instructions (like ADDSS). Also note that most microarchitectures are superscalar and may have multiple units capable of executing the instruction you are looking at. https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf
    - nwallin 5y ago
      In general, recent consumer x86 CPUs will be faster at floating point code than fixed point code. Floating point multiply is already faster than integer multiply; fixed point has the additional cost of the bitshift. (which is very small, but non-zero) Addition/subtraction are similar. Mid-range smartphones will generally have acceptable floating point units, and you should stick to floating point math. If you're targeting low end smartphones, you never know what you're going to get. Fixed point is generally only still useful on embedded. If you're building software for fixed point, it's generally because you know exactly what CPU your software is going to run on, and you know it doesn't have a FPU.
benhoyt 5y ago
I know fixed point was very important back in the days when CPUs didn't have dedicated floating point instructions. How important is it now, when most common CPUs have fast floating point operations? Is there still a performance win? Do games and similar software use them today?
- whateveracct 5y ago
  The main appeal of fixed point nowadays is determinism across hardware - so networked games benefit, for instance.
  - benhoyt 5y ago
    Interesting. Are IEEE-specified floating point operations not deterministic?
    - cmroanirgo 5y ago
      That's my question too. I wrote a multiplayer strategy game back in mid 90's issuing floating point and it was deterministic. No problems. Maybe chip optimizations have affected this? We looked at fixed point, but with careful scheduling we'd get zero fpu (x87) stalls for float operations, so it wasn't a real win to go fixed. And it gave us the benefit of having more registers to use without needing to use the main stack as much, which also made the asm easier to read. Edit: typos
      - anonymoushn 5y ago
        Your compiler or runtime might reorder operations, different machines might have DAZ and FTZ set differently, some CPUs might helpfully offer you a bunch of extra bits of precision while others do not
      - newpavlov 5y ago
        Achieving reliable reproducibility for floating point calculations is... difficult, to say the least. There are minor differences between hardware (x87 vs SSE is the most famous one, but there are others). Changing compiler, its version or options may produce subtly different results (the most obvious example is the -ffast-math flag). And even the bigger problem is implementation of non-primitive (e.g. trigonometric) functions. Usually your program will use implementation from a system or vendor library, which probably have different underlying implementations.
lifthrasiir 5y ago
> If you #include <stdfix.h>, you gain access to compiler-understood fixed-point data types. For example, you get access to type _Accum, which is a 16.15 fixed point exactly like the one that we've been considering above. You can actually use _Accum without including stdfix.h, at least for compilers that conform the embedded extension to C (ISO/IEC TR 18037 [1]). Stdfix.h just gives you a macro named `accum` among others; this approach has been used for any new C keyword since C99 (e.g. _Bool vs. stdbool.h, _Alignas vs. stdalign.h). The size of _Accum type is also not exactly defined (it can well be 4.27). [1] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf
TheNewAndy 5y ago
I used fixed point for my game's physics, because I wanted things to be deterministic across platforms and compilers (the game has a hidden "solver" which is used to tweak things a little bit to make the game more fun, but this involves rerunning simulations multiple times).
- TheNewAndy 5y ago
  I did need a sqrt, but I cared more about predictability than accuracy, so I just did an iterative algorithm (actually two - one for the integer part, and then a second one to get better precision)
- whateveracct 5y ago
  Did you use stdfix, another library, or just hand-roll it?
  - TheNewAndy 5y ago
    Handrolled. It looks like this: https://ideationapps.com/2020/12/09/making-two-birds-fixed-point/ https://ideationapps.com/2020/12/09/making-two-birds-fixed-p...
H8crilA 5y ago
Another advantage: the results of additions no longer depend on the operation order. Converting floats to such ints helped me remove nondeteminism from a large pipeline that did additions over large sets of numbers. It was annoying to trace diffs in the pipeline when we were making changes and wanted to see what the end results are.
juanuys 5y ago
Whenever I hear "fixed point arithmetic", it reminds me of the jittery graphics on PSX. Can't find a more official source than Reddit, but here goes: > It's because the position of each polygon's vertex (corner) is only calculated at a very low precision. Once the polygon moves (or the camera) the vertexes will stay at the same point, until they're closer to the next and suddenly "jump" to the new position without transition. Newer graphics hardware could interpolate smoothly here with more in-between states (that's where all the talk about "floating point precision" came from in graphics). 0. https://www.reddit.com/r/gaming/comments/bkedc/heres_a_question_why_do_3d_models_on_the_ps1_tend/ https://www.reddit.com/r/gaming/comments/bkedc/heres_a_quest...
- queezey 5y ago
  The “jitter” of PSX graphics is caused by a number of factors: https://retrocomputing.stackexchange.com/a/5021 https://retrocomputing.stackexchange.com/a/5021 Incidentally, the Nintendo 64 also used fixed point numbers in RDP graphics instructions, but did not exhibit the same visual artifacts as the PlayStation.

79 points by vha3 5y ago

Don't use stdfix.h if you are doing this though. As soon as you need to change your headroom (even temporarily within an algorithm), it will be a pain. Just use the boring C90 types (possibly typedeffed to something else) and write the operators you need.

vha3 5y ago

Prepared as a lecture supplement for ECE 4760 (Digital System Design Using Microcontrollers) at Cornell.

hausen 5y ago
Nice explanation! May I suggest a tiny addition to the text? Fixed point (in decimal) is also useful to make sure 1 trillion dimes are 100 billion dollars instead of $99,999,997,952.

galangalalgol 5y ago

Fixed point was still normal instruction in mandatory classes when I was in school. It is a pity, but I feel like we stopped teaching it at some point.

anthk 5y ago

That would be easier with Forth :).

analognoise 5y ago

Fixed point is critical reading for a lot of FPGA work.

Osiris 5y ago
For those of us unfamiliar with FPGA work, can you elaborate?
- tails4e 5y ago
  FPGAs let you define the structure of the hardware, and implementing fixed point is a lot simpler in terms of logic gages used and usually higher performance. You absolutely could use floating point, but the HW cost would be high, so most folks convert to fixed and use that. Then the question becomes how many bits, as you can have arbitrary width fixed point, so must choose at the design time depending on the application requirements.

zanethomas 5y ago

I used fixed-point for all the 3d code in The Virtual Reality Playhouse (1992). That was the last time I wrote any significant assembler code. Good times.

zanethomas 5y ago
By the way ... that was the first VR program one could run at home. I drove liquid crystal classes with the modem control lines. Switching left/right was synchronized to the monitor's vertical retrace. Even better times. :)

the__alchemist 5y ago

I'm using fixed point for real-time DSP on cortex-M. Faster than floating. Using the CMSIS-DSP Q31 functions, in particular. On Rust `i32`s.

vha3 5y ago
On the PIC32, fixed add is ~2 cycles and floating point is is ~60. And about a 2x increase for multiplies. On architectures with floating point hardware some of the advantage is lost, but it's fantastic for DSP on microcontrollers.
- remram 5y ago
  Do you have numbers for x86? A web search didn't give me a clear answer, especially for non-vectorized code.
  - vha3 5y ago
    I don't unfortunately. I came up with those numbers by using the timers on the PIC32 to measure execution time, in case that's helpful. Or alternatively (and often more simply) by setting and clearing a GPIO pin before/after the operation being timed, and then using the oscilloscope to measure execution time
  - klodolph 5y ago
    There are half a million x86 microarchitectures. You can look up a particular microarchitecture in Agner Fog’s instruction tables (link below). There will be both throughput and latency values for different instructions (or something else, depending on microarchitecture). Keep in mind that x86 has both x87 and SSE floating-point, it sounds like what you want is the single precision, non-vectorized SSE instructions (like ADDSS). Also note that most microarchitectures are superscalar and may have multiple units capable of executing the instruction you are looking at. https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf
  - nwallin 5y ago
    In general, recent consumer x86 CPUs will be faster at floating point code than fixed point code. Floating point multiply is already faster than integer multiply; fixed point has the additional cost of the bitshift. (which is very small, but non-zero) Addition/subtraction are similar. Mid-range smartphones will generally have acceptable floating point units, and you should stick to floating point math. If you're targeting low end smartphones, you never know what you're going to get. Fixed point is generally only still useful on embedded. If you're building software for fixed point, it's generally because you know exactly what CPU your software is going to run on, and you know it doesn't have a FPU.

benhoyt 5y ago

I know fixed point was very important back in the days when CPUs didn't have dedicated floating point instructions. How important is it now, when most common CPUs have fast floating point operations? Is there still a performance win? Do games and similar software use them today?

whateveracct 5y ago
The main appeal of fixed point nowadays is determinism across hardware - so networked games benefit, for instance.
- benhoyt 5y ago
  Interesting. Are IEEE-specified floating point operations not deterministic?
  - cmroanirgo 5y ago
    That's my question too. I wrote a multiplayer strategy game back in mid 90's issuing floating point and it was deterministic. No problems. Maybe chip optimizations have affected this? We looked at fixed point, but with careful scheduling we'd get zero fpu (x87) stalls for float operations, so it wasn't a real win to go fixed. And it gave us the benefit of having more registers to use without needing to use the main stack as much, which also made the asm easier to read. Edit: typos
    - anonymoushn 5y ago
      Your compiler or runtime might reorder operations, different machines might have DAZ and FTZ set differently, some CPUs might helpfully offer you a bunch of extra bits of precision while others do not
    - newpavlov 5y ago
      Achieving reliable reproducibility for floating point calculations is... difficult, to say the least. There are minor differences between hardware (x87 vs SSE is the most famous one, but there are others). Changing compiler, its version or options may produce subtly different results (the most obvious example is the -ffast-math flag). And even the bigger problem is implementation of non-primitive (e.g. trigonometric) functions. Usually your program will use implementation from a system or vendor library, which probably have different underlying implementations.

lifthrasiir 5y ago

> If you #include <stdfix.h>, you gain access to compiler-understood fixed-point data types. For example, you get access to type _Accum, which is a 16.15 fixed point exactly like the one that we've been considering above. You can actually use _Accum without including stdfix.h, at least for compilers that conform the embedded extension to C (ISO/IEC TR 18037 [1]). Stdfix.h just gives you a macro named `accum` among others; this approach has been used for any new C keyword since C99 (e.g. _Bool vs. stdbool.h, _Alignas vs. stdalign.h). The size of _Accum type is also not exactly defined (it can well be 4.27). [1] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf

TheNewAndy 5y ago

I used fixed point for my game's physics, because I wanted things to be deterministic across platforms and compilers (the game has a hidden "solver" which is used to tweak things a little bit to make the game more fun, but this involves rerunning simulations multiple times).

TheNewAndy 5y ago
I did need a sqrt, but I cared more about predictability than accuracy, so I just did an iterative algorithm (actually two - one for the integer part, and then a second one to get better precision)
whateveracct 5y ago
Did you use stdfix, another library, or just hand-roll it?
- TheNewAndy 5y ago
  Handrolled. It looks like this: https://ideationapps.com/2020/12/09/making-two-birds-fixed-point/ https://ideationapps.com/2020/12/09/making-two-birds-fixed-p...

H8crilA 5y ago

Another advantage: the results of additions no longer depend on the operation order. Converting floats to such ints helped me remove nondeteminism from a large pipeline that did additions over large sets of numbers. It was annoying to trace diffs in the pipeline when we were making changes and wanted to see what the end results are.

juanuys 5y ago

Whenever I hear "fixed point arithmetic", it reminds me of the jittery graphics on PSX. Can't find a more official source than Reddit, but here goes: > It's because the position of each polygon's vertex (corner) is only calculated at a very low precision. Once the polygon moves (or the camera) the vertexes will stay at the same point, until they're closer to the next and suddenly "jump" to the new position without transition. Newer graphics hardware could interpolate smoothly here with more in-between states (that's where all the talk about "floating point precision" came from in graphics). 0. https://www.reddit.com/r/gaming/comments/bkedc/heres_a_question_why_do_3d_models_on_the_ps1_tend/ https://www.reddit.com/r/gaming/comments/bkedc/heres_a_quest...

queezey 5y ago
The “jitter” of PSX graphics is caused by a number of factors: https://retrocomputing.stackexchange.com/a/5021 https://retrocomputing.stackexchange.com/a/5021 Incidentally, the Nintendo 64 also used fixed point numbers in RDP graphics instructions, but did not exhibit the same visual artifacts as the PlayStation.