BigInt的对数

39

在 JavaScript 中,是否有一种方法可以获取 BigInt 的对数?

对于普通的数字,您可以使用以下代码:

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

但是,我需要处理可能高于170!的阶乘数,因此常规数字类型不起作用。Math.log无法与BigInt一起使用。那么我该如何获得对数?

然而,我需要处理阶乘数,有可能会比170!更大,因此普通的数字类型无法胜任。由于Math.log无法与BigInt一起使用,因此我该如何获取对数?

const largeNumber = BigInt(1000);
const result = ???

2
你可能需要自己计算。 - evolutionxbox
10
你想要哪种对数? - Nina Scholz
3
你期望返回哪种数据类型作为返回值?你能否编辑你的问题并给出所寻找的函数的规格说明,包括输入和预期输出的(极端)示例? - trincot
8
你认为 OP 在这里感到困惑的原因是什么?对一个大整数取对数似乎是一个非常合理的问题。 - idmean
2
对于那些需要计算大整数的高精度对数的人,另一个简单的选择是利用 decimal.js,网址为 https://github.com/MikeMcl/decimal.js ... - Trentium
显示剩余8条评论
6个回答

33

如果您不想返回一个BigInt,那么以下内容可能也适用于您:

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()将为您输入的任何BigInt或Int数字作为参数返回标准精度浮点数。


正如@Mielipuoli所提到的,自然对数可以计算为

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

或者更简单地说,就像我上面展示的那样,使用 log10(bigint) * Math.log(10)

@Nat 在下面的评论中已经解释了这种方法的工作原理,即通过分别计算对数的整数部分和小数部分并将它们相加来实现。关于结果的精度: Math.log10() 使用一个浮点数进行计算,其通常具有 13 到 14 位十进制数字的精度,因此,你所期望的结果也只有这些。

因此,我将 BigInt 数字的字符串表示截断为 15 个字符。任何更多的小数位在隐式类型转换为浮点数时都会被忽略。

我还添加了十六进制字符串版本,在 @PeterCordes 的建议下由 @somebody 进一步开发成为 natlog()。它可以产生与我的原始解决方案“相同”的结果(只有最后显示的一个数字之间存在差异)!


3
谢谢,这个有效!小提示:它返回log10而不是自然对数,但可以通过除以Math.log10(Math.E)来修复。如果bigint < 0,我将返回NaN而不是null。 - Mielipuoli
2
这是其中一个需要解释为什么使用此计算方法以及该近似值的正确性的地方,这将非常有帮助。 - Thorbjørn Ravn Andersen
4
如果你实际上不需要log10,那么选择以10为底数转换是一个不必要的昂贵选择。假设BigInt内部使用二进制块,转换为十六进制应该会更便宜,因为每个十六进制数字仅取决于4位二进制数,而不是所有更高的位(这需要BigInt除法)。但获取小数部分则变得更加棘手;除非JS允许在非十进制数字中使用基数点,例如 0x0.abc123 - Peter Cordes
2
解释算法如下:log(a*b)=log(a)+log(b) ==> log(a/b)=log(a)-log(b) ==> log(a)=log(a/b)+log(b) ==> log10(BigInt)=log10("0."+BigInt)+log10(10^BigInt.Length) ==> log10(BigInt)=log10("0."+BigInt)+BigInt.Length。 - Nat
1
当然……你也可以使用十六进制子串,不用小数点,并从中减去Math.min(length, 15) - somebody
显示剩余4条评论

25
其他答案已经充分回答了您在标题中提出的问题,即:“如何计算BigInt的对数?”。但是,您还提到您特别感兴趣的是阶乘的对数,对于这种情况,使用不同的算法可以避免范围上的困难。
应用log(ab) = log(a) + log(b),以下函数计算阶乘的对数:

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

  return total;
}

console.log(logFactorial(170));


