! 32-bit C: ! int fib_c(int n) { ! ! int x=0, y=1, i=0; ! ! for(;i x! 1 :> y! n [ x y w+ y x! y! ] times x ; :: fib-c-big ( n -- m ) 0 :> x! 1 :> y! n [ x y + y x! y! ] times x ; : fib-recursive ( n -- m ) dup 1 <= [ [ 1 - fib-recursive ] [ 2 - fib-recursive ] bi + ] unless ; MEMO: fib-memo ( n -- m ) dup 1 <= [ [ 1 - fib-memo ] [ 2 - fib-memo ] bi + ] unless ; : fib-times ( m -- n ) [ 0 1 ] dip [ tuck + ] times drop ; : (fib-tc) ( x y n -- m ) dup 0 = [ 2drop ] [ [ tuck + ] [ 1 - ] bi* (fib-tc) ] if ; : fib-tc ( n -- m ) [ 0 1 ] dip (fib-tc) ; : fib-mn ( n -- n' ) { { 1 1 } { 1 0 } } swap m^n first second ; ! Benchmarks 42 [ "fib-recursive 42" print [ fib-recursive drop ] benchmark time. ] [ "fib-memo 42" print [ fib-memo drop ] benchmark time. ] bi "fib-memo 10000" print [ 10000 fib-memo drop ] benchmark time. ! Biggest fib # to fit into 32-bit signed integer "fib-c-32-bit 44" print [ 44 fib-c-32-bit drop ] benchmark time. 1000000 { [ "fib-mn 1000000" print [ fib-mn drop ] benchmark time. ] [ "fib-tc 1000000" print [ fib-tc drop ] benchmark time. ] [ "fib-times 1000000" print [ fib-times drop ] benchmark time. ] [ "fib-c-big 1000000" print [ fib-c-big drop ] benchmark time. ] [ "fib-c-32-bit 1000000" print [ fib-c-32-bit drop ] benchmark time. ] } cleave fib-recursive 42 == Running time == 16.437921 seconds fib-memo 42 == Running time == 0.0 seconds fib-memo 10000 == Running time == 0.031251 seconds fib-c-32-bit 44 == Running time == 0.0 seconds fib-mn 1000000 == Running time == 25.219396 seconds fib-tc 1000000 == Running time == 90.28319999999999 seconds fib-times 1000000 == Running time == 89.345465 seconds fib-c-big 1000000 == Running time == 88.861081 seconds fib-c-32-bit 1000000 == Running time == 0.250006 seconds