C：对 256 位整数求幂

Question

我正在处理一种对无符号 256 位整数进行运算的算法，我需要编写一个函数来计算给定公式的值

uint256 compute(uint16 x) {
    return floor(exp2(x / 256)) - 1;
}

我们可以看到方程保留了变量边界 (compute(0) == 0, compute(65535) == 1<<255)。除法应该被视为有理数的除法，而不是整数。

提供的语法是伪 C 语法，但我正在寻找可以在其他语言中使用的通用算法方法。

非常感谢您的帮助和时间。

Answer 1

您可以预先计算 [65280, 65535] 中 x 函数的所有 256 位值并制成表格（即 255 x 256 + i）；您将通过参数的 8 个最低有效位查找 table。这将占用 8KB 的存储空间。

对于较低的参数值，将表格值右移 255 - (x >> 8)。

如果您想要纯粹的速度并且能够负担得起 64KB 的存储空间，您可以预先计算 0 到 7 的移位，并通过使用正确的字节偏移进行复制来执行更大的移位。

或者，您可以考虑使用指数函数的 CORDIC 方法，但我认为它不会更快或需要更少的存储空间。

C: Exponentiation over 256bit integers