4 ms·

Here is a naive question. A lot of effort goes into dealing with floating point imprecision and instabilities, right. So why aren’t these algorithms implemented

Here is a naive question. A lot of effort goes into dealing with floating point imprecision and instabilities, right. So why aren’t these algorithms implemented with integers? A 64 bit integer could represent the region from 0 to 1 with 2*64 evenly spaced slices, for example. Would that make things more accurate across operations? Is this something that is done?

moonchild 4y ago
That is called 'fixed point', and it is useful for some applications. What makes floating point interesting is that it can represent values with very different magnitudes; your 64-bit fixed point number can't represent any number greater than 1, for instance. Whereas a 32-bit float can represent numbers with magnitudes between ~2^-127 and ~2^127.
- psychphysic 4y ago
  Maybe Cosine could be fixed and converter to float before use. Using identities to calculate Sine and Tangent functions.
  - bigbillheck 4y ago
    Seems like a lot of effort for no actual gain.
    - psychphysic 4y ago
      Just an option if magnitude is an issue. You only needs 0-1 plus a sign bit. Fixed to float is easy enough. It'd let you use a fixed point implementation for 0 - pi/2 benefiting from smaller look up table and simpler implementation.
      - Someone 4y ago
        > It'd let you use a fixed point implementation for 0 - pi/2 benefiting from smaller look up table Why would that table be smaller if you use 2^64 values in that range instead of the fewer than 2^55 doubles in that range? > and simpler implementation. Why would it be simpler? With doubles, the hardware will do scaling for you. With fixed point, you need a helper function or macro to do multiplications, and those have to use an intermediate result with more than 64 bits (in this special case, some shortcuts are possible, but those won’t make the implementation simpler).
        psychphysic 4y ago
        One or both of us have lost the thread here. There was an exchange about using fixed point (which apparently is being used according to other comments for easier correctness verification, speed and simplicity). Someone pointed out that float gives you a wider range of values. But those values are not needed for cosine which has a range of 0-1 in the interval 0 to pi/2.
        dahart 4y ago
        > But those values are not needed for cosine which has a range of 0-1 in the interval 0 to pi/2 Ah not quite true though; the “range” is also referring to the exponent range of representable numbers, so don’t forget the small numbers near 0. You can get much smaller numbers with much higher precision out of a single-precision float than a fixed-point 64 bit [0,1] number.
        psychphysic 4y ago
        Ah makes sense. I imagine depending one how you intend to use the numbers you need that precision at the steeper parts too.
