Paste: fib

! 32-bit C: 
! int fib_c(int n) { 
! 
!     int x=0, y=1, i=0; 
! 
!     for(;i<n;i++) {
!         int t = y; y=x+y; x=y; 
!     } 
!     return x; 
! }

:: fib-c-32-bit ( n -- m ) 0 :> 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