fib.fs 548 Bytes
Newer Older
anton's avatar
anton committed
1 2 3 4
\ Note: This is incorrect ("n fib" produces the result for fib(n+1)),
\ but we do not change it to ensure that future timing results are
\ comparable to older timing results.

anton's avatar
anton committed
5 6 7 8 9 10 11 12 13 14
: fib ( n1 -- n2 )
    dup 2 < if
	drop 1
    else
	dup
	1- recurse
	swap 2 - recurse
	+
    then ;

Bernd Paysan's avatar
Bernd Paysan committed
15 16 17 18 19 20 21 22 23 24
: main 34 fib drop ;

\ The problem with fib is that it really is O(1)...
0 [IF]
    5e fsqrt fdup 1/f fconstant /sqrt5
    1e f+ f2/ fln     fconstant gbase
    : fib ( n -- f )
	dup s>f gbase f* fdup fexp fswap fnegate fexp
	1 and IF f+ ELSE f- THEN  /sqrt5 f* ;
[THEN]