Skip to content

Instantly share code, notes, and snippets.

@t-nissie t-nissie/fib.jl
Last active Sep 23, 2017

Embed
What would you like to do?
Three ways of generating n-th Fibonacci number in Julia language
#!/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

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.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
@kafisatz

This comment has been minimized.

Copy link

kafisatz commented Sep 23, 2017

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.