Live data from Hacker News

Log is non-monotonic in PHP and Lua

purplesyringa.moe

51–58 of 58 posts

Re: Log is non-monotonic in PHP and Lua

#51
post #42

Earlier quoted context omitted.

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?

Ahem. Clearly my math knowledge failing me here. Apologies, and thanks for clearing it up :)

Re: Log is non-monotonic in PHP and Lua

#52
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

Citation needed. You only need LuaJIT if performance is very important, which is not the case for many scripting purposes. I personally use Lua 5.3.

Re: Log is non-monotonic in PHP and Lua

#53

> 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, _even array indexing_, because they have 53 bits of mantissa and they're guaranteed to represent all 32-bit integers with 100% precision.

Lua 5.3 introduced a proper integer type. However, JavaScript still represents all numbers as doubles!

Re: Log is non-monotonic in PHP and Lua

#54
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

Well, I use PICO-8 LUA. Where are my double-precision floats and 64bit integers at? XD

Re: Log is non-monotonic in PHP and Lua

#55
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…

I am curious what the correct algorithm would be, if for no other reason than to find out how on god's green earth it could be slower than using a division as an erstwhile shortcut. 8I

Re: Log is non-monotonic in PHP and Lua

#56

Earlier quoted context omitted.

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?

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 only advantage of the hyperbolic logarithm (a.k.a. natural logarithm) is that the multiplicative factor is unity when computing its derivative or primitive.

The binary logarithm can be computed faster and more accurately, except for arguments very close to 1.

It is a historical accident that most standard libraries have been defined in the past to include natural logarithms instead of binary logarithms. Moreover lazy implementers sometimes have written a binary logarithm function that uses a pre-existing hyperbolic logarithm function, instead of the direct implementation that would be much more efficient.

Derivatives and primitives are seldom computed, but the computational advantage of binary logarithms applies to each function evaluation.

Even when derivatives or primitives are computed, in almost all applications there already exists another multiplicative constant in the formula that must be computed, which can absorb in it the factor "ln 2", so there is no increased computational cost.

There exists absolutely no reason to ever use multiple bases with logarithms.

One can choose to always use only binary logarithms and there exists no problem that would need other kinds of logarithms.

Choosing a base for logarithms is equivalent with choosing a unit of measurement for them. Changing the base of logarithms is done by the same rules as changing the unit of measurement for any quantity. In the same way as there is no need to use multiple units of measurement for a quantity, there is no need to ever work with multiple bases for logarithms.

Thus there is no reason for a programming language to include a function with 2 arguments like "log(arg, base)" instead of having only a function with 1 argument, e.g. "log2" (and the 2 constants LN_2 and LOG2_E).

Re: Log is non-monotonic in PHP and Lua

#57
post #21

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.

In the past there were a lot of standard libraries that computed the transcendental functions with big errors.

Now there are several libraries that are guaranteed to produce correctly rounded results for any FP64 arguments.

However, the correct libraries are somewhat slower than the libraries that provide correct results for most, but not for all input arguments.

Re: Log is non-monotonic in PHP and Lua

#58
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…

I am curious what the correct algorithm would be, if for no other reason than to find out how on god's green earth it could be slower than using a division as an erstwhile shortcut. 8I

In this particular case, there never exists any need to compute a logarithm of an arbitrary base, so such a function must not exist in a library.

If someone had the weird idea to write some formula with logarithms in a random base they should convert that formula to use binary logarithms, because there is no advantage in using another base.

Nonetheless, if one would want to include such a function, or any other function, one could reduce the argument to some small range using mathematical properties of the function and then some polynomial approximation should be determined, in order to use it to compute the function values.

If you determine a polynomial approximation for a function, whichever function it is, you can compute the entire function faster and more accurately than when you compute the function as a composition of other functions, one or more of which are computed by their own polynomial approximations.

In order to ensure that the function is rounded correctly, one must determine how many polynomial terms are needed and how big must be the numbers used for storing the coefficients.

For a function with a single argument, like "log2", it is much easier to do an exhaustive search to find all the argument values that would need more polynomial terms or more bits in the coefficients, to guarantee correct rounding.

For functions with 2 arguments, it can be difficult or impossible to find all problematic argument pairs, unless the function has some special mathematical properties that would allow a formal proof about the accuracy needed in polynomial evaluation to ensure correct rounding.

Post reply on HN