ChuckNorris89 4y ago
There should be plenty of C trigonometric algorithms made for fixed point. They usually use lookup tables and interpolation. Used a lot in embedded microcontrollers that don't have hardware floating point or hardware trig functions, and in automotive where floats were (still are?) a no-go due to the dangerous float math pitfalls and the safety critical nature of ECUs. I remember writing a fast, small footprint, but very accurate fixed point trig function for the microcontroller used in my batcher project, many lives ago. I'll try to find it and put it on github. The neat thing is that you can use the native overflow wrap around property enabled by C integers and processor registers to rotate back and fourth around the trigonometric circle without needing to account for the edge cases of the 0/360 degree point. You do need to suppress MISRA warning here though as it will go nuts seeing that.
- rtfeldman 4y ago
  I'd love to see some implementations of fixed point trig functions, but I haven't found any! Do you have any links by any chance?
  - Someone 4y ago
    I’d Google “forth trig functions” and get, for example https://web.stanford.edu/~dljaffe/SVFIG99/trig.html https://web.stanford.edu/~dljaffe/SVFIG99/trig.html https://www.hpmuseum.org/forum/thread-18123.html https://www.hpmuseum.org/forum/thread-18123.html (which links to https://archive.org/details/Forth_Dimension_Volume_04_Number_1/page/n8/mode/1up https://archive.org/details/Forth_Dimension_Volume_04_Number...)
    - rtfeldman 4y ago
      Nice, I didn't realize Forth used them - thank you!
  - ChuckNorris89 4y ago
    I don't have the code at hand to show you, nor do I have any links similar trig stuff as I wrote everything from scratch, first in Matlab to prover the concept, then in C, as there wasn't anything similar online at the time, but I used the principles of fixed point fractional math of representing floating point numbers as scaled integers in the Q notation, which is well documented for use in microcontrollers and DSPs of the era (early to late '00s) Here's the wiki gist with some C code snippet examples [1]. Here's a more detailed math paper that goes in the weeds[2]. Here's a nice presentation from Motorola-Freescale-NXP I just found which I wish I had back then as this is awesome and explains the basics for everyone to understand, and seeing those Motorola Windows 95 GUI tools brings a nostalgic smile on my face. [1] https://en.wikipedia.org/wiki/Q_(number_format) https://en.wikipedia.org/wiki/Q_(number_format) [2] http://darcy.rsgc.on.ca/ACES/ICE4M/FixedPoint/FixedPointRepresentationFractionalMath.pdf http://darcy.rsgc.on.ca/ACES/ICE4M/FixedPoint/FixedPointRepr... [3] https://www.nxp.com/files-static/training_presentation/TP_CONTROLLER_CONTINUUM_FP.pdf https://www.nxp.com/files-static/training_presentation/TP_CO...
syockit 4y ago
Speaking from no experience, but it should be doable. But since in most applications you're going to use floating point anyway (or, if you're using fixed point, maybe right bit shift or maybe even do integer division until it fits the range of your value), the extra precision would be discarded in the end.
dzdt 4y ago
Re: "imprecision and instabilities" on standard hardware there really are neither. Floating point numbers have an exact meaning (a particular fraction with an integer numerator and a denominator that is a power of 2). There are exactly specified rules for basic operations so that adding, subtracting, multiplying, or dividing these fractions will give you the nearest representable fraction to the exact result (assuming the most common round-to-nearest mode). The bit that appears as "imprecision and instabilities" is a mismatch between three things: (1) what the hardware provides (2) what controls or compiler optimisation settings the programming language exposes (3) what the user expects. There are several sticky points with this. One mentioned in the parent article is higher precision. Starting from the original 8087 floating point coprocessor x86 has supported both 80-bit and 64-bit floating point in hardware, but programming language support has mostly ignored this and only shows the user "double" precison with 64 bits of storage allocated. But with some compiler settings parts of the compuation would be done at 80 bit precision with no user visibility or control over which parts had that extra precision. Newer hardware modes stick to 64 bit computation so you're unlikely to run into that particular stickiness on a modern programming stack. There is another that comes up more now: fused multiply and add. Modern hardware can calculate round(a*x+b) in one step where a,x,b are floating point numbers (i.e. fractions) and the "round" operation produces the nearest representable fraction to the correct result. This is faster and more accurate to calculate than doing the multiplication and addition seperately, which gives round(round(a*x)+b) But again programming language control is weak over whether and when fused-multiply-and-add is used, and this is a detail that almost all programmers almost always just want to ignore anyway.
jcranmer 4y ago
What you're describing is fixed point. Fixed point absolutely exists in practice, but it has an important limitation: its accuracy is scale-dependent, unlike floating-point. Suppose for example you were doing a simulation of the solar system. What units do you use for coordinates--AUs, light-seconds, kilometers, meters, even miles? With floating-point, it doesn't matter: you get the same relative accuracy at the end. With fixed point, you get vastly different relative accuracy if your numbers are ~10¯⁶ versus ~10⁶.

moonchild 4y ago

That is called 'fixed point', and it is useful for some applications. What makes floating point interesting is that it can represent values with very different magnitudes; your 64-bit fixed point number can't represent any number greater than 1, for instance. Whereas a 32-bit float can represent numbers with magnitudes between ~2^-127 and ~2^127.

psychphysic 4y ago
Maybe Cosine could be fixed and converter to float before use. Using identities to calculate Sine and Tangent functions.
- bigbillheck 4y ago
  Seems like a lot of effort for no actual gain.
  - psychphysic 4y ago
    Just an option if magnitude is an issue. You only needs 0-1 plus a sign bit. Fixed to float is easy enough. It'd let you use a fixed point implementation for 0 - pi/2 benefiting from smaller look up table and simpler implementation.
    - Someone 4y ago
      > It'd let you use a fixed point implementation for 0 - pi/2 benefiting from smaller look up table Why would that table be smaller if you use 2^64 values in that range instead of the fewer than 2^55 doubles in that range? > and simpler implementation. Why would it be simpler? With doubles, the hardware will do scaling for you. With fixed point, you need a helper function or macro to do multiplications, and those have to use an intermediate result with more than 64 bits (in this special case, some shortcuts are possible, but those won’t make the implementation simpler).
      - psychphysic 4y ago
        One or both of us have lost the thread here. There was an exchange about using fixed point (which apparently is being used according to other comments for easier correctness verification, speed and simplicity). Someone pointed out that float gives you a wider range of values. But those values are not needed for cosine which has a range of 0-1 in the interval 0 to pi/2.
        dahart 4y ago
        > But those values are not needed for cosine which has a range of 0-1 in the interval 0 to pi/2 Ah not quite true though; the “range” is also referring to the exponent range of representable numbers, so don’t forget the small numbers near 0. You can get much smaller numbers with much higher precision out of a single-precision float than a fixed-point 64 bit [0,1] number.
        psychphysic 4y ago
        Ah makes sense. I imagine depending one how you intend to use the numbers you need that precision at the steeper parts too.

ChuckNorris89 4y ago

