有没有比融合泰勒级数更有效的方法来划分和征服 64 位硬件上的 uint 256 日志？
Is there a more efficient way to divide and conquer a uint 256 log on 64 bit hardware with rust or inline assembly than converging Taylor series?
我希望将 256 位无符号整数的对数基数 n（10 会很好）作为 Rust 中的浮点数，而不会损失精度。在我看来，我需要实现一个 8xf64 512 位浮点数 512 类型，并使用泰勒级数来近似 ln，然后求对数。我知道有一些汇编方法可以获取 f64 的日志。我想知道堆栈溢出是否有人可以想到分而治之或其他更有效的方法。我愿意在 8xf64 512 位数组上运行内联汇编。
这可能是有用的算法起点/大纲。 IDK 如果它会给你 exact 结果，比如 error <= 0.5ulp（即你的 512 位浮点数的尾数的最后一位正确舍入），甚至 error <= 1 ulp .也许值得研究 bc / dc / calc 等扩展精度计算器的作用。
我认为 log 收敛很快，所以如果您要进行牛顿迭代来优化，这种位扫描方法可能是获得良好起点的快速方法。即使你真的只需要大约 256 个尾数位正确，我也不知道要得到它需要多大的多项式，并且每个乘法/加法/fma 将在 512 位（8x）或 320 位（5x双精度）。
首先将整数转换为二进制浮点数
对于正常大小的浮点数，通常的方法利用了二进制浮点数的对数特性。如果没有 256 位硬件浮点数，您需要自己找到 ilog2(int)，即最高设置位 () 的位置。
然后将您的 256 位整数视为 [1..2) 或 [0.5 .. 1) 范围内数字的尾数，并且是的，对 log2() 使用多项式逼近，它是准确的 超过那个有限的范围。 （在实际的软浮点数之前，您可能希望将数字左移以便对其进行归一化，即最高设置位在顶部。即 x <<= clz(x).
然后对尾数进行多项式逼近
然后加上整数指数 + log_approx(尾数) => log2(x).
有更多关于实现 log2(double) 的细节（SIMD 一次做 4 个，与做一个扩展精度计算非常不同）。
它包括一些实现的链接，例如Agner Fog 的 VCL 使用两个多项式的比率而不是一个更大的多项式，并使用各种技巧来尽可能保持精度：https://github.com/vectorclass/version2/blob/9874e4bfc7a0919fda16596144d393da5f8bf6c0/vectormath_exp.h#L942。如进一步缩小范围：如果x > SQRT2*0.5，则增加指数并加倍尾数。 （如果 512 位 FP 除法真的很昂贵，你可以在一个多项式中使用更多项。）VCL 目前是 Apache 许可的，所以你可以随意复制你想要的任何东西。
IDK 如果有更多的技巧可能对大扩展精度或软浮点更有价值，那实现 不 使用。 VCL 的数学函数比一些更快的近似值花费更多的精力来保持高精度，但它们并不精确。
你真的需要 512 位浮点数吗？也许只有 320 位（5x 双）？
如果您不需要比 double 更大的指数范围，您可以将 double-double-arithmetic 技术扩展到更宽的浮点数，利用硬件 FP 获得 52 或 53每个 64 位块的尾数位数。 （从评论来看，显然你已经打算这样做了。）
您可能不需要 512 位浮点数来获得足够的精度。 256/52 = 4.92，因此只有 5x double 块比您的输入具有更高的精度（尾数位），并且可以精确表示任何 256 位整数。 （IEEE double 确实有足够大的指数范围；-1022 .. +1023）。并且有足够的余地 log2(int) 应该将每个 256 位输入映射到一个唯一的单调输出，即使有一些舍入误差。
我希望将 256 位无符号整数的对数基数 n（10 会很好）作为 Rust 中的浮点数，而不会损失精度。在我看来，我需要实现一个 8xf64 512 位浮点数 512 类型，并使用泰勒级数来近似 ln，然后求对数。我知道有一些汇编方法可以获取 f64 的日志。我想知道堆栈溢出是否有人可以想到分而治之或其他更有效的方法。我愿意在 8xf64 512 位数组上运行内联汇编。
这可能是有用的算法起点/大纲。 IDK 如果它会给你 exact 结果，比如 error <= 0.5ulp（即你的 512 位浮点数的尾数的最后一位正确舍入），甚至 error <= 1 ulp .也许值得研究 bc / dc / calc 等扩展精度计算器的作用。
我认为 log 收敛很快，所以如果您要进行牛顿迭代来优化，这种位扫描方法可能是获得良好起点的快速方法。即使你真的只需要大约 256 个尾数位正确，我也不知道要得到它需要多大的多项式，并且每个乘法/加法/fma 将在 512 位（8x）或 320 位（5x双精度）。
首先将整数转换为二进制浮点数
对于正常大小的浮点数，通常的方法利用了二进制浮点数的对数特性。如果没有 256 位硬件浮点数，您需要自己找到 ilog2(int)，即最高设置位 (
然后将您的 256 位整数视为 [1..2) 或 [0.5 .. 1) 范围内数字的尾数，并且是的，对 log2() 使用多项式逼近，它是准确的 超过那个有限的范围。 （在实际的软浮点数之前，您可能希望将数字左移以便对其进行归一化，即最高设置位在顶部。即 x <<= clz(x).
然后对尾数进行多项式逼近
然后加上整数指数 + log_approx(尾数) => log2(x).
log2(double) 的细节（SIMD 一次做 4 个，与做一个扩展精度计算非常不同）。
它包括一些实现的链接，例如Agner Fog 的 VCL 使用两个多项式的比率而不是一个更大的多项式，并使用各种技巧来尽可能保持精度：https://github.com/vectorclass/version2/blob/9874e4bfc7a0919fda16596144d393da5f8bf6c0/vectormath_exp.h#L942。如进一步缩小范围：如果x > SQRT2*0.5，则增加指数并加倍尾数。 （如果 512 位 FP 除法真的很昂贵，你可以在一个多项式中使用更多项。）VCL 目前是 Apache 许可的，所以你可以随意复制你想要的任何东西。
IDK 如果有更多的技巧可能对大扩展精度或软浮点更有价值，那实现 不 使用。 VCL 的数学函数比一些更快的近似值花费更多的精力来保持高精度，但它们并不精确。
你真的需要 512 位浮点数吗？也许只有 320 位（5x 双）？
如果您不需要比 double 更大的指数范围，您可以将 double-double-arithmetic 技术扩展到更宽的浮点数，利用硬件 FP 获得 52 或 53每个 64 位块的尾数位数。 （从评论来看，显然你已经打算这样做了。）
您可能不需要 512 位浮点数来获得足够的精度。 256/52 = 4.92，因此只有 5x double 块比您的输入具有更高的精度（尾数位），并且可以精确表示任何 256 位整数。 （IEEE double 确实有足够大的指数范围；-1022 .. +1023）。并且有足够的余地 log2(int) 应该将每个 256 位输入映射到一个唯一的单调输出，即使有一些舍入误差。