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.
Log is non-monotonic in PHP and Lua
21–30 of 58 posts
Re: Log is non-monotonic in PHP and Lua
#22Earlier quoted context omitted.
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 programm…
I simply assumed the tables in question were log tables. (No, not that kind of log.)
Re: Log is non-monotonic in PHP and Lua
#23> 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…
> The PlayStation 1 didn't have jiggly vertices and warpy textures because of fixed-point
Indeed modern GPUs still use fixed-point rasterizers.
Re: Log is non-monotonic in PHP and Lua
#24[dead]
Re: Log is non-monotonic in PHP and Lua
#25There's a widespread misconception (not shared by the article author) that floating point arithmetic is "imprecise" in the sense that the result is off by some amount of random noise. On the contrary, IEEE floating point results are precisely specified to produce the closest representable value to the mathematically exact result.
For efficiency reasons, library functions (and sometimes, sadly, hardware implementations) don't always guarantee this (closest representable) exact result. That's fine if the function is then called "approximate_inverse_square_root" or something. Sometimes being off by some epsilon is a good tradeoff for 10x efficiency. I'm unhappy when such a tradeoff is smuggled into my math library without warning.
I checked Rust's source code to confirm the article's claim that it doesn't have a precise log function, and indeed, here's the implementation:
pub fn log(self, base: f64) -> f64 {
self.ln() / base.ln()
}
Re: Log is non-monotonic in PHP and Lua
#26Earlier quoted context omitted.
"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 programm…
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 betw…
> because we now know the exact precision requirement for those functions over all 64-bit doubles
Do you have a link or something on this?
Re: Log is non-monotonic in PHP and Lua
#27> 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…
> Lua uses 64-bit double floats for everything
Not true in Lua >= 5.3. 64-bit signed integers are included in the number type now. And there is a math.ult function for treating them as unsigned.
And so 0x7fffffffffffffff is representable properly.
Re: Log is non-monotonic in PHP and Lua
#28I've tested this with both LuaJIT and Lua 5.5. It appears to only affect LuaJIT. Worth mentioning in the article I'd say.
Re: Log is non-monotonic in PHP and Lua
#29> 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…
> Lua uses 64-bit double floats for everything Not true in Lua >= 5.3. 64-bit signed integers are included in the number type now. And there is a math.ult function for treating them as unsigned. And so 0x7fffffffffffffff is representable properly.
this is true but basically everyone uses LuaJIT these days
Re: Log is non-monotonic in PHP and Lua
#30There's a widespread misconception (not shared by the article author) that floating point arithmetic is "imprecise" in the sense that the result is off by some amount of random noise. On the contrary, IEEE floating point results are precisely specified to produce the closest representable value to the mathematically exact result. For efficiency reasons, library functions (and sometimes, sadly, hardware implementation…
> On the contrary, IEEE floating point results are precisely specified to produce the closest representable value to the mathematically exact result.
Not sure about Rust, but C++ only guarantees that for four arithmetic operations and `sqrt`. Not `pow`, not `log`. Not even when when all inputs/outputs are integers. Sometimes you can even get `(int)pow(10, 2) == 99`, which I believe is fully standard-compliant.