Algorithm timing
I have an algorithm that works with extremely large numbers around the order of 2, raised to a power of 4,500,000. I am using the BigInteger class in .NET 4 to handle these numbers.
The algorithm is very simple in that it is the only loop that reduces a large seed based on some predefined criteria. With each iteration, the number decreases by about 10 exponents, so that in the next iteration, 45,000,000 becomes 4,499,990.
I am currently getting 5.16 iterations per second, or 0.193798 seconds per iteration. Based on this, the total time for the algorithm should be approximately 22 hours to bring the exponent value down to 0.
The problem is that as the number decreases, the time it takes to process the number in memory also decreases. Plus, as the exponentiation rate decreases to the 200,000 range, the iterations per second get huge, and the decrease per iteration also increases exponentially.
Instead of letting the algo run all day, is there a mathematical way to calculate how long it will take based on the initial seed and iterations per second?
This would be very helpful as I can quickly measure the optimization attempts.
Consider the following psuedocode:
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));
}
source to share
Rewrite first
double log = BigInteger.Log(b, 10);
and
double log = log(2)/log(10) * e; // approx 0.3 * e
Then you will notice that the algorithm ends after O (1) iterations (70% chance of aborting on each iteration), perhaps you are neglecting the cost of everything but the first iteration.
The total cost of your algorithm is about 1-2 times more expensive than the Math.Pow(2, e)
original metric e
. For base = 2 this is a trivial beat-break, for others you will need to square-and-multiply
source to share