> Everyone already knows floating-point operations are imprecise and it wouldn’t be fun to blog about.
Wellll... Yes and no. And I want to nitpick "FP ops are imprecise" because it's important sometimes.
It does come up in Lua - Lua uses 64-bit double floats for everything, _even array indexing_, because they have 53 bits of mantissa and they're guaranteed to represent all 32-bit integers with 100% precision.
I just opened Lua and got `2 ^ 32 == 4294967296.0` and `2 ^ 32 + 1 == 4294967297.0`. You can store 4 billion things in a Lua table and access them with double float indexes.
The usual "0.1 + 0.2 != 0.3" is _not_ imprecision. You could dedicate 1,000 bits to a float and still find some example of a number that's trivial to represent in decimal but repeats forever in binary.
While I'm on it, fixed-point and floating-point aren't magically different. Floats work better on very big values. Fixed-points are more predictable but run out of range easily when squaring numbers. This comes in 3D math when finding the length of vectors or normalizing vectors.
The PlayStation 1 didn't have jiggly vertices and warpy textures because of fixed-point. It had jiggly vertices because its GPU didn't have subpixel-precise rendering, and it only had 16 bits of precision. It had warpy textures because it had affine texture mapping. The N64's GPU had more bits of precision and it had perspective-correct texture mapping. There's no 16-bit floating-point format that would have saved the PS1 from wobbling.
Also floats aren't the cause of T-junctions or "sparklies" that are common in 3D game levels. That will happen in any system with finite precision, and if fixed-point would fix it, we'd use fixed-point.
I have the impression that creating monotonic floating point function is particularly hard. At least I know that std::lerp is designed to be monotonic in its t parameter (not even in a or b) and its implementation has a number of branches. Although it has other guarantees as well, so I don't know how much of the implementation complexity can be assigned to the monotonicity requirement.
Recently I was reading an article on the EML operator (exp-min-log) that uses exponentiation and logarithm to build elementary math functions including arithmetic operations. There was a table of results from testing across languages.
Language Result of 2 x 3 Error
---
Node.js v25.3.0 6.000000000000000 0
Python 3.9.6 6.000000000000001 8.88e-16
PHP 8.5.1 6.000000000000001 8.88e-16
Go 1.26.2 6.000000000000000 0
Rust 6.000000000000001 8.88e-16
It was speculated that this miniscule margin of error, 1 ULP (unit in the last place), is likely due to the difference in how log() is implemented by the language. Supposedly Python, PHP, and Rust use LLVM's libm (C math library) but maybe Go and Node.js internally compile to CPU instructions directly? There was no evidence presented, so I was skeptical of this explanation.
Python, PHP, and Rust do indeed use libm. Not LLVM's libm specifically, though, but rather just about anything they can find in runtime, and those libraries can have suboptimal accuracy.
Node uses V8, which notably implements a ton of math manually, because it needs the results to be deterministic across devices. It seemingly uses LLVM's libm, which IIRC promises 0.5 ulp for most operations. (https://github.com/v8/v8/blob/f24c62fbc342d616032734b714116e...)
Go avoids dynamic linking, so they also have their own implementation. (https://github.com/golang/go/blob/543ead71a8e7acc2bd6f326327...) They only promise 1 ulp, but I guess in this specific case it works out better than approximations used by the default libm on their system by pure chance?
Nice, thanks for tracking down those links, fascinating. Apparently being off by 1 ULP is within IEEE 754 floating-point spec, and "effectively negligible".
Correctly rounding transcendental functions is very difficult because of something called the table maker's dilemma, so the standard didn't want to impose a potentially extreme performance cost if they didn't have to.
Correctly rounded single precision functions at a reasonable cost are much easier these days. LLVM 18+ implements them, but the gnu libraries have been slower to improve.
This is the best source I could find, funny enough the author doesn't explain the name "table maker".
I suppose it's from the parable of a table maker who finds that one leg is too long, so they sand down that leg, only to find that another leg is too long, so they sand that down... slowly sanding away all the legs.
As a simple programmer I don't understand the dilemma. I do understand that sin, tan, sqrt, etc., take one argument, so you can guarantee a certain precision for them, at least in 32-bit floats, whereas a log in arbitrary base has two inputs, so its input space is huge and it's hard to guarantee anything, especially for 64-bit doubles.
If someone could write up a good explanation that could be its own HN post
The dilemma is hypothetical (because we now know the exact precision requirement for those functions over all 64-bit doubles) but let's assume that we don't know that and also we happen to use decimals instead. What if, some f(x) is known to be, say, 123.4999...9997 with 1,000 fractional digits? You have to calculate at least 1,000 decimal digits of f(x) in order to correctly round, before that we only know it's between 123.4999...999 and 123.5000...001. There seems no mathematical theory that specially prevents this annoying possibility, hence the dilemma.
> the author doesn't explain the name "table maker".
I suppose that parable fits, but also there is the dilema of someone making a table of (results) of transcendental functions. In the before times, most people got their sines and cosines and logs and what not by looking them up in tables. And someone has to make those tables. The example given where rounding to some specific number of digits depends on how many digits you calculate to is deeply unsatisfying, especially if you wanted to make a table for other people to use to lookup the results of functions.
Yeah, I simplified it a little. Though I must say I'm surprised pretty much every library I looked at uses the natural logarithm specifically, and not log2, which would seemingly be easier to compute with floats. Does anyone here know why, by any chance?
You can change base with a single multiplication by special constants if you accept 1ULP error, so working in one or the other doesn't really gain you much. But exp/logs are often implemented as a combination of a table lookup and polys, so you can just bake it into the constants even more easily.
Not sure why they wouldn't use log2 internally, but the mathematical reason is that e^x is the function whose derivative is itself, so it and the natural logarithm are fundamental to lots of other theories/operations like Euler's formula.
The log base is a parameter, not a function, so that doesn't typecheck. Multivariate monotonicity isn't really a popular term, as far as I'm aware, so I'm not aware of good terminology for this. Maybe "log is non-monotonic with respect to the base"?
> Everyone already knows floating-point operations are imprecise and it wouldn’t be fun to blog about.
Wellll... Yes and no. And I want to nitpick "FP ops are imprecise" because it's important sometimes.
It does come up in Lua - Lua uses 64-bit double floats for everything, _even array indexing_, because they have 53 bits of mantissa and they're guaranteed to represent all 32-bit integers with 100% precision.
I just opened Lua and got `2 ^ 32 == 4294967296.0` and `2 ^ 32 + 1 == 4294967297.0`. You can store 4 billion things in a Lua table and access them with double float indexes.
The usual "0.1 + 0.2 != 0.3" is _not_ imprecision. You could dedicate 1,000 bits to a float and still find some example of a number that's trivial to represent in decimal but repeats forever in binary.
While I'm on it, fixed-point and floating-point aren't magically different. Floats work better on very big values. Fixed-points are more predictable but run out of range easily when squaring numbers. This comes in 3D math when finding the length of vectors or normalizing vectors.
The PlayStation 1 didn't have jiggly vertices and warpy textures because of fixed-point. It had jiggly vertices because its GPU didn't have subpixel-precise rendering, and it only had 16 bits of precision. It had warpy textures because it had affine texture mapping. The N64's GPU had more bits of precision and it had perspective-correct texture mapping. There's no 16-bit floating-point format that would have saved the PS1 from wobbling.
Also floats aren't the cause of T-junctions or "sparklies" that are common in 3D game levels. That will happen in any system with finite precision, and if fixed-point would fix it, we'd use fixed-point.
I have the impression that creating monotonic floating point function is particularly hard. At least I know that std::lerp is designed to be monotonic in its t parameter (not even in a or b) and its implementation has a number of branches. Although it has other guarantees as well, so I don't know how much of the implementation complexity can be assigned to the monotonicity requirement.
Recently I was reading an article on the EML operator (exp-min-log) that uses exponentiation and logarithm to build elementary math functions including arithmetic operations. There was a table of results from testing across languages.
It was speculated that this miniscule margin of error, 1 ULP (unit in the last place), is likely due to the difference in how log() is implemented by the language. Supposedly Python, PHP, and Rust use LLVM's libm (C math library) but maybe Go and Node.js internally compile to CPU instructions directly? There was no evidence presented, so I was skeptical of this explanation.Python, PHP, and Rust do indeed use libm. Not LLVM's libm specifically, though, but rather just about anything they can find in runtime, and those libraries can have suboptimal accuracy.
Node uses V8, which notably implements a ton of math manually, because it needs the results to be deterministic across devices. It seemingly uses LLVM's libm, which IIRC promises 0.5 ulp for most operations. (https://github.com/v8/v8/blob/f24c62fbc342d616032734b714116e...)
Go avoids dynamic linking, so they also have their own implementation. (https://github.com/golang/go/blob/543ead71a8e7acc2bd6f326327...) They only promise 1 ulp, but I guess in this specific case it works out better than approximations used by the default libm on their system by pure chance?
Nice, thanks for tracking down those links, fascinating. Apparently being off by 1 ULP is within IEEE 754 floating-point spec, and "effectively negligible".
Correctly rounding transcendental functions is very difficult because of something called the table maker's dilemma, so the standard didn't want to impose a potentially extreme performance cost if they didn't have to.
Correctly rounded single precision functions at a reasonable cost are much easier these days. LLVM 18+ implements them, but the gnu libraries have been slower to improve.
"The Table-Maker's Dilemma"
https://people.eecs.berkeley.edu/~wkahan/LOG10HAF.TXT
This is the best source I could find, funny enough the author doesn't explain the name "table maker".
I suppose it's from the parable of a table maker who finds that one leg is too long, so they sand down that leg, only to find that another leg is too long, so they sand that down... slowly sanding away all the legs.
As a simple programmer I don't understand the dilemma. I do understand that sin, tan, sqrt, etc., take one argument, so you can guarantee a certain precision for them, at least in 32-bit floats, whereas a log in arbitrary base has two inputs, so its input space is huge and it's hard to guarantee anything, especially for 64-bit doubles.
If someone could write up a good explanation that could be its own HN post
The dilemma is hypothetical (because we now know the exact precision requirement for those functions over all 64-bit doubles) but let's assume that we don't know that and also we happen to use decimals instead. What if, some f(x) is known to be, say, 123.4999...9997 with 1,000 fractional digits? You have to calculate at least 1,000 decimal digits of f(x) in order to correctly round, before that we only know it's between 123.4999...999 and 123.5000...001. There seems no mathematical theory that specially prevents this annoying possibility, hence the dilemma.
> the author doesn't explain the name "table maker".
I suppose that parable fits, but also there is the dilema of someone making a table of (results) of transcendental functions. In the before times, most people got their sines and cosines and logs and what not by looking them up in tables. And someone has to make those tables. The example given where rounding to some specific number of digits depends on how many digits you calculate to is deeply unsatisfying, especially if you wanted to make a table for other people to use to lookup the results of functions.
My assumption is it's referring to mathematical tables and the historical makers of them. https://en.wikipedia.org/wiki/Mathematical_table
I find it interesting the blog author tied PHP and Lua together. PHP uses a JIT from Lua. Is this related to the log issue?
> PHP uses a JIT from Lua.
Wow, TIL! I was certain this is a mistake, but apparently PHP uses DynAsm (https://wiki.php.net/rfc/jit), which was developed for LuaJIT (https://luajit.org/dynasm.html). Cool stuff!
To answer your question, probably not. I dated the PHP change that added this "optimization" back to 2014 (https://github.com/php/php-src/commit/b547e1358d3846fad4cd0c...), while DynAsm only started being used around 2019 (https://wiki.php.net/rfc/jit). I think this is just convergent evolution.
(I'm putting "optimization" in quotes because it changes semantics.)
Yeah, I simplified it a little. Though I must say I'm surprised pretty much every library I looked at uses the natural logarithm specifically, and not log2, which would seemingly be easier to compute with floats. Does anyone here know why, by any chance?
You can change base with a single multiplication by special constants if you accept 1ULP error, so working in one or the other doesn't really gain you much. But exp/logs are often implemented as a combination of a table lookup and polys, so you can just bake it into the constants even more easily.
Not sure why they wouldn't use log2 internally, but the mathematical reason is that e^x is the function whose derivative is itself, so it and the natural logarithm are fundamental to lots of other theories/operations like Euler's formula.
I was prepared to read how its console logging function could reorder writes so that
could result in or something, which would've been no less surprising.Good find, but I'm curious if anyone is ever sweeping the base of the logarithm in real life.
Wouldn't a more applicable title be that the log base is non-monotonic?
The log base is a parameter, not a function, so that doesn't typecheck. Multivariate monotonicity isn't really a popular term, as far as I'm aware, so I'm not aware of good terminology for this. Maybe "log is non-monotonic with respect to the base"?