Stream: ideas

Topic: FixedPoint number type

Martin Stewart (Jun 11 2022 at 13:04):

I'm betting a FixedPoint package will be created early on (either by me or someone else :smile: ). The reason for this is that fixed point has a number of advantages:

1. It has better performance than Dec
2. It doesn't have NaN, +infinity, -infinity problems that floating point has
3. It's guaranteed to be deterministic unlike floating point (unless the floating point is implemented in software in which case fixed point has better performance)

A drawback with fixed point though is that it doesn't have as large a range of representable values compared to floating point. Typically a fixed point number is represented with 64 bits. Some number of bits represent the integer part, 1 bit for the sign, and the rest represent the fractional part.

My question is, of those 63 bits (1 bit is used already for the sign), how much should be used for the integer part and how much should be used for the fractional part?

Some ideas:

1. 31 bits for the integer part and 32 for the fractional part. The advantage with this is, you can convert between FixedPoint and Int32 and back without any risk of an integer overflow (you'll only truncate the fractional part when converting to Int32). The drawback is that the largest representable value will only be a little over 2 billion (you can't represent the world population for example)
2. 34 bits for the integer part and 29 for the fractional part. The largest value is now over 17 billion. This seems like it will cover most use cases (though not all, you can't represent the annual budget of larger countries). And 29 fractional bits is enough to represent a nanometer if the units are in meters, which seems like enough precision for most uses case well. The drawback is that going from FixedPoint to Int32 risks overflow.
3. 46 integer bits, 17 fractional bits. Largest value is 70 trillion. Now we can do financial math! But 17 fractional bits might be too low precision for things like a physics engine. At a scale of 1 meter, the smallest representable unit would be 7 micrometers, which sounds decent, but the issue is that fixed point can lose a lot of precision if you multiply a big number with a small number followed by another big number (this is something that floating point avoids), so it's important to have extra precision to protect against that.

Anyone else have any thoughts on this?

Edit: There could of course be multiple FixedPoint types with different trade-offs between range and precision but I think it would be best if there's a single FixedPoint type so the user doesn't have to convert between different types all the time.

Richard Feldman (Jun 11 2022 at 15:46):

Dec is fixed point! :smiley:

Richard Feldman (Jun 11 2022 at 15:47):

it's 128-bit fixed point specifically

Martin Stewart (Jun 11 2022 at 17:12):

Dec is base 10 right? You are correct that it's fixed point, but I guess when I hear fixed point I assume base 2. My bad for the confusion :sweat_smile:

Richard Feldman (Jun 11 2022 at 17:12):

base 10 indeed!

Richard Feldman (Jun 11 2022 at 17:13):

the goal is to make it the default non-integer type, so if you put 0.1 + 0.2 into the repl, it evaluates it as a Dec and gives you 0.3

Martin Stewart (Jun 11 2022 at 17:15):

My use case is a number type that's fast enough to be suitable for physics engines but also deterministic so that it's suitable for peer to peer multiplayer games. I don't think Dec fits that use case? At least to me it seems like using 128 bits and working with base 10 will cause a significant performance loss (again, within the context of physics engines, its performance is probably fine for most applications).

Richard Feldman (Jun 11 2022 at 17:16):

ah, so I suppose base 2 would be faster

Richard Feldman (Jun 11 2022 at 17:16):

so as I understand it, floating point numbers can be that as long as you're using the same trigonometry functions

Richard Feldman (Jun 11 2022 at 17:17):

this is based on a conversation with Mason Remaley awhile back

Richard Feldman (Jun 11 2022 at 17:17):

my understanding is that IEEE-754 defines precisely enough how floating point operations ought to work that every CPU gives the same answer for the same hardware instructions

Richard Feldman (Jun 11 2022 at 17:18):

however, for some reason the trig functions (sin, cos, etc) are actually slower in hardware than when done in software with lookup tables

Richard Feldman (Jun 11 2022 at 17:18):

so it's normal to use userspace trig functions from libc, and sometimes those software implementations give different answers on different machines

Richard Feldman (Jun 11 2022 at 17:19):

if all of this is correct, then Roc could get deterministic floating-point operations across machines by not using the local libc, and rather providing our own software implementations for trig functions in the roc stdlib

Richard Feldman (Jun 11 2022 at 17:21):

I think that would be the absolute fastest, in the sense that I don't think even base-2 fixed point can be faster than floating point except maybe at addition, subtraction, multiplication, and division

Richard Feldman (Jun 11 2022 at 17:22):

since addition and subtraction can be hardware integer ops, which are generally faster than hardware floating point ops, and multiplication and division in base 2 can be bit shifts, which should be significantly faster than hardware floating point multiplication and division especially

Richard Feldman (Jun 11 2022 at 17:23):

that said, I don't know about fixed-point sqrt and trig

Richard Feldman (Jun 11 2022 at 17:24):

they certainly don't have hardware support, but if floating point wants to use lookup tables anyway, maybe you just do fixed-point lookup tables and end up getting equivalent performance anyway? I'm not sure!

Martin Stewart (Jun 11 2022 at 17:31):

My understanding about floating point determinism is largely based on this article https://randomascii.wordpress.com/2013/07/16/floating-point-determinism/. In the article the author mentions

Rounding, precision, exceptions, and denormal support – that’s a lot of [CPU] flags. If you do need to change any of these flags then be sure to restore them promptly. Luckily these settings should rarely be altered so just asserting once per frame that they are as expected (on all threads!) should be enough. There have been sordid situations where floating-point settings can be altered based on what printer you have installed and whether you have used it. If you find somebody who is altering your floating-point settings then it is very important to expose and shame them.

though I guess the platform can check if these CPU flags are consistent between platforms?

There's other things that get mentioned like (a + b) + c where some CPUs can store the a + b in a temporary register with higher precision before adding c which would lead to a different result. I admit I don't really understand the details on when this happens.

There's a lot of stuff in the article and maybe it can all be addressed but it does make me want to just write my own FixedPoint package to make sure that the results really are deterministic and a multiplayer game isn't going to desync with an extremely difficult to pin down bug.

Richard Feldman (Jun 11 2022 at 17:36):

yeah the platform can set those flags once and then not change them :thumbs_up:

Richard Feldman (Jun 11 2022 at 17:39):

that said, it should be possible to write your own fixedpoint type in pure Roc that has the same performance as if it were written in C/C++/Rust/etc

Richard Feldman (Jun 11 2022 at 17:40):

we expose all the hardware primitives with no overhead, e.g. Num.addWrap is just a single addition instruction

Martin Stewart (Jun 11 2022 at 17:40):

Richard Feldman said:

yeah the platform can set those flags once and then not change them :thumbs_up:

The article seems to say that those CPU flags can be changed at any point and as a result the platform would need to check on each thread, repeatedly while the program is running. Maybe that's overkill and printers aren't so badly programmed anymore but it does make me a little nervous.

Richard Feldman (Jun 11 2022 at 17:41):

well certainly the Roc compiler won't emit any instructions that change them, and the Roc stdlib doesn't change them either :big_smile:

Richard Feldman (Jun 11 2022 at 17:41):

so if they changed, it's because the platform ran some code that changed them

Martin Stewart (Jun 11 2022 at 17:42):

Maybe I'm just mistaken but it seems like device drivers (maybe other normal programs?) all share and modify the same floating point CPU flags? The article is 9 years old so maybe things have changed as well.

Richard Feldman (Jun 11 2022 at 17:50):

oh interesting - like if the OS is doing time slices and doesn't restore the flags after switching back to your process after running another one

Richard Feldman (Jun 11 2022 at 17:51):

now I understand what you mean about threads - not just your own code, but other processes' code too

Richard Feldman (Jun 11 2022 at 17:51):

yeah I guess that could happen!

Jared Cone (Aug 18 2022 at 04:57):

I work on an online multiplayer multiplatform physics game. Just wanted to concur that trying to get perfect float determinism on all platforms may theoretically be possible but would be a ton of work. We settle for close enough using quantization. I think a fast fixed-point math library would be fantastic.

Last updated: Jun 16 2026 at 16:19 UTC