javascript - 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”，如 commented here .

使用 WebAssembly 有更好的东西?

PS:如果不可能有一个通用的解决方案，为了解决我的问题，我可以使用像 ilog2_64bits(n) 这样的函数，WebAssembly chop 或忽略输入 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)比天真的 ilog2() 快 4 倍, 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);

虽然我不知道为什么。