3

我有一个算法可以处理大约 2 到 4,500,000 次方的极大数字。我使用 .NET 4 中的 BigInteger 类来处理这些数字。

该算法非常简单，因为它是一个基于某些预定义标准减少较大初始数的单个循环。在每次迭代中，数字会减少大约 10 个指数，因此在下一次迭代中，4,500,000 将变为 4,499,990。

我目前每秒进行 5.16 次迭代或每次迭代 0.193798 秒。基于此，算法的总时间应该大约为 22 小时，以将指数值降至 0。

问题是，随着数量的减少，处理内存中的数字所需的时间也会减少。另外，随着指数减少到 200,000 范围，每秒的迭代次数变得巨大，每次迭代的减少量也呈指数增长。

不是让算法运行一整天，有没有一种数学方法可以根据初始起始数和每秒迭代次数来计算需要多少时间？

这将非常有帮助，因为我可以快速衡量优化尝试的改进。

考虑以下伪代码：

double e = 4500000; // 4,500,000.
Random r = new Random();
while (e > 0)
{
    BigInteger b = BigInteger.Power(2, e);
    double log = BigInteger.Log(b, 10);
    e -= Math.Abs(log * r.Next(1, 10));
}
4

2 回答 2

1

第一次重写

double log = BigInteger.Log(b, 10);

作为

double log = log(2)/log(10) * e; // approx 0.3 * e

然后您会注意到算法在 O(1) 次迭代后终止（每次迭代的终止机会约为 70%），您可能可以忽略除第一次迭代之外的所有成本。

算法的总成本大约Math.Pow(2, e)是初始指数的1 到 2 倍e。对于 base=2 这是一个微不足道的位移，对于其他人你需要平方和乘法

于 2013-02-13T12:06:28.540 回答
-1

由于您使用的是随机，因此无法估计未知的时间！

于 2013-02-13T11:50:23.583 回答