Fixed Point Arithmetic • Hacker News Board

Re: Fixed Point Arithmetic

#11

Post by tails4e » Mon, Oct 18, 2021, 1:04 AM UTC

Osiris wrote: post #6

analognoise wrote: post #5

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

For those of us unfamiliar with FPGA work, can you elaborate?

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.

Re: Fixed Point Arithmetic

#12

Post by remram » Mon, Oct 18, 2021, 1:05 AM UTC

vha3 wrote: post #10

the__alchemist wrote: post #8

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.

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.

Do you have numbers for x86? A web search didn't give me a clear answer, especially for non-vectorized code.

Re: Fixed Point Arithmetic

#13

Post by vha3 » Mon, Oct 18, 2021, 1:15 AM UTC

remram wrote: post #12

vha3 wrote: post #10

Earlier quoted context omitted.

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.

Do you have numbers for x86? A web search didn't give me a clear answer, especially for non-vectorized code.

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

Re: Fixed Point Arithmetic

#14

Post by klodolph » Mon, Oct 18, 2021, 1:16 AM UTC

remram wrote: post #12

vha3 wrote: post #10

Earlier quoted context omitted.

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.

Do you have numbers for x86? A web search didn't give me a clear answer, especially for non-vectorized code.

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

Re: Fixed Point Arithmetic

#15

Post by hausen » Mon, Oct 18, 2021, 1:26 AM UTC

vha3 wrote: post #2

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

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.

Re: Fixed Point Arithmetic

#16

Post by benhoyt » Mon, Oct 18, 2021, 1:34 AM UTC

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?

Re: Fixed Point Arithmetic

#17

Post by lifthrasiir » Mon, Oct 18, 2021, 1:49 AM UTC

> If you #include , 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

Re: Fixed Point Arithmetic

#18

Post by TheNewAndy » Mon, Oct 18, 2021, 1:58 AM UTC

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

Re: Fixed Point Arithmetic

#19

Post by TheNewAndy » Mon, Oct 18, 2021, 2:00 AM UTC

TheNewAndy wrote: post #18

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

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)

Re: Fixed Point Arithmetic

#20

Post by TheNewAndy » Mon, Oct 18, 2021, 2:06 AM UTC

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.