求最大n的最快算法,使x^n<=y

如果 gmp library 包含对数函数,请使用它

result = Floor(log(y)/log(x))

否则您可以利用 binary search square x (x, x^2, x^4, x^8) 如果可能,则减小功率步长

returns 24 for x = 2; y = 31415926.0;
(same as Floor(ln(y)/ln(x))

int FindXPower(double x, double y) 
{
  int Powers[64];
  double t, s, next;
  int ix;

  //exponential search phase
  ix = 0;
  t = x;
  while (t <= y)
  {
    Powers[ix++] = t;  //remember them to use later
    t = t * t;
  };
  //now powers contain [x,x^2,x^4,x^8,x^16...]

  ix--;
  int Result = 1 << ix;  // 2^lastindex: 1,2,4,8,16,32...

  //binary search phase
  s = Powers[ix--];     //max value after squaring
  while ((s < y) && (ix >= 0))
  {
     t = Powers[ix];
     next = s * t;
     while (next < y)
     {
      s = next;
      next = next * t;
      Result = Result + (1<<ix);
     }
     ix--;
  };
  return Result;
}

而不是线性递减 n 您可以通过二分法搜索正确的值。

定义两个变量: n_low n_high 具有在任何时刻的不变量 x^n_high 严格大于 y x^n_low 小于或等于 y .

m 两者之间的距离减半 n_高 .

然后比较 x^m 具有 .如果严格地说是大的,则分配: n_high = m else分配 n_low = m 什么时候 n_low+1==n_high 的价值 就是你想要的价值。

我假设您使用的是任意精度整数(GMP还支持任意精度浮点)。

• 估算计算结果 n_est = floor(log(y_float) / log(x_float))
• 实际 n 要么是 n_est - 1 , n_est 或 n_est + 1 这很容易检查。