Consider the experiment of estimating how long it would take to evaluate
fibonacci on a workstation. First evaluate fib_work 100.
Since the definition given above results in a recursive process, it is necessary
to create a definition which results in an iterative process when evaluated.
Consider the following definitions:
fib_work_iter =: monad def 'fib_iter 1 1 , y.'
fib_iter =: monad define
('a' ; 'b' ; 'count') =. y.
if. count = 0
do. b
else. fib_iter (1 + a + b) , a , count - 1
end.
)
Applying fib_work_iter to the integers 0 through 10 gives the same result as
applying fib_work:
fib_work_iter "0 i. 11 1 1 3 5 9 15 25 41 67 109 177
Next, use fib_work_iter to compute fib_work 100 (exactly).
fib_iter 100x 57887932245395525494200
Finally, time the recursive fibonacci definition on arguments not much larger
than 20 to get an estimate of the number of applications/sec the workstation can perform.
(fib_work_iter ("0) 20 21 22 23) % time'fibonacci ("0) 20 21 22 23'
845.138 1367.49 2212.66 3580.19
Using 3500 applications/sec as an estimate we have:
0 3500 #: 57887932245395525494200x 16539409212970150141 700 0 100 365 24 60 60 #: 16539409212970150141x 5244612256 77 234 16 49 1
which is (approximately) 5244612256 centuries!
An alternate experimental approach to solve this problem is to time the recursive
fibonacci definition and look for patterns in the ratios of successive times.
experiment =: (4 10 $'fibonacci ') ,. ": 4 1 $ 20 21 22 23 experiment fibonacci 20 fibonacci 21 fibonacci 22 fibonacci 23 t =: time "1 experiment t 2.75291 4.42869 7.15818 11.5908 (1 }. t) % _1 }. t 1.60873 1.61632 1.61924 ratio =: (+/ % #) (1 }. t) % _1 }. t ratio 1.61476 0 100 365 24 60 60 rep x: ratio^100 205174677357 86 306 9 14 40
This experimental approach produces a somewhat larger estimate of more than 205174677357 centuries. Students should be cautioned about certain flaws in either experimental design.