Two implementations...
[1/5] from: rgombert::essentiel::net at: 5-Feb-2003 18:24
Hi all rebolers,
I'm back to rebol after two year, and have great times playing with it ;-)
I wanted to show some optimisation possible for some recursive computation,
and wrote the small program below.
Run the test, it talks for itself...
I know this is nothing new for most of you... but maybe it can be of some
help for someone ;-)
Have fun with it...
############### CODE ###############
REBOL [
title: "Test for two implementation of FIBONACCI function"
author: "Renaud GOMBERT"
notes: { slowfib use the intuitive way of implementing fib(n). fastfib
do the same,
but use a block to store allready known values of fibo(n).
* As fastfib store all results, it is provided with a refinement to
release them.
* Both functions works for positive integers.
* Max calculable value is fib(46), according to Rebol math
capabilities.
* If you want to waste CPU time, try running slowfib 46 LOL ;-)
}
]
krono: func [code n /local T][
prin [code "running" n "times... "]
T: now/time/precise
print ["and return:" loop n [do code] ", taking:" (now/time/precise -
T)]
]
slowfib: func [n][
either n < 2 [n][add slowfib n - 2 slowfib n - 1]
]
fastfib: function [n /release][r][
accu: [1 1]
r: either n <= length? accu [
accu/:n
][
last append accu add fastfib n - 2 fastfib n - 1
]
if release [clear at accu 3]
r
]
; TEST RUN
do [
print "TESTING THE TWO FIB FUNCTIONS :^/"
krono [slowfib 25] 10
krono [fastfib 25]10
krono [fastfib/release 25]10
krono [slowfib 30] 5
krono [fastfib 30] 5
krono [fastfib/release 30] 5
krono [fastfib 46] 10000
krono [fastfib/release 46] 10000
krono [fastfib 46] 1450000
krono [slowfib 11] 10000
]
halt
############### END OF CODE ###############
---------------------
Renaud GOMBERT - www.essentiel.net
[2/5] from: greggirwin:mindspring at: 5-Feb-2003 11:38
Thanks Renaud!
Good stuff, and if you put the function in a context with ACCU as a
word in the context, you can avoid it being a global word.
-- Gregg
[3/5] from: joel:neely:fedex at: 5-Feb-2003 13:54
Hi, Gregg and Renaud,
Gregg Irwin wrote:
> Good stuff, and if you put the function in a context with ACCU as a
> word in the context, you can avoid it being a global word.
>
It's not necessary to use an object. Simply define ACCU as /LOCAL and
let the persistence of literal values take care of the rest. That
way ACCU isn't global either.
-jn-
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
Atlanta, Ga. - Scientists at the Centers for Disease Control today
confirmed that hoof-and-mouth disease cannot be spread by Microsoft's
Outlook email application, believed to be the first time the program
has ever failed to propagate a major virus.
[4/5] from: rgombert:essentiel at: 5-Feb-2003 21:10
From: "Gregg Irwin" <[greggirwin--mindspring--com]
>> Thanks Renaud!
> Good stuff, and if you put the function in a context with ACCU as a
> word in the context, you can avoid it being a global word.
Yes, it's a way ;-)
In fact i just forgotten to include 'ACCU in the local variable definition
block :
fastfib: function [n /release][r accu][
function_body
]
Just for those who haven't tried the script :
* slowfib 35 : need about 49 seconds to return on my PC
* fastfib/release 35 : can be run 170000 times winthin 49 seconds
* fastfib 35 (not releasing each time) run 170000 times in 0.4 s
--------------------------------
Renaud GOMBERT - www.essentiel.net
[5/5] from: greggirwin:mindspring at: 5-Feb-2003 14:08
Hi Joel,
JN> It's not necessary to use an object. Simply define ACCU as /LOCAL and
JN> let the persistence of literal values take care of the rest. That
JN> way ACCU isn't global either.
DOH! Of course, he's not COPYing the initial block. Thanks for
catching me.
-- Gregg