c - 找到最大 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

如果gmp库包含对数函数，则使用它

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

否则你可以利用二分搜索 - 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;
}