Awesome Fibonacci

The Fibonacci sequence, in every language, by every algorithm.

A collection of Fibonacci implementations written to be read and compared, not just to run. The same problem, solved in different languages and with different algorithms, is a surprisingly good lens on what each language and each approach actually costs you — in speed, in memory, and in how much code you have to write.

• The Sequence
• Implementations
• The Algorithms
• Running Them
• Contributing
• License

Every implementation here should follow the standard indexing:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)   for n > 1

Giving: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Every implementation is checked against the same table of known values in CI, so F(10) is 55 in all of them. That consistency is what makes comparing them worth anything.

Rows are languages, columns are the algorithms below. Every implementation is checked against the same values in CI.

Languages we'd love to see: C++, Haskell, JavaScript, Ruby, Elixir, Zig, Clojure, OCaml, Scala, Kotlin, Swift, Erlang, Prolog, APL — and anything else you can make a compiler accept.

Fibonacci is a small problem with a genuinely wide spread of solutions, which is what makes it worth collecting:

* Assuming constant-time pow, which stops being true once the numbers outgrow a machine word.

The closed form is the interesting one to compare across languages, because it's the only implementation that's wrong past a point — the rounding error in pow eventually flips the result to a neighbouring integer. Where that happens depends on the language's floating point, not the maths: it's F(76) in Go and Rust (both IEEE double), and F(71) in Python, Lisp, and C. Each implementation's tests pin its own limit, so a regression in it fails the build.

The exact implementations are bounded instead by integer range. In Go and Rust they work in 64-bit integers, where F(93) is the last value that fits; Python and Lisp use arbitrary-precision integers and stay exact as far as you care to compute.

Each language lives in its own top-level directory and is self-contained.

# Go — tests plus benchmarks
cd Go && go test -bench=.

# Rust — `cargo run` prompts for a length and prints the sequence
cd Rust && cargo test

# Python
cd Python && python -m unittest discover

# Lisp
cd Lisp && sbcl --script fibonacci_test.lisp

# C
cc -std=c11 -Wall -Wextra -Wpedantic -Werror C/fibonacci.c C/fibonacci_test.c -lm -o /tmp/fibonacci_test && /tmp/fibonacci_test

Contributions are very welcome, whether that's a new language, a new algorithm in a language that's already here, or tests for one that lacks them.

The short version:

1. Put your code in the directory for its language, creating it if it doesn't exist yet (use the language's conventional name — Haskell, not hs).
2. Follow the standard indexing: F(0) = 0, F(1) = 1.
3. Name files after the algorithm — recursive_fibonacci.py, matrix.go.
4. Use the language's idiomatic layout and tooling. A Rust entry should be a Cargo project; a Go entry should be a package with _test.go files.
5. Add tests if the language makes it reasonable to.
6. Update the table in Implementations.

See CONTRIBUTING.md for the longer version.

GPL-3.0 © Parham Alvani