计算算法时间

我有周围幂4,500,000 2的顺序非常大的数字作品的算法。我使用.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)); 
}

来源

2013-02-13 Raheel Khan

正在增加é？ – CR41G14 2013-02-13 11:41:15

@thang：如果我以200,000的指数值开始，算法只需要几秒钟来处理。该算法当然要复杂得多，但上面的代码会产生相同的结果，因为每次迭代的大部分时间都由BigInteger构造函数进行计算。所以你可以想象，随着数字的减少，它会大幅加速。 – 2013-02-13 11:44:27

@ CR41G14：我的错误。修复了代码。每次迭代都会减少“e”。 – 2013-02-13 11:47:03

首先重写

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

为

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

然后你发现，该算法Ô后终止（1）迭代（〜每次迭代70％终止的几率），你也许可以忽略除第一次迭代以外的所有成本。

算法的总成本大约是Math.Pow(2, e)的初始指数e的1至2倍。对于基地= 2，这是一个简单的位位移，为您需要其他方和乘法

来源

2013-02-13 12:06:28 CodesInChaos

谢谢。我会试着看看它是否接近实际的时间。 – 2013-02-13 12:09:52

-1

没有办法，因为你正在使用随机估计未知的时间！

来源

2013-02-13 11:50:23 CR41G14

实际上，随机数仅用于代码示例中，以将每次迭代的缩减限制在1到10之间。我很乐意使用这个级别的近似值。 – 2013-02-13 11:51:33

如果你说每次迭代都会由于这些值而发生显着变化，那么我不认为这是可能的，你可以做的唯一的事情是每1000次迭代获得一个经过的时间，并将其作为一个非常有用的参数。 – CR41G14 2013-02-13 11:54:20

计算算法时间

回答

相关问题