3 ms·
… in fact, you can easily compute up to f(10^8) in a couple of seconds using this code (not shown, because the result takes far longer to print than to compute)
by danbruc 7y ago
… in fact, you can easily compute up to f(10^8) in a couple of seconds using this code (not shown, because the result takes far longer to print than to compute).
Is this actually this fast or did the author get fooled by lazy evaluation or something along that line? For the fun of it I tried to come up with an algorithm in C# that works more or less like the matrix exponentiation one but without explicitly using matrix exponentiation. When finished it failed to terminate for large numbers and I eventually estimated that it would take about six hours to find the 100 millionth Fibonacci number with this code on my laptop. I don't see why this would be so much slower than a straight forward implementation of the matrix exponentiation algorithm, where is the big difference if any? Or is the .NET big integer implementation that slow? Or did the author get fooled after all?
private static BigInteger Fibonacci(UInt32 n)
{
if (n == 0)
{
return BigInteger.Zero;
}
else
{
var (a, b) = (BigInteger.Zero, BigInteger.One);
var mask = 1u << (Int32)Math.Floor(Math.Log(n, 2));
while ((mask >>= 1) != 0)
{
var s = a + b;
var (a2, b2, s2) = (a * a, b * b, s * s);
(a, b) = ((n & mask) == 0) ? (a2 + b2, s2 - a2) : (s2 - a2, s2 + b2);
}
return b;
}
}
- mcnamaratw 7y agoTo do f(10^8) the OP says his/her code would take the matrix and square it about 26 times (2^26 = 67 million and change), then do some more in other ways. That's where the speedup comes from. Are you also doing that? (The mechanism for the speedup is described in passing, in a little note about the Haskell library function he's using to calculate a power of the matrix. For whatever it's worth this trick is excellent, but it dates from before computers were invented.)
- danbruc 7y agoYes, as you can see in the code, the loop executes once for each bit to the right of the leftmost set bit or equivalently ⌊log₂(n)⌋ times. Naively this suggest a runtime of O(log(n)) but the numbers become huge pretty quickly and then all the arithmetic operations are far from O(1). The actual runtime is probably more like O(n²) or O(n² log(n)) after one accounts for the runtime of the big integer operations.
- edflsafoiewq 7y agoI transcribed your code into Python and it took about 90s to do fib(10[star][star]8) on my T420. Language doesn't matter of course, this is just an exercise of the bignum library. Nice idea to use s.
- danbruc 7y agoOkay, so the .NET big integer implementation is like two orders of magnitude slower than it could be? I will have a look into that, I always assumed that all big integer libraries are more or less comparable in performance. Thanks for the hint. EDIT: I found an issue [1] concerning .NET big integer performance, it seems it is only using pretty basic and relatively slow algorithms, especially for multiplication which is the relevant operation here. [1] https://github.com/dotnet/runtime/issues/14407 https://github.com/dotnet/runtime/issues/14407