There should be plenty of C trigonometric algorithms made for fixed point. They usually use lookup tables and interpolation. Used a lot in embedded microcontrollers that don't have hardware floating point or hardware trig functions, and in automotive where floats were (still are?) a no-go due to the dangerous float math pitfalls and the safety critical nature of ECUs. I remember writing a fast, small footprint, but very accurate fixed point trig function for the microcontroller used in my batcher project, many lives ago. I'll try to find it and put it on github. The neat thing is that you can use the native overflow wrap around property enabled by C integers and processor registers to rotate back and fourth around the trigonometric circle without needing to account for the edge cases of the 0/360 degree point. You do need to suppress MISRA warning here though as it will go nuts seeing that.

rtfeldman 4y ago
I'd love to see some implementations of fixed point trig functions, but I haven't found any! Do you have any links by any chance?
- Someone 4y ago
  I’d Google “forth trig functions” and get, for example https://web.stanford.edu/~dljaffe/SVFIG99/trig.html https://web.stanford.edu/~dljaffe/SVFIG99/trig.html https://www.hpmuseum.org/forum/thread-18123.html https://www.hpmuseum.org/forum/thread-18123.html (which links to https://archive.org/details/Forth_Dimension_Volume_04_Number_1/page/n8/mode/1up https://archive.org/details/Forth_Dimension_Volume_04_Number...)
  - rtfeldman 4y ago
    Nice, I didn't realize Forth used them - thank you!
- ChuckNorris89 4y ago
  I don't have the code at hand to show you, nor do I have any links similar trig stuff as I wrote everything from scratch, first in Matlab to prover the concept, then in C, as there wasn't anything similar online at the time, but I used the principles of fixed point fractional math of representing floating point numbers as scaled integers in the Q notation, which is well documented for use in microcontrollers and DSPs of the era (early to late '00s) Here's the wiki gist with some C code snippet examples [1]. Here's a more detailed math paper that goes in the weeds[2]. Here's a nice presentation from Motorola-Freescale-NXP I just found which I wish I had back then as this is awesome and explains the basics for everyone to understand, and seeing those Motorola Windows 95 GUI tools brings a nostalgic smile on my face. [1] https://en.wikipedia.org/wiki/Q_(number_format) https://en.wikipedia.org/wiki/Q_(number_format) [2] http://darcy.rsgc.on.ca/ACES/ICE4M/FixedPoint/FixedPointRepresentationFractionalMath.pdf http://darcy.rsgc.on.ca/ACES/ICE4M/FixedPoint/FixedPointRepr... [3] https://www.nxp.com/files-static/training_presentation/TP_CONTROLLER_CONTINUUM_FP.pdf https://www.nxp.com/files-static/training_presentation/TP_CO...

syockit 4y ago

Speaking from no experience, but it should be doable. But since in most applications you're going to use floating point anyway (or, if you're using fixed point, maybe right bit shift or maybe even do integer division until it fits the range of your value), the extra precision would be discarded in the end.

dzdt 4y ago

Re: "imprecision and instabilities" on standard hardware there really are neither. Floating point numbers have an exact meaning (a particular fraction with an integer numerator and a denominator that is a power of 2). There are exactly specified rules for basic operations so that adding, subtracting, multiplying, or dividing these fractions will give you the nearest representable fraction to the exact result (assuming the most common round-to-nearest mode). The bit that appears as "imprecision and instabilities" is a mismatch between three things: (1) what the hardware provides (2) what controls or compiler optimisation settings the programming language exposes (3) what the user expects. There are several sticky points with this. One mentioned in the parent article is higher precision. Starting from the original 8087 floating point coprocessor x86 has supported both 80-bit and 64-bit floating point in hardware, but programming language support has mostly ignored this and only shows the user "double" precison with 64 bits of storage allocated. But with some compiler settings parts of the compuation would be done at 80 bit precision with no user visibility or control over which parts had that extra precision. Newer hardware modes stick to 64 bit computation so you're unlikely to run into that particular stickiness on a modern programming stack. There is another that comes up more now: fused multiply and add. Modern hardware can calculate round(a*x+b) in one step where a,x,b are floating point numbers (i.e. fractions) and the "round" operation produces the nearest representable fraction to the correct result. This is faster and more accurate to calculate than doing the multiplication and addition seperately, which gives round(round(a*x)+b) But again programming language control is weak over whether and when fused-multiply-and-add is used, and this is a detail that almost all programmers almost always just want to ignore anyway.

jcranmer 4y ago

What you're describing is fixed point. Fixed point absolutely exists in practice, but it has an important limitation: its accuracy is scale-dependent, unlike floating-point. Suppose for example you were doing a simulation of the solar system. What units do you use for coordinates--AUs, light-seconds, kilometers, meters, even miles? With floating-point, it doesn't matter: you get the same relative accuracy at the end. With fixed point, you get vastly different relative accuracy if your numbers are ~10¯⁶ versus ~10⁶.