Three ways of generating n-th Fibonacci number in Julia language

fib.jl

#!/usr/bin/env julia
# Gist: https://gist.github.com/t-nissie/641df996b9035f85b230
# Three ways of generating n-th Fibonacci number in Julia language
# Put perfutil.jl in the same directory as:
#     wget https://raw.githubusercontent.com/JuliaLang/julia/master/test/perf/perfutil.jl
# Turn off garbage collection (GC), when you get occasional bad timings. See perfutil.patch below.
###
using Base.Test
include("perfutil.jl")

## recursive fib ##
rfib(n) = n < 2 ? n : rfib(n-1) + rfib(n-2)
@test   rfib(30) == 832040
@timeit rfib(30) "rfib30" "Recursive fibonacci"

## tail recursive fib ##
helper(current, next, n) = n==0 ? current : helper(next, next+current, n-1)
tfib(n) = helper(BigInt(0), BigInt(1), n)
@test   tfib(30) == 832040
@timeit tfib(30)   "tfib30" "Tail-recursive fibonacci"
@timeit tfib(1000) "tfib1k" "Tail-recursive fibonacci"
# tfib(1000_000) -> StackOverflowError
# https://github.com/JuliaLang/julia/issues/4964: we're not actually planning to implement tail-call-optimization ...

## matrix fib ## Ref. http://enterprisegeeks.hatenablog.com/entry/2014/07/22/125603 ##
function mfib(n)
   F = BigInt[1 1; 1 0]
   Fn = F ^ n
   Fn[2, 1]
end
@test   mfib(30) == 832040
@timeit mfib(30)       "mfib30" "Matrix fibonacci"
@timeit mfib(1000)     "mfib1k" "Matrix fibonacci"
@timeit mfib(1000_000) "mfib1M" "Matrix fibonacci"
@timeit mfib(1048_576) "mfibP2" "Matrix fibonacci"   # 2^20

fib.md

Benchmark results of three ways of generating n-th Fibonacci number in Julia language

perfutil.jl repeats timing unitil the total time exceeds 2 second.

Normal

You may get occasional bad timings.

julia,rfib30,  8.538760, 11.409943,  8.939613,  0.721338
julia,tfib30,  0.006470, 38.306444,  0.010211,  0.317977
julia,tfib1k,  0.258336, 27.925543,  0.396892,  1.609619
julia,mfib30,  0.019380, 42.976481,  0.031119,  0.512464
julia,mfib1k,  0.042365, 31.833606,  0.064658,  0.712824
julia,mfib1M, 33.427004, 46.740143, 35.335734,  2.200661
julia,mfibP2, 24.446778, 30.853158, 25.735110,  1.490637

Garbage collection (GC) turned off

Garbage collection (GC) is turned off with perfutil.patch. Much better, but still bad timings are.

julia,rfib30,  8.538646, 11.232758,  8.935024,  0.722507
julia,tfib30,  0.006414,  0.198812,  0.007206,  0.002313
julia,tfib1k,  0.259024,  0.679841,  0.288803,  0.037958
julia,mfib30,  0.019201,  0.159903,  0.020940,  0.004771
julia,mfib1k,  0.042209,  3.186654,  0.046943,  0.018111
julia,mfib1M, 33.383937, 39.606305, 34.842625,  1.482601
julia,mfibP2, 24.444076, 29.963378, 25.259533,  1.201020

perfutil.patch

--- perfutil.jl.original	2016-02-16 11:22:00.000000000 +0900
+++ perfutil.jl	2016-02-16 11:22:27.000000000 +0900
@@ -57,7 +57,7 @@
         if codespeed
             submit_to_codespeed( $t, $name, $desc, "seconds", test_group )
         elseif print_output
-            @printf "julia,%s,%f,%f,%f,%f\n" $name minimum($t) maximum($t) mean($t) std($t)
+            @printf "julia,%s,%10.6f,%10.6f,%10.6f,%10.6f\n" $name minimum($t) maximum($t) mean($t) std($t)
         end
         gc()
     end
@@ -69,7 +69,9 @@
         tot = 0.0
         i = 0
         while i < mintrials || tot < mintime
+            gc_enable(false)
             e = 1000*(@elapsed $(esc(ex)))
+            gc_enable(true)
             tot += e
             if i > 0
                 # warm up on first iteration

Have you ever considered this function?
see: https://www.nayuki.io/page/fast-fibonacci-algorithms

"""Returns the tuple (F(n), F(n+1))."""
fib_bk(x::Int) = fib_bk(BigInt(x))

function fib_bk(n::BigInt)
	if n == 0
		return (BigInt(0), BigInt(1))
	else
		a, b = fib_bk(div(n,2))
		c = a * (b * BigInt(2) - a)
		d = a * a + b * b
		if iseven(n)
			return (c, d)
		else
			return (d, c + d)
        end
    end
end