Eduardo Cavazos wrote:
Here's a version in FP style, just for fun.
Joy has a 'binrec' (binary recursion) combinator. See this article for
details:
http://www.latrobe.edu.au/philosophy/phimvt/joy/j01tut.html
This is an area where Factor shines.
Here's a version using a 'binrec' in Factor:
----------------------------------------------------------------------
USING: kernel locals math prettyprint tools.time ;
IN: fib
:: binrec ( f: ( -- ) g: ( -- ) h: ( -- ) i: ( -- ) j: ( -- ) -- )
dup f call
[ g call ]
[
dup h call f g h i j binrec
swap i call f g h i j binrec
j call
]
if ; inline recursive
: fib ( a -- b )
[ 1 <= ]
[ drop 1 ]
[ 1 - ]
[ 2 - ]
[ + ]
binrec ;
[ 34 fib ] time .
----------------------------------------------------------------------
~ # ./factor/factor /scratch/_fib-binrec-a.factor
==== RUNNING TIME
1.228229 seconds
==== GARBAGE COLLECTION
Nursery Aging Tenured
GC count: 0 0 0
Cumulative GC time (us): 0 0 0
Longest GC pause (us): 0 0 0
Average GC pause (us): 0 0 0
Objects copied: 0 0 0
Bytes copied: 0 0 0
Total GC time (us): 0
Cards scanned: 0
Decks scanned: 0
Code heap literal scans: 0
9227465
~ #
Compare with the standard version:
----------------------------------------------------------------------
USING: kernel math prettyprint tools.time ;
IN: fib
: fib ( m -- n )
dup 1 <= [ drop 1 ] [ dup 1 - fib swap 2 - fib + ] if ;
[ 34 fib ] time .
----------------------------------------------------------------------
~ # ./factor/factor /scratch/_fib-a.factor
==== RUNNING TIME
1.276612 seconds
==== GARBAGE COLLECTION
Nursery Aging Tenured
GC count: 0 0 0
Cumulative GC time (us): 0 0 0
Longest GC pause (us): 0 0 0
Average GC pause (us): 0 0 0
Objects copied: 0 0 0
Bytes copied: 0 0 0
Total GC time (us): 0
Cards scanned: 0
Decks scanned: 0
Code heap literal scans: 0
9227465
~ #
I.e. the version using 'binrec' is just as fast.
Ed
