gmp uses a particular recurrence relation to exactly compute fib(x) in about log(x) steps[0]. Of course, the digits of the numbers it has to multiply also incr

gmp uses a particular recurrence relation to exactly compute fib(x) in about log(x) steps[0]. Of course, the digits of the numbers it has to multiply also increase. It's fast-ish up to fib(128 million) or so but soon after that you run into the limit of the size of numbers in gmp, which are limited to being less than 2^31 * 32 bits long or something. [0]: https://gmplib.org/manual/Fibonacci-Numbers-Algorithm https://gmplib.org/manual/Fibonacci-Numbers-Algorithm