Compute the N-th Fibonacci using three different, popular implementations:

• Naive Recursion: Version using the naive recursion (1 iteration).
• Tail Recursion: Version using the tail recursion (M iterations).
• Iterative: Iterative version using loops (M iterations).

Each version will be run in a separate benchmark stage. In order to bring the tail-recursive and the iterative versions in a measurable range (if possible at all), the implementations have to repeat the computation M times, updating a checksum according to:

checksum = 0
for i in 0 .. <M:
    checksum += fibonacci_iterative(N)
    checksum %= 2147483647

Benchmark aspects: Recursion

Input

• N -- The Fibonacci number to compute.
• M -- The number of iterations to repeat the tail-recursive and iterative implementations.

Control Output

After writing the stage run times to STDOUT, the implementations should print:

• N-th Fibonacci result (result from first stage)
• checksum from second stage
• checksum from third stage

• C++: Default implementation for C++, gcc (O3)
• C++: Default implementation for C++, clang (O3)
• Go: Default implementation for Go
• Nim: Default implementation for Nim (gcc)
• Nim: Default implementation for Nim (clang)
• Python: Default implementation for Python
• Rust: Default implementation for Rust
• Scala: Default implementation for Scala

Each bar corresponds to the run time of one particular stage. Use mouse-over to highlight a single stage for comparison. Only shows run times of the largest data size.

Run time: Total

All raw run times of individual runs for small (N = 34, M = 145806), medium (N = 36, M = 306557), and large (N = 38, M = 644537) problem sizes. Use mouse-over to see relative performance.

Run time: Naive Recursion

All raw run times of individual runs for small (N = 34, M = 145806), medium (N = 36, M = 306557), and large (N = 38, M = 644537) problem sizes. Use mouse-over to see relative performance.

Run time: Tail Recursion

All raw run times of individual runs for small (N = 34, M = 145806), medium (N = 36, M = 306557), and large (N = 38, M = 644537) problem sizes. Use mouse-over to see relative performance.

Run time: Iterative

All raw run times of individual runs for small (N = 34, M = 145806), medium (N = 36, M = 306557), and large (N = 38, M = 644537) problem sizes. Use mouse-over to see relative performance.