4
请注意,这样做可能会积累一些误差。误差有多严重......谁知道呢。但尝试其他方法可能是值得的,比如对每个小于n的质数取log10或log的总和,例如 Math.log(2) * (Math.floor(n / 2) + Math.floor(n / 4) + Math.floor(n / 8) ...etc) - somebody
...但是对于大多数情况来说,像这样简单的东西可能已经足够了。 - somebody
3
太棒了!那我就不需要BigInt了。严格来说,它并没有回答我发布的问题,所以我不能将其标记为答案。但这正是我所需要的,非常感谢你! :) - Mielipuoli
3
是的,这似乎几乎像是一个 https://www.google.com/search?q=xy+question。将对数相加比使用非常大的整数更有意义! - Carsten Massmann
2
作为微优化,您可以从2开始循环,因为log(1)= 0。 - Ilmari Karonen
5
如果你想要一个阶乘的对数,那么斯特林逼近公式:log(n!) ~ n log n - n + O(log n) 就足够了。你可以对这个逼近公式进行进一步的精细化。参见例如 https://en.wikipedia.org/wiki/Stirling%27s_approximation。 - delsim

1
受MWO答案的启发,您可以将BigInt转换为与所需计算对数的对数相同的字符串,并获得字符串长度。
例如,要计算floor(log2(9007199254740991)),您可以执行 BigInt("9007199254740991").toString(2).length - 1
请注意,toString仅允许使用2到36的基数。

1
- 1 只会向相反的方向引入偏差。BigInt("8").toString(2).length4,而 BigInt("31").toString(2).length - 1 也是 4 - Sebastian Simon
@SebastianSimon 或许我只是累了,有点困惑,但我不理解你的例子。是的,BigInt("31").toString(2).length - 1 是4。但这是正确的,不是吗?floor(log2(31)) = 4。(尽管有可能在你的评论后更改了答案,这可以解释) - Stef
@Stef 是的,当然是正确的; 我确实指的是编辑历史记录,作者更改了“要计算 floor(log2()) + 1,您可以执行 BigInt("").toString(2).length ”为“要计算 floor(log2()),您可以执行 BigInt("").toString(2).length - 1”,也许是无意中,因为这些编辑相隔一分钟。 - Sebastian Simon
1
好的,使用这个方法只能将日志四舍五入/截断为整数,因此例如log10(1000) == log10(9999),在许多情况下可能并不那么有用... - ilkkachu

1

回应我之前的评论,如果有人需要寻求高精度对数运算,可以使用一些大数字包来实现这个功能。例如,下面的代码片段使用decimal.js在1000位精度下计算...

  • 使用BigInt验证170!时,使用decimal.js计算170!
  • 使用decimal.js计算170!
  • 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>

顺带一提,有趣的是,即使在1000位数时,仍然会存在四舍五入误差。通常,人们会通过包含一些额外的“隐藏”小数位来进行一些更高精度的计算,然后再将结果保留到所需的精度。


0

如果它纯粹是字符串形式,对于我的代码,我只是懒惰地这样做:

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

单行代码,没有循环,没有递归,也没有专门的 bigint 库 - 什么都没有。

当然,它的精度受到 IEEE 64 位双精度 FP 的限制,因此它只能准确到 15 个左右 的有效十进制数字 位数

因为在第二部分中添加了 "0.",所以该部分不会溢出或下溢,除非您的字符串太长,例如超过 500k 个数字等。

如果是这种情况,请将其缩短到前 300 个数字左右 - 这已经足够了,因为通常情况下,它由描述数量级的左侧项主导,右侧项仅执行较小的精度调整。


0
你能检查一下这个是否适用于你吗?该函数返回一个 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())

对于Log2,分别如下:

 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())


2
如果我想要一个BigInt作为返回值,那么它是有效的。但重点是实际上获得具有小数精度的数字,以便我可以继续进行比仅使用BigInt工作更复杂的其他数学运算。但还是谢谢! - Mielipuoli

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接