math - 如何在没有大整数乘法的情况下获得 5**x 的前 x 个前导二进制数字

Question

我想以完美的精度高效优雅地计算 5**x 的前 x 个前导二进制数字？

例如5**20是10101101011110001110101111000101101011000110001。前8位二进制数字是10101101。

在我的用例中，x 最多为 1-60。我不想创建一个表。使用 64 位整数的解决方案就可以了。我只是不想使用大整数。

Answer 1

first x leading binary digits of 5**x without big integer multiplication

efficiently and elegantly compute with perfect precision the first x leading binary digits of 5^x?

“以完美的精度计算”遗漏了 pow()。太多的实现将返回不完美的结果，FP 数学可能不会使用 64 位精度，即使使用 long double。

---

用一个 64 位整数部分 .ms 和一个 64 位小数部分 .ls 组成一个整数。然后循环 60 次，乘以 5 并根据需要乘以 2，以防止前导位变得太大。

请注意 分数 中有一些精度损失，N > 42，但这不足以影响 OP 正在寻找的整数部分。

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

typedef struct {
  uint64_t ms, ls;
} uint128;

// Simplifications possible here, leave for OP
uint128 times5(uint128 x) {
  uint128 y = x;
  for (int i=1; i<5; i++) {
    // y += x
    y.ms += x.ms;  
    y.ls += x.ls;
    if (y.ls < x.ls) y.ms++;
  }
  return y;
}

uint128 div2(uint128 x) { 
  x.ls = (x.ls >> 1) | (x.ms << 63);
  x.ms >>= 1;
  return x;
}

int main(void) {
  uint128 y = {.ms = 1};
  uint64_t pow2 = 2;
  for (unsigned x = 1; x <= 60; x++) {
    y = times5(y);
    while (y.ms >= pow2) {
      y = div2(y);
    }
    printf("%2u %16" PRIX64 ".%016" PRIX64 "\n", x, y.ms, y.ls);
    pow2 <<= 1;
  }
}

输出

         whole part.fraction
 1                1.4000000000000000
 2                3.2000000000000000
 3                7.D000000000000000
 4                9.C400000000000000
...
57  14643E5AE44D12B.8F5FEE5AA432560D
58  32FA9BE33AC0AEC.E66FD3E29A7DD720
59  7F7285B812E1B50.401791B6823A99D0
60  9F4F2726179A224.501D762422C94044
    ^-------------^ This is the part OP is seeking.

解决这个任务的关键是:divide and conquer .形成一个算法(根据需要只是 *5 和/2)，并编写一个类型和函数来执行每个小步骤。

---

60 的循环是否有效？也许不是。另一种方法是使用 Exponentiation by squaring .对于较大的 N 来说当然是值得的，但是对于 N == 60 来说，一个循环足够简单，可以快速转弯。