寻找确切的迭代次数

Question

在Fa(x, a)中，x是某个数，a是迭代次数。此外，在 Fb(x, y, dev) 中， min 和 max 是一个较低和较高的区间， dev一些允许偏差，returns 间隔中每个数字所需的迭代次数。例如，如果 min 需要 5 次迭代，max 需要 10 次迭代，Fb returns 10.

因此，这会产生：

unsigned int Fa(double x, unsigned int a);

unsigned int Fb(double min, double max, double dev)  {
  unsigned int it_min = 1;
  unsigned int it_max = 1;
  for(; fabs(Fa(min, it_min) - Fa(min, it_min+1)) > dev; it_min++);
  for(; fabs(Fa(max, it_max) - Fa(max, it_max+1)) > dev; it_max++);
  return it_min > it_max ? it_min+1 : it_max+1;
}

但是，这种函数对于大数 (> 1000) 来说真的很慢，因为迭代次数是疯狂的（迭代次数 > 100,000,000）。有没有更快的方法？

我通过添加 it_min* = 20 和使用 it_min-- 的 for 循环使其更快，但它仍然太慢。

感谢您的帮助。

Answer 1

这里有一个优化：

unsigned int iter(double v, double dev, unsigned int i) {
  double r;
  double fa1 = Fa(min, i);
  do {
    double fa2 = Fa(min, ++i)
    r = fabs(fa1-fa2);
    fa1 = fa2;
  } while (r > dev);
  return i;
}

unsigned int Fb(double min, double max, double dev)  {
  unsigned int it_min = iter(min, dev, 1);
  unsigned int it_max = iter(max, dev, 1);

  return it_min > it_max ? it_min+1 : it_max+1;
}

这样，您将在每次迭代中仅评估 Fa一次，而不是两次。

Answer 2

您对 Fa 进行了重复调用。这是消除这些重复项的方法。响应时间将减少一半：

unsigned int Fb(double min, double max, double dev)  {
  unsigned int it_min = 0;
  unsigned int it_max = 0;

  double delta;
  double previousFa = Fa(min, 1);
  do {
    it_min++;
    double nextFa = Fa(min, it_min+1);
    delta = previousFa - nextFa;
    previousFa = nextFa;
  } while (delta > dev);

  ... // do the same for max/it_max

  return it_min > it_max ? it_min+1 : it_max+1;
}

Answer 3

我终于找到了答案：我希望输入数字 <1e-5 AND numbers>1e5，所以我从大量迭代开始：(INT_MAX/2)。然后，我检查在哪个区间找到结果，然后再次划分。这将重复直到我得到正确的结果。

寻找确切的迭代次数

Looking for the exact number of iterations

c

iteration