Instantly share code, notes, and snippets.

# t-nissie/fib.jl

Last active May 31, 2021 22:14
Star You must be signed in to star a gist
Three ways of generating n-th Fibonacci number in Julia language
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/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
``````
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 --- 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 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

``````