找到最大 n 使得 x^n<=y 的最快算法

Question

我正在做一个项目，该项目要求我找到最大的 n，使得 x^n<=y 提供了 x 和 y。我正在使用 gmp 库并在 c 中处理大量数据。

约束条件：

x>=1 & y>=1

使用我想到的第一种方法，当 x=12 且 y = 411^20000 时，我花了大约 5 秒的时间找到 n，即

int n=0;
int x=12;
int y=100;
int temp;
int answer;
while(1)
{
    temp = pow(x,n);
    if(temp>y)
        {
            answer = n-1;
            return(0);
        }
   n++;
}

注意：不是实际代码。不想用 gmp 语法使事情复杂化

有没有更快的算法？完整代码： https://pastebin.com/J1vbmEbK

Answer 1

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

定义两个变量：n_low 和 n_high，其不变量在任何时刻 x^n_high 严格大于 y 且 x^n_low 是小于或等于 y.

在每次迭代中，计算 m 的值，它将 n_high 和 n_low 之间的距离减半。

然后比较 x^m 和 y。如果严格大于，则赋值：n_high = m 否则赋值 n_low = m。当 n_low+1==n_high 时 n_low 的值就是您要查找的值。

Answer 2

如果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;
}

Answer 3

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

将 bigints 转换为浮点数。这会产生舍入误差。
估计结果计算n_est = floor(log(y_float) / log(x_float))。
实际的 n 是 n_est - 1、n_est 或 n_est + 1，这很容易检查。

找到最大 n 使得 x^n<=y 的最快算法

Fastest algorithm to find the largest n such that x^n<=y

c

algorithm

math

gmp