JS Math.log() discrepancy

#1

This should not be problem at all but for the life of me I'm not able to put my finger on the heart of it.

I have a factory that spins out functions to determine the number of digits an integer will have. The factory is supplied a base, which is then scoped to the returned closure. The closure in turn accepts any integer and returns a digit count, mathematically.

Below are three different versions, floor, ceil and parseInt, followed by their output. Can anybody explain what is wrong with my logic? It's Thanksgiving and I think all the food has clouded my brain. Thanks in advance for your advice.

/*
function factory(base) {
    let log = Math.log;
    let floor = Math.floor;
    return x => { return floor(log(x) / log(base)) + 1;};
}
*/
/* floor
999 3
1000 3    // X
1001 4
255 8
256 9
4095 3
4096 4
*/

/*
function factory(base) {
    let log = Math.log;
    let ceil = Math.ceil;
    return x => { return ceil(log(x) / log(base));};
}
*/

/* ceil
999 3
1000 3    // X
1001 4
255 8
256 8     // X
257 9
4095 3
4096 3    // X
4097 4
*/

function factory(base) {
    let log = Math.log;
    return x => { return parseInt(log(x) / log(base), 10) + 1;};
}

/* int
999 3
1000 3    // X
1001 4
255 8
256 9
257 9
4095 3
4096 4
4097 4
*/

// tests

decDigCount = factory(10);

console.log(999, decDigCount(999));
console.log(1000, decDigCount(1000));
console.log(1001, decDigCount(1001));

binDigCount = factory(2);

console.log(255, binDigCount(255));
console.log(256, binDigCount(256));
console.log(257, binDigCount(257));

hexDigCount = factory(16);

console.log(4095, hexDigCount(4095));
console.log(4096, hexDigCount(4096));
console.log(4097, hexDigCount(4097));

Sandbox: https://repl.it/DsBi

#2

The mistake is in using floats when you need exact results

#3

So I should toss this method, then and just use a string character count?

#4

But then you would need to find a way to represent the value as a string in that base, that may not be possible for large bases.. unless you start using unicode or an array of ints or.. some such. And if you're doing that then you're already counting digits during that process

I'm not sure how integer division is (accurately) done is js. Multiplication should be fine though.

Division and truncation is.. probably fine, it'll either be an exact operation or be greater than the truncated result, and then just truncate it to get the integer result... maybe. I'd feel safer with multiplication without knowing more

#5

And so it is...

function factory(base) {
    let log = Math.log;
    return x => { return parseInt(log(x * base) / log(base), 10)};
}

999 3
1000 4
1001 4
255 8
256 9
257 9
4095 3
4096 4
4097 4

Same outcome with,

function factory(base) {
    let log = Math.log;
    let floor = Math.floor;
    return x => { return floor(log(x * base) / log(base))};
}

Thanks for your help, @ionatan.

#6

I think this method should fail for example for x = 100, x = 100000 and base = 10.

#7

I would like to start my post with two notes completely unrelated to the main problem. They will be probably much more valuable than rest of my post (sorry):

  1. parseInt(log(x) / log(base), 10) does exactly the same thing as return floor(log(x) / log(base)) as long as x and base are integers, but parseInt is much slower.
  2. it's better to usually define variables with the const keyword, let is required only if you want to change the value of a variable.

There is nothing wrong with your logic, you just need a more precise function. This is a well-known problem of the numerical methods. We have approximated value of log(x) and log(base) and then we divide them. Floating-point division of two approximated values intensifies the error.

The situation is different when the base is fixed. In this situation, we can create a more precise function based on Taylor series. And in many programming languages, this is done for the most popular bases.

Example (Python 2.7.10):

  math.log(1000, 10)
=> 2.9999999999999996
   math.log10(1000)
=> 3.0

Is this inconsistency? I would not say so. log10 is much slower and usually, we do not really need very precise numbers in the science.

There is also a log10 function in JavaScript. Short quote from the MDN:

This function is the equvalent of Math.log(x) / Math.log(10).

Fortunately, sometimes MDN is wrong. Let's take a look at language specification:

Math.log10(x) returns an implementation-dependent approximation to the base 10 logarithm of x.

Implementation-dependent, in most browsers Math.log10 will return more precise values. Example (Chrome):

   Math.log(1000) / Math.log(10)
=> 2.9999999999999996
   Math.log10(1000)
=> 3

So you can use log10, but if you want to cover all the possible bases and use this code in the web project (different browsers)... well, that's not really possible. But JavaScript has rather small (for scientific purposes) range for the safe calculations:

   Number.MAX_SAFE_INTEGER
=> 9007199254740991

So if you want to stay in this range it might be better to use a recurrence (ECMAScript 6 introduces tail call optimization).

#8

Right you are. Thank you for weighing in, @factoradic.

I was writing this to support another problem involving digits and went out on a limb to see if it could work with multiple bases so moved away from log10 for practice, but my real need is base 10 so will use log10 for that problem.

This will be something to dig into this week.

#9

You can use arbitrary bases, that's not related to the precision problem here, aside from perhaps if log10 has got "better" behaviour near the edge cases.. and then still being at the mercy of the js implementation you're using

That rules out using anything that doesn't produce an integer result, which very much includes the log functions.

One way to count digits is to count how many times you need to divide by the base until the value is less than 1. But division isn't exact so you may be required to start from the other end and count how many times 1 needs to be multiplied by the base to become greater than your value.

#10

This is what I've settled upon, for now...

const digits = x => {return Math.floor(Math.log10(x || 1) + 1)};

For my prpbem I may end up with a longhand approach that caches the digits in an array, the length of which will be the digit count, and the digits will be in isolation, which I need.

function num_split(x) {
    let r = [];
    while (x > 0) {
        r.unshift(x % 10);
        x = Math.floor(x / 10);
    }
    return r;
}

Proof of concept:

let result = [];
for (let i = 1; i <= 100; i++) {
    let r = 0;
    let n = num_split(i);
    for (let j = 0; j < n.length; j++){
        n[j] = Math.pow(n[j], j+1);
        r += n[j]
    }
    if (r === i) {
        result.push(r);
    }
}
console.log(result)

// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 89 ]