BigInt 的优化整数对数 base2

Question

这是计算整数 log2(n) 的朴素算法，

  function ilog2(n) {  // n is a positive non-zero BigInt
     const C1 = BigInt(1)
     const C2 = BigInt(2)
     for(var count=0; n>C1; count++)  n = n/C2
     return count
  } // example ilog2(16n)==4

我正在测试优化（请参见下面的示例），但它们不是“用于 log2”，正如这里所评论的。

有什么更好的使用WebAssembly吗？

PS：如果不可能有一个通用的解决方案，为了解决我的问题，我可以使用像ilog2_64bits(n)，WebAssembly 截断或忽略输入 BigInt 的一些位的函数 。

---

非 WebAssembly

在纯 Javascript 中没有那么优化的示例（理想的是 WebAssembly！）......尝试改编BigInteger.js的 integerLogarithm() ：

  function ilog2_pe(value, base=2n) {
      // example: ilog2_pe(255n) returns { p: 128n, e: 7n }
      if (base  <= value) {
          let i = ilog2_pe(value, base**2n);
          let t = i.p*base
          return (t <= value)
            ? { p: t,   e: i.e*2n + 1n }
            : { p: i.p, e: i.e*2n }
      }
      return { p: 1n, e: 0n };
  }

  function ilog2_str(n) { // 2*faster!
    return n.toString(2).length - 1
  }

PS：它在现代浏览器和最新版本的 NodeJS 中运行。

---

关于性能...ilog2_pe(x64bits)快4倍艾德里安的天真ilog2()，ilog2_pe(x1024bits)是〜快9倍......，预计......但是：

任何非 WebAssembly 解决方案都有如此丑陋的性能，即使是 512、1024、2048 位......计算字符串数字的ilog_str()速度要快 2 倍！对于少于 64 位，速度要快 3 倍或更多。

Answer 1

以下代码在 Firfeox 89、Chrome 90 上似乎比 ilog2_str 更快。

function ilog2_str(n) { // 2*faster!
  return n.toString(2).length - 1
}

function ilog2_bs(value) {
  let result = 0n, i, v;
  for (i = 1n; value >> (1n << i); i <<= 1n);
  while (value > 1n) {
    v = 1n << --i;
    if (value >> v) {
      result += v;
      value >>= v;
    }
  }
  return result;
}

testcases = [...Array(10000)].map((n, i) => 13n ** BigInt(i));
testcases.map(ilog2_str);
testcases.map(ilog2_bs);

虽然我不知道为什么。