Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Log is non-monotonic in PHP and Lua

purplesyringa.moe

Post reply on HN
Print view View original

41–50 of 58 posts

Re: Log is non-monotonic in PHP and Lua

#41

Post by purplesyringa »

eternauta3k wrote: post #19

Good find, but I'm curious if anyone is ever sweeping the base of the logarithm in real life.

I sort of needed to do that. I needed to compress data with an approximately geometric distribution, and as part of that process I needed to invert its CDF, which is `CDF = 1 - (1 - p)^x`. That translates to `x = log_(1 - p) (1 - CDF)`, which is variable over both the argument and the base. At that point I wondered how consistent the implementation of double-argument `log` is, since the encoder and the decoder need to agree about it, which led to this article.

Re: Log is non-monotonic in PHP and Lua

#42

Post by Ennea »

purplesyringa wrote: post #38
Ennea wrote: post #28

I've tested this with both LuaJIT and Lua 5.5. It appears to only affect LuaJIT. Worth mentioning in the article I'd say.

That's interesting! On my PC it reproduces under Lua 5.5 (`log_a x > log_b x`), but not under LuaJIT (`log_a x = log_b x`). I took a look at LuaJIT's implementation ( https://github.com/LuaJIT/LuaJIT/blob/faaf663340347a78b22ed9... ) and noticed that it always uses the `ln x / ln a` formula -- or, rather, `log_2 x / log_2 a`, which is just as correct I guess. Have you perhaps misinterpreted the results? (I do think it…

Hm, perhaps, but I am confused now. In the article, you're comparing log_a x log_b x in your comment. To make it clear, I am running this code: https://bpa.st/ZCKA

Which prints, for LuaJIT: true true false

And for Lua 5.5: true false false

Re: Log is non-monotonic in PHP and Lua

#43

Post by inigyou »

lexicality wrote: post #29
mjmas wrote: post #27

Earlier quoted context omitted.

> 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

Pinned several language versions ago? No they don't.

Re: Log is non-monotonic in PHP and Lua

#44

Post by inigyou »

kaathewise wrote: post #35
yeputons wrote: post #30

Earlier quoted context omitted.

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

Yeah, those operations (+fma) are the only ones for which IEEE 754 mandates correct rounding. Calculating correct rounding for other functions without hardware support is both challenging to implement and is often really slow. And that's before one gets into special functions. Or, even worse, inverses of special functions. Sometimes you might be lucky when those don't over/underflow around the edges of the domain

It's still challenging to implement with hardware support but you don't notice because it challenges Intel instead of you. There is a reason that no instruction set since x87 implements transcendentals - and x87 did them in microcode.

Re: Log is non-monotonic in PHP and Lua

#46

Post by SkiFire13 »

ReactiveJelly wrote: post #16

> 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 usual "0.1 + 0.2 != 0.3" is _not_ imprecision.

It _is_ imprecision. Even if you cannot represent 0.3 exactly, you can consider the closest representable number, and that is different than the sum of the closest numbers to 0.1 and 0.2 because doing all of this introduced imprecision.

Re: Log is non-monotonic in PHP and Lua

#47

Post by kaathewise »

inigyou wrote: post #44
kaathewise wrote: post #35

Earlier quoted context omitted.

Yeah, those operations (+fma) are the only ones for which IEEE 754 mandates correct rounding. Calculating correct rounding for other functions without hardware support is both challenging to implement and is often really slow. And that's before one gets into special functions. Or, even worse, inverses of special functions. Sometimes you might be lucky when those don't over/underflow around the edges of the domain

It's still challenging to implement with hardware support but you don't notice because it challenges Intel instead of you. There is a reason that no instruction set since x87 implements transcendentals - and x87 did them in microcode.

True!

Older numerical libraries such as cephes had to work with heterogeneous non-IEEE floating point implementations: you can still see remnants of VAX tests in the docs, for example. That, too, must've been quite a struggle

Re: Log is non-monotonic in PHP and Lua

#48

Post by kaathewise »

purplesyringa wrote: post #36
codeflo wrote: post #25

There'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…

Thank you! This point has been driving me mad for the last couple of years. While answering a sibling comment, I found a paper analyzing various libms for their precision: https://homepages.loria.fr/pzimmermann/papers/glibc238-20230... (2023). I only skimmed it, but it looks like only LLVM's libm guarantees 0.5 ulp for every supported single-precision operation, and everyone else is wildly off. That's a pretty good r…

Table--Maker's dilemma [0] says that we probably can't get correct rounding for some functions. That said, you can still calculate every function within 1 ULP by using extended precision (for example the double-double arithmetic, which uses two doubles to represent a single fp number) and rounding.

But I don't think anyone does this in practice. Simulations don't need perfect precision, anything involving real data has to deal with measurement errors which are usually much larger than f64 ULP scales, and then there's configurable arbitrary-precision for when it's really needed.

[0]: https://people.eecs.berkeley.edu/~wkahan/LOG10HAF.TXT, which coincidentally is also about the log function

Re: Log is non-monotonic in PHP and Lua

#49

Post by purplesyringa »

Ennea wrote: post #42
purplesyringa wrote: post #38

Earlier quoted context omitted.

That's interesting! On my PC it reproduces under Lua 5.5 (`log_a x > log_b x`), but not under LuaJIT (`log_a x = log_b x`). I took a look at LuaJIT's implementation ( https://github.com/LuaJIT/LuaJIT/blob/faaf663340347a78b22ed9... ) and noticed that it always uses the `ln x / ln a` formula -- or, rather, `log_2 x / log_2 a`, which is just as correct I guess. Have you perhaps misinterpreted the results? (I do think it…

Hm, perhaps, but I am confused now. In the article, you're comparing log_a x log_b x in your comment. To make it clear, I am running this code: https://bpa.st/ZCKA Which prints, for LuaJIT: true true false And for Lua 5.5: true false false

`log_a x The topic of the post is that in PHP and Lua (without LuaJIT), sometimes this inequality doesn't hold, and instead we get `log_a x > log_b x`, which is very incorrect and cannot be explained away by rounding.

Does that make more sense?

Re: Log is non-monotonic in PHP and Lua

#50

Post by purplesyringa »

SkiFire13 wrote: post #46
ReactiveJelly wrote: post #16

> 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 usual "0.1 + 0.2 != 0.3" is _not_ imprecision. It _is_ imprecision. Even if you cannot represent 0.3 exactly, you can consider the closest representable number, and that is different than the sum of the closest numbers to 0.1 and 0.2 because doing all of this introduced imprecision.

To expand on this, the imprecision arises the moment you write 0.1 (decimal) in source code and the compiler converts it to binary; the arithmetic itself is (mostly) exact. So as long as you use numbers that look "good enough" in base-2, floats behave very reasonably. The constantly made assumption that floats are imprecise is, in this sense, a user error -- the user shouldn't have used decimals.
Post reply on HN