Logarithm of a BigInt

user_9015596 0
Viewed 2735

Is there a way to get the logarithm of a BigInt in JavaScript?

With normal numbers, you would use this code:

const largeNumber = 1000;
const result = Math.log(largeNumber);

However, I need to work with factorial numbers, potentially higher than 170!, so the regular number type doesn't work. Math.log doesn't work with BigInt. So how do I get the logarithm?

const largeNumber = BigInt(1000);
const result = ???
bigint biginteger logarithm javascript
6 Answers

In case you don't want to return a BigInt, then the following might work for you too:

function log10(bigint) {
  if (bigint < 0) return NaN;
  const s = bigint.toString(10);

  return s.length + Math.log10("0." + s.substring(0, 15))
}

function log(bigint) {
  return log10(bigint) * Math.log(10);
}

function natlog(bigint) {
  if (bigint < 0) return NaN;

  const s = bigint.toString(16);
  const s15 = s.substring(0, 15);

  return Math.log(16) * (s.length - s15.length) + Math.log("0x" + s15);
}

const largeNumber = BigInt('9039845039485903949384755723427863486200719925474009384509283489374539477777093824750398247503894750384750238947502389475029384755555555555555555555555555555555555555554444444444444444444444444222222222222222222222255666666666666938475938475938475938408932475023847502384750923847502389475023987450238947509238475092384750923847502389457028394750293847509384570238497575938475938475938475938475555555555559843991');

console.log(natlog(largeNumber)); // 948.5641152531601
console.log(log10(largeNumber), log(largeNumber), log(-1))
// 411.95616098588766
// 948.5641152531603
// NaN

log10() will return a standard precision float for any BigInt or Int number you enter as an argument.

As @Mielipuoli quite rightly mentioned, the natural logarithm can be calculated as

function log(bigint) {
  return log10(bigint) / Math.log10(Math.E);
}

Or, even simpler, as shown in my snippet above, as log10(bigint) * Math.log(10).

@Nat already explained in a comment below, how this approach works, i.e. by calculating the integer and fractional parts of the logarithm separately and summing them up. With regards to the precision of the result: the Math.log10() works on a float number with its usual 13 to 14 decimal digits precision, and so, for a result, this is all you can expect too.

For this reason, I truncated the string representation of the BigInt number to 15 characters. Any further decimal places would have been ignored in the implicit type conversion to float anyway.

I also added the hex-string version here, suggested by @PeterCordes and further developed by @somebody as natlog(). It works - probably faster than my original solution - and produces the "same" result (only the very last shown digit deviates between the two results)!

user_26100610

The other answers have adequately addressed the question you give in the title, viz.: "how do I compute the logarithm of a BigInt?". However, you also mention that you are particularly interested in logarithms of factorials, for which a different algorithm avoids your range difficulties.

Applying log(ab) = log(a) + log(b), the following function computes the log of a factorial:

function logFactorial(n) {
  let total = 0;
  for (let current = 1; current <= n; ++current) {
    total += Math.log10(current);
  }

  return total;
}

console.log(logFactorial(170));

user_49261650

Inspired from MWO's answer, you could simply convert the BigInt into a string with the same base as the logarithm that you want to calculate and get the string length.

For example to calculate floor(log2(9007199254740991)) you can do BigInt("9007199254740991").toString(2).length - 1.

Note that toString only allows bases from 2 to 36.

user_17794770

Following up on my earlier comment, if one ever finds themselves seeking a really high precision logarithm, there are a couple of big decimal packages available that offer this capability. For example, the code snippet below makes use of decimal.js to a precision of 1000 digits in order to calculate...

  • 170! using BigInt to validate 170! when using decimal.js
  • 170! using decimal.js
  • ln( 170! )
  • log10( 170! )
  • exp( ln( 170! ) )
  • round( exp( ln( 170! ) ) )

<style>
textarea {
    width: 100%;
    height: 100vh;
}
</style>

<textarea id=result width:"100%" height:"100vh"></textarea>

<script src="https://cdnjs.cloudflare.com/ajax/libs/decimal.js/10.3.1/decimal.min.js"></script>

<script>

let result = document.getElementById( 'result' );

Decimal.precision = 1000;
Decimal.toExpPos = 1000;


b = BigInt( 1 );
d = new Decimal( 1 );
for ( let di = 2, bi = 2n; di <= 170; di++, bi++ ) {
  d = Decimal.mul( d, di );
  b = b * bi;
}

result.value = `BigInt 170! = ${b}\n\n`;
result.value += `decimal.js 170! = ${d.toString()}\n\n`;

result.value += `ln( 170! ) = ${Decimal.ln( d ).toString()}\n\n`;
result.value += `log10( 170! ) = ${Decimal.log10( d ).toString()}\n\n`;

result.value += `exp( ln ( 170! ) ) = ${Decimal.exp( Decimal.ln( d ) ).toString()}\n\n`;
result.value += `round( exp( ln ( 170! ) ) ) = ${Decimal.round( Decimal.exp( Decimal.ln( d ) ) ).toString()}\n\n`;
  
</script>

As an aside, amusingly, even at a 1000 digits, there are still rounding errors. Typically one will make the calculations with some addition precision by including a few more "hidden" decimal places, and then round back to the desired precision.

user_76961620

Could you check if this works for you? The function returns a BigInt.

function log10(bigint) {
    const n = bigint.toString(10).length;
    return bigint > 0n ? BigInt(n - 1) : null;
}

const largeNumber = BigInt('9039845039485903949384755723427863486200719925474009384509283489374539477777093824750398247503894750384750238947502389475029384755555555555555555555555555555555555555554444444444444444444444444222222222222222222222255666666666666938475938475938475938408932475023847502384750923847502389475023987450238947509238475092384750923847502389457028394750293847509384570238497575938475938475938475938475555555555559843991')

console.log(log10(largeNumber).toString())

For Log2 would be this respectively:

 const largeNumber = BigInt('9039845039485903949384755723427863486200719925474009384509283489374539477777093824750398247503894750384750238947502389475029384755555555555555555555555555555555555555554444444444444444444444444222222222222222222222255666666666666938475938475938475938408932475023847502384750923847502389475023987450238947509238475092384750923847502389457028394750293847509384570238497575938475938475938475938475555555555559843991')

    function log2(bigint) {
        const n = bigint.toString(2).length;
        return bigint > 0n ? BigInt(n - 1) : null;
    }
    
    console.log(log2(largeNumber).toString())

user_91750970

If it's purely in string form, for mine I just lazily do

- log()    here means natural-log ln()
- length() here means string length, sometimes called len()

- input bigint_str x

     ( length(x) * log(10) ) + log( "0." x )

Single liner, no loops, no recursion, no specialized bigint library - nothing.

Granted, it's precision is capped by IEEE 64-bit double precision FP, so its's accurate to 15 or so significant decimal digits.

Because one is prepending "0." in the 2nd half, that portion won't overflow or underflow unless your string is too long e.g. like more than 500k digits etc

If that's the case, trim it down to first 300 digits or so - that's way more than sufficient, since, by and large, it's dominated by the left side term describing order of magnitude, with right side only performing minor accuracy adjustments

user_146721140
Related