First off .. let me say I liked the video, it was a good overview and packed a lot of knowledge.<p>gmp contains not only the basic operations on arbitrary precision integers, it also contains a highly efficient implementation of the fibonacci sequence.<p>It uses a recurrence relation other than the ones mentioned, that can generate F(2<i>k-1) and F(2</i>k+1) quickly from F(k) and F(k-1): <a href="https://gmplib.org/manual/Fibonacci-Numbers-Algorithm" rel="nofollow">https://gmplib.org/manual/Fibonacci-Numbers-Algorithm</a><p>(so in a way it's similar to the repeated squaring matrix algorithm, you find your way up to the desired number in log2(n) uses of the recurrence relation)<p>My particular computer (AMD Ryzen 7 3700X) can compute fibonacci(21'500'000) (21 and a half million) as a 149,262,011 bit number in right around 1s. The wrapper program is not very interesting, it's literally just calling `mpz_class::fibonacci`...: <a href="https://gist.github.com/jepler/9908e9ee4a7b0becc11edbedf8b76539" rel="nofollow">https://gist.github.com/jepler/9908e9ee4a7b0becc11edbedf8b76...</a><p>(I commented out the line finding the decimal length of the resulting number, but this was not actually a very big part of the runtime and could probably still have stayed under 1s.)<p>On the same machine, OP's bin/field_ext.O3.out program takes a hair over 1 second to compute F(4 million) so it seems this algorithm, plus the probably better-optimized gmp, are well faster.<p>However, gmp gives out soon after: It only supports numbers up to (I think; it's been a while since I figured this out) CHAR_BIT * sizeof(int) * (1<<31) bits long so it literally can't find F(256 million):<p><pre><code> gmp: overflow in mpz type
Command terminated by signal 6</code></pre>