fibonacci

Fibonacci Number Generator

$ fib --help
Usage: fib n
Calculate the nth Fibonacci number

$ seq 1 20 | xargs -n1 fib | tr '\n' ' '
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 

This generator uses the approximation floor(0.5 + (phi^n)/sqrt(5)) [1]. As such, it is much faster than methods which rely on incremental recursion, without sacrificing accuracy.

As it relies on the C math library, exact integer output isn't possible for n > 92, since the largest long long integer is 9223372036854775807. For such large numbers, we fall back on approximate output (%Lg in printf(3)).

[1] https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding