Hacker News Reader

Comment by bee_rider | Hacker News Reader

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…

View on HN

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

Funny, though I think the main measure most people actually pay attention to is how complicated your code is to do the distance functions.

I've almost never seen a real complexity difference between floating point and fixed point math in a language that supports fixed point either natively or through operator overloading. Yeah, scaling sometimes changes across an operation; but that's the type system's job, it's not actual complexity. And the error analysis is almost always much simpler for the fixed point implementation than the floating point implementation; and anyone writing code doing numeric approximations in any representation without considering numeric stability and doing the error analysis probably isn't worth running software from.

I am a little confused. My assertion is that most languages don't offer fixed point trig functions. Am I wrong on that assertion?

If you have the trig functions already implemented for the fixed point you are doing, what you are saying makes perfect sense to me. But I swear I get challenged on that point every time it comes up, as nobody has a fixed point trig library. (Well, that seems to be the assertion.)

Fixed-point CORDIC is not hard… but a trivial implementation will be slower than a hardware float implementation, true. Several of the micros I work on have a CORDIC accelerator on a (usually only one) low-latency core designed for BLDC control etc, but that’s neither universal, nor general, of course.

geodesics on ellipsoids of revolution are no small task.

which is why you should just use GeographicLib (or proj, now that it incorporates the same geodesic routines).

You can have floats with bounded absolute error, and floats are a universal standard that makes all the projection calculations much easier. Speaking of projections, the error between lat/long coordinates and the physical surface of the earth they correspond to is also non-uniform. Looks like you can get a bit under 1m resolution with absolute error in single precision if I did the math right.

> People are convinced you have to use doubles because of the inaccuracy of floats

With single-precision floats, considering the worst case, i.e. longitudes close to the equator but far away from the prime meridian, one ulp can translate into as much as 1.68 m (5.5 ft) of distance on the surface (*). That's good enough for some uses, but not for dGPS or any other serious geometric computation. Whereas, with double precision, one ulp in this worst case scenario corresponds to about 3 nanometers. It's overkill, for sure, but if these are the only two types you have, you pick the latter.

* = To represent the integer 179, you need 8 bits, leaving only 16 for the fraction. Since 1 degree of longitude near the equator is about 110 km, you have 1/2^16 degrees * 110 km/degree giving 0.0016784... km.

Right. My point is that I wish more people would reach instead for a fixed point lat/lng library. It would almost certainly be easier to reason with for most people. Similar for most people doing financial math should probably use something other than IEEE floats.

And again, IEEE numbers are amazingly well done for what they are. Which is largely the digital version of scientific notation that is using base-2.

It's quite difficult to find fixed-point number systems that include trigonometry, never mind fancier tools like elliptic integrals. The problem is not just one of static number representations, but also geodetic/geometric computations. [ed: I see this is where the other thread is heading already]

> I think it is fair to argue that basic libraries don't support trig on common fixed point sizes.

Its not that hard to roll your own support for fixed point trig. CORDIC is your friend. Easy to understand and easy to implement. Plus you can easily customize it for whatever custom fixed point size you want to work with.

Back in the day I implemented fixed point SIN / COS / TAN / ATAN routines on an 8 bit micro. Angle was represented as 8.8 fixed point, with 256.0 = 360 degrees. Made it nice when adding and subtracting angle values, as 360 degrees would overflow back to zero degrees. SIN/COS values, being between 0.0 and 1.0, were stored as 0.16 bit fixed point, so FFFFh = 0.9998 (approx 1.0). Used it for embedded magnetometer and gyro applications. Worked great and was reasonably fast considering it was an 8 bit micro.

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.

I think the trick is to make sure the compiler knows you are doing the math with a constant and such? They likely won't branch on arbitrary numbers to sometimes do it as a shift and other times do the multiplication. But compilers for a long time would propagate constants through and pick a faster option for basic a*2.

Reply on news.ycombinator.com