Create a gist now

Instantly share code, notes, and snippets.

@wting /Fib.java Secret
Last active Dec 12, 2015

What would you like to do?
Fibonacci microbenchmark, moved to here: https://github.com/wting/fib-benchmark#performance
// gcc -O2 fib.c
#include <stdio.h>
int fib(n) {
if (n < 2)
return 1;
return fib(n-2) + fib(n-1);
}
int main(int argc, char const* argv[]) {
printf("%d\n", fib(40));
return 0;
}
(defn fib [n]
(if (= n 0) 0
(if (= n 1) 1
(+ (fib (- n 1)) (fib (- n 2))))))
(defn -main
(println (fib 30)))
package main
import "fmt"
func fib(n int) int {
if n < 2 {
return 1
}
return fib(n-2) + fib(n-1)
}
func main() {
fmt.Println(fib(40))
}
-- ghc -O -O2 -optc-O3 fib.hs
fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = fib(n-1) + fib(n-2)
main = do
print (fib 40)
class Fib {
static int fib(int n) {
if (n < 2)
return 1;
return fib(n-2) + fib(n-1);
}
public static void main(String[] args) {
System.out.println(fib(40));
}
}
function fib(n) return n < 2 and 1 or fib(n-2) + fib(n-1) end
print(fib(40))
def fib(n):
if n < 2:
return 1
return fib(n-2) + fib(n-1)
print(fib(40))
def fib(n)
if n < 2
return 1
end
return fib(n-2) + fib(n-1)
end
puts fib(40)
fn fib(n: int) -> int {
if n < 2 {
return 1;
}
fib(n-2) + fib(n-1)
}
fn main() {
io::println(fmt!("%d", fib(40)));
}

Performance

C:              0.38s
Java:           0.55s
Go:             0.90s
Rust:           1.29s
Haskell:        1.32s
LuaJit:         2.17s
PyPy:          10.06s
Lua:           21.18s
Ruby 1.9.3:    22.13s
Ruby 2.0.0:    22.13s
Python 2.7.3:  43.88s
Python 3.3.0:  66.28s

Test Machine

CPU: i7-2640M @ 2.80GHz
RAM: 16GB
HDD: SSD
kmag commented Feb 12, 2013

The Lua version should be
function fib(n) return n < 2 and 1 or fib(n-2) + fib(n-1) end

so that fib(0) will be 1, just like your other implementations.

Edit: swapped the order of the recursive calls to be consistent with original implementation

Owner
wting commented Feb 24, 2013

Thanks, I've updated the code and ran the benchmark again but it only made a marginal difference (~0.1s).

The Clojure results seem to be missing.

Owner
wting commented Apr 1, 2013

@johntyree: Clojure results added here. Gists don't support directories so I had to migrate to a repo.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment