将二进制大整数转换为科学计数法并截断为 1 位尾数的算法

Question

我有一个非常大的无符号二进制大整数，规模为 6*10^120。 假设大整数存储在许多 QWORD（8 字节）无符号整数或几个 YMM 寄存器的结构中。

我想用十进制（不是二进制）科学记数法来显示它，比如

6E120

。尾数始终为 1 位，并且必须是完整十进制表示形式的前导数字；将其截断为 1 位有效数字，而不是四舍五入到最接近的数字。指数始终为 3 位数。格式是 aExyz，如 8E095。

找到数量级（10 的幂）和前导小数位的最省时（最快）的算法是什么？ 我是求算法，不是求程序，我自己写。

会用MASM64汇编语言来完成。如果有指令可以提供帮助，例如位操作或 FPU/SSE/AVX512 技巧，请提出建议。

这不是一个高级程序，因此任何包含第三方库或高级语言结构的响应都没有帮助。 我知道某种算法涉及许多部门。这些在 ASM 中很昂贵，所以我正在寻找替代方案。我知道如何将二进制转换为十进制，然后再转换为科学记数法。我试图避免中间步骤。

Answer 1

假设最大可能值合理地接近您的平均值，我怀疑答案可能是：

1. 在静态常量数组中预先计算所有可能的

   powers_of_10

   。 (#ops ~0)
   • 如果所有数字都适合 2 个 YMM 寄存器，这意味着支持的最大值为 1E154，这意味着 10 的幂的查找表将占用 ~9856 字节。
2. 在您的数字中，计算前导binary零的数量（也使用

   clz

   ）（#ops< ~10)
3. 使用

   (max-bits - number_of_leading_zeroes) / 3.32192809489

   可以很好地估计最终的小数位数。这也是一个很好的估计 10 的接近幂。(#ops ~2)
4. 从该估计中迭代

   powers_of_10

   ，直到找到小于您的值的最大 10 次方。 (#ops ~8)
   • 如果你愿意牺牲指数的准确性，那么这一步可以跳过。
5. 在循环中将 10 的幂加到自身，直到大于您的输入。 （#ops< ~100) (10 additions of 10

   uint64

   s）
   • 如果您愿意牺牲尾数的次要准确性，那么

     double(input)/double(power_of_ten)

     将在一个分区中完成。
6. 发射

   loop_count-1

   E

   power_of_ten_index

   。 (#ops ~4)

如果您愿意牺牲指数和尾数的准确性，那将剩下约 16 个完全忽略低位的操作。