Do you mean fixed point using integers, or actually decimal (base-10)? My gut would be to use fixed-point integers with a power of two in the denominator.
On the other hand, I’m not sure if modern compilers even bother converting division/multiplications by powers of two to shifts these days, so maybe it isn’t worth it…
Compilers will convert mul/div to shifts, if they notice one of the operands is a power of 2. I would have included a link to an example on compiler explorer (https://godbolt.org/) but the source editor didn't work on my Pinephone for some reason..
Ah, interesting, I’m playing around with it on godbolt and it is doing all the sort of obvious stuff you might expect (division by 2 implemented as a shift, multiplication by 2 or 3 represented as adds, etc). You are right.
For some reason this was in my head as one of those “surprisingly, optimizing compilers might skip it” situations (like loop unrolling). Dunno where I picked that up.
Fair that relying on decimal is an interesting choice. My gut is that it would help with a lot of reasoning for folks.
This comes up all of the time with stuff like lat/lng values. People are convinced you have to use doubles because of the inaccuracy of floats. Completely skipping over the fact that you could have fixed point accuracy to 6 decimal digits with the same number of bits as a float. You just reduce your max/min value that you can represent. Which, for lat/lng, you are already heavily bounded.
I think it is fair to argue that basic libraries don't support trig on common fixed point sizes. But that is ultimately my lament. Floats are amazing for what they need to do. For what many people need, though, it feels overkill because it is overkill.
> This comes up all of the time with stuff like lat/lng values. People are convinced you have to use doubles because of the inaccuracy of floats.
Using any floating point representation for lat/long makes no sense at all to me. Floating point is designed for representing values where expected error scales with magnitude, not for values where error is constant with magnitude; the latter requires fixed point. I truly don't understand why someone would optimize their position representation for maximum accuracy off the coast of Africa, instead of having it uniform across the world.
Depends how you measure. The choice of floating point lat/long is very favorable for people in the area of Null Island, and while the population there nearly zero, the population density is either NaN or infinite, depending on how you handle your divide-by-zeros. I can certainly see optimizing your implementation for an infinite-population-density-area region...
This depends entirely on the sizes needed. For a surprising number of things people would use fixed point for, I would be surprised if you couldn't get good speed with surprisingly little effort.
If you don't have to do trig, I'd be surprised if you aren't faster by default, oddly. Indeed, if you are just adding and subtracting, it is just a number. If you are doing multiplication, it is a multiply and shift. So long as you don't try and support massive numbers of different fixed sizes, that shift is almost certainly still cheaper than float hardware. (Indeed, a lot of multiplications wouldn't even need the shift...)
Again, I do not mean this as a criticism of floats. For simulations and for numbers where you do have to support completely arbitrary values, there is a reason floats are a thing.
An integer add, sub, or shift is 1 cycle of latency; integer mul is generally 3 cycles; integer div is lol-that-is-slow. Floating-point adds, subs, muls, and fmas are generally 4 cycles, with div being lol-that-is-slow (but generally faster than integer division because your divisor and dividend have fewer bits).
So fixed-point addition and subtraction are definitely faster, multiplication is a wash if you're doing binary-based fixed point (but slower if you're doing decimal-based fixed point), and fixed-point division is definitely slower than floating-point division.
Kudos on providing the numbers. I wasn't confident in the numbers that I remembered and with how pipelined everything is, I didn't know how much to lean on them. Not exactly my standard workflow to care about this level of speed.
My gut would still be that it is typically a wash for most everyone as far as speeds go? If default libraries supported it more directly, I would think it would largely be a win for a lot of reasoning. In particular, silly stuff like 1e32 + 1e1 would not be nearly as surprising to most people. And the entire class of bugs around stuff like doing something until it reaches 0.9 would almost certainly go away if we guaranteed precision to a set number decimal places.
Alas, default libraries do not support this, though. So the above is admittedly wishful thinking on my end. And I could as easily describe a world where people insist on arbitrary numbers of fixed point values and how that would be its own set of landmines.
Do you mean fixed point using integers, or actually decimal (base-10)? My gut would be to use fixed-point integers with a power of two in the denominator.
On the other hand, I’m not sure if modern compilers even bother converting division/multiplications by powers of two to shifts these days, so maybe it isn’t worth it…
Compilers will convert mul/div to shifts, if they notice one of the operands is a power of 2. I would have included a link to an example on compiler explorer (https://godbolt.org/) but the source editor didn't work on my Pinephone for some reason..
Ah, interesting, I’m playing around with it on godbolt and it is doing all the sort of obvious stuff you might expect (division by 2 implemented as a shift, multiplication by 2 or 3 represented as adds, etc). You are right.
For some reason this was in my head as one of those “surprisingly, optimizing compilers might skip it” situations (like loop unrolling). Dunno where I picked that up.
Fair that relying on decimal is an interesting choice. My gut is that it would help with a lot of reasoning for folks.
This comes up all of the time with stuff like lat/lng values. People are convinced you have to use doubles because of the inaccuracy of floats. Completely skipping over the fact that you could have fixed point accuracy to 6 decimal digits with the same number of bits as a float. You just reduce your max/min value that you can represent. Which, for lat/lng, you are already heavily bounded.
I think it is fair to argue that basic libraries don't support trig on common fixed point sizes. But that is ultimately my lament. Floats are amazing for what they need to do. For what many people need, though, it feels overkill because it is overkill.
> This comes up all of the time with stuff like lat/lng values. People are convinced you have to use doubles because of the inaccuracy of floats.
Using any floating point representation for lat/long makes no sense at all to me. Floating point is designed for representing values where expected error scales with magnitude, not for values where error is constant with magnitude; the latter requires fixed point. I truly don't understand why someone would optimize their position representation for maximum accuracy off the coast of Africa, instead of having it uniform across the world.
Agreed. But I'm assuming we are in the minority on this one? Bad assumption?
Depends how you measure. The choice of floating point lat/long is very favorable for people in the area of Null Island, and while the population there nearly zero, the population density is either NaN or infinite, depending on how you handle your divide-by-zeros. I can certainly see optimizing your implementation for an infinite-population-density-area region...
Speed wise no hardware can do it though.
This depends entirely on the sizes needed. For a surprising number of things people would use fixed point for, I would be surprised if you couldn't get good speed with surprisingly little effort.
I would be surprised if you could get even one third of performance of floats. So why bother?
If you don't have to do trig, I'd be surprised if you aren't faster by default, oddly. Indeed, if you are just adding and subtracting, it is just a number. If you are doing multiplication, it is a multiply and shift. So long as you don't try and support massive numbers of different fixed sizes, that shift is almost certainly still cheaper than float hardware. (Indeed, a lot of multiplications wouldn't even need the shift...)
Again, I do not mean this as a criticism of floats. For simulations and for numbers where you do have to support completely arbitrary values, there is a reason floats are a thing.
An integer add, sub, or shift is 1 cycle of latency; integer mul is generally 3 cycles; integer div is lol-that-is-slow. Floating-point adds, subs, muls, and fmas are generally 4 cycles, with div being lol-that-is-slow (but generally faster than integer division because your divisor and dividend have fewer bits).
So fixed-point addition and subtraction are definitely faster, multiplication is a wash if you're doing binary-based fixed point (but slower if you're doing decimal-based fixed point), and fixed-point division is definitely slower than floating-point division.
Kudos on providing the numbers. I wasn't confident in the numbers that I remembered and with how pipelined everything is, I didn't know how much to lean on them. Not exactly my standard workflow to care about this level of speed.
My gut would still be that it is typically a wash for most everyone as far as speeds go? If default libraries supported it more directly, I would think it would largely be a win for a lot of reasoning. In particular, silly stuff like 1e32 + 1e1 would not be nearly as surprising to most people. And the entire class of bugs around stuff like doing something until it reaches 0.9 would almost certainly go away if we guaranteed precision to a set number decimal places.
Alas, default libraries do not support this, though. So the above is admittedly wishful thinking on my end. And I could as easily describe a world where people insist on arbitrary numbers of fixed point values and how that would be its own set of landmines.