Logarithm Precision

[ghost]

Godot version: 3.1

OS/device including version: Windows 10

Issue description:
Precision issues with flooring a value produced by a logarithmic operation:
floor(log(1000)/log(10)) yields 2 as a result
int(log(1000)/log(10)) yields 2 as a result
In both cases, the expected result was 3 because log(1000)/log(10) yields 3 as a result

Steps to reproduce:
print(floor(log(1000)/log(10)))
print(int(log(1000)/log(10)))

Minimal reproduction project:

Logarithm Precision Issue.zip

[raymoo]

Is this really a precision issue? If the result is very close to but below 3 (think 2.9999999 or something), then printing it out might round it to 3, but flooring it will give you 2. I think what you would want to do in this situation is round the result, not floor it.

How are you determining what the result of log(1000)/log(10) is? If you're printing it out, it will get rounded.

[Meriipu]

I think it is a precision issue but it might be a floating point one in general not specific to godot?

I had to add a line checking for (almost?)-equality otherwise the rounding down would be one short.

func ....():
  var base: int = alphabet.length()
  if id == 0:
    return alphabet[0]
  var i: int = int(log(id)/log(base))
  #adjust for floating point errors in the line above
  if pow(base, i+1) <= id:
    i = i+1

[raymoo]

Why not just do

var i: int = int(round(log(id) / log(base)))

This isn't a Godot-specific issue, general-purpose logarithms are just implemented approximately. In Python, if I do math.log(1000, 10) (in python the default base is e unless you give it the optional second argument), it gives me the result 2.9999999999999996.

If you really need an exact way to calculate floor(log(x)), and it has to work for any input x (not just ones with clean integer exponents), then that would be a feature request because you can't do it with the current built-in log. It would be a different algorithm. If you only need to handle the case where the logarithm should output an integer value, you could just use the built-in log and round the result.

EDIT: You could implement an exact floor(log(x)) in GDScript, but that may be slow. You can perform integer division by 10 until the value is less than 10, and count how many divisions you performed.

EDIT2: Had an error in my code

[Meriipu]

Why not just do

var i: int = int(round(log(id) / log(base)))

because that would overestimate the number of significant digits needed to represent id in base (when the log is greater than 2.5 but less than 3, and round eagerly bumps it up to 3).

alphabet = "0123456789"
id = 857
base = len(alphabet)
i = int(round(log(id) / log(base)))
--> 3

while you only need 8*10^2 + 5*10^1 + 7*10^0, in other words the actual log is less than 3

it only becomes a problem (with floating point) when id is close to (if not exactly) 1000, because then the calculated log might still be 2.99999997 or something but the actual log is 3 (or higher).

You are probably right in that it is not a godot-specific issue though.

[raymoo]

I don't think your workaround is perfect though, because what if the real log is actually something like 2.9999999?

Anyway, if you need exact floor(log(x)/log(base)), you can use the algorithm I described in my previous post, just replace 10 with the actual base (assuming integer base).

[raymoo]

The bottom line is what you're doing would require log to have maximum possible precision, because the output of floor has thresholds where the output jumps. This is too expensive in the general case because log is implemented by an approximate iterative algorithm and you would need to run it more times to get that precision. Since it looks like you only need floored integer logarithm, you can use the algorithm I posted, which will run in log time.

[Meriipu]

I don't think your workaround is perfect though, because what if the real log is actually something like 2.9999999?

if the real log is 2.9999 which floors to 2, then 10^(2+1) > id (since by definition of the log, the log would be 3 if 10^3 = id) -- in that case, the +1 adjustment would not be applied

[raymoo]

Doesn't that also assume that exponentiation is computed exactly?

[akien-mga]

That's not a Godot issue indeed, it's just a normal floating point precision error. There are various strategies to work it around well documented on the Internet, but one which could work here is something like that:

const EPSILON = 0.00001
...
print(floor(log(x) / log(base) + EPSILON))

[raymoo]

That doesn't work for the same reason as rounding, that you might actually have a logarithm that's integer value minus epsilon.

[Meriipu]

Doesn't that also assume that exponentiation is computed exactly?

is exponentiation with integers (or integers converted to floats) ever not exact?

edit: well, assuming you are not going ridiculously high with your values that is.

[akien-mga]

That doesn't work for the same reason as rounding, that you might actually have a logarithm that's integer value minus epsilon.

It does work better than rounding, as rounding gives you wrong values for everything from 1.50001 to 1.99998, while flooring after adding an epsilon only means that your precision is as high as the epsilon. I took an epsilon of 0.00001 as a conservative value, but you can likely make it a tad smaller and still have decent results.

But you can't have more precision than what the epsilon accounts for with floating point, that's why it's an epsilon. You will have errors with floating point, that's in their definition.

If you want perfect math up to the n-th place, you need to use another approach without ever touching floating point numbers.

[raymoo]

is exponentiation with integers (or integers converted to floats) ever not exact?

In my testing with small numbers, no, but there's no guarantee that it will be exact so I wouldn't code based on that assumption. An integer can be too big to be represented exactly in floating point, but it seems like your code's use case wouldn't encounter big numbers like that(?)

It does work better than rounding, as rounding gives you wrong values for everything from 1.50001 to 1.99998, while flooring after adding an epsilon only means that your precision is as high as the epsilon.

That's true, but there is an exact solution for the case of integer operands and flooring the result (the one I posted earlier) that's not too bad asymptotically (but maybe would have painful overhead from implementation in GDScript).