# Paste: fib

Author: mnestic factor Sat, 29 Aug 2009 01:36:19
Plain Text |
```! 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```

## Annotation: lame version

Author: luis factor Sat, 29 Aug 2009 01:40:55
Plain Text |
```:: (fib) ( n p1 p2 -- f )
n zero? [ p2 ] [ n 1 - p2 p1 p2 + (fib) ] if ;

: fib ( nth -- n )
0 1 (fib) ;```