[REBOL] Re: Fibonaccio - Was: Report on WinCE Rebol --- Speed Comparison

From: bard:papegaaij:austarnet:au at: 29-Jun-2001 14:32

Hi,

I noticed you are using a recursive fibonaccio function to measure speed on
different platforms. Some time ago I implemented a fibonaccio generator as a
way of learning various aspects of REBOL. Features I used are:
- an object to store the function and some house-keeping variables;
- an iterating definition instead of the recursive one to get rid of stack
overflows;
- working internally with reals instead of integers to be able to generate
really BIG numbers;
- storing calculated results in an internal 'memory-list' to greatly speed
up calculations (at the cost of memory space off course).
Personally I was surprised at both the ease in which I could implement all
this in REBOL (it was one of the first things I attempted) and the speed of
calculation achieved. Try to time fib 35 from below and then do the same
with f! 35! REBOL doesn't even show any elapsed time for the latter case on
my machine. And for any number, once it is known you'll get an instanteneous
result. I suspect that using a hashed memory-list would speed things up even
more.

So, just for fun and elucidation, here is my version of the fibonaccio
generator:

REBOL [
    Title: "Fibonaccio calculator"
    Date:  14-11-2000
    File:  %fibonaccio.r
    Versio: 1.0
    Purpose: {
        This is a simple calculator to return the fibonaccio number for any
given ordinal.
    }
    Usage: {F! integer!}
    Notes: {
        Implemented without tail-recursion, using a memory-list.
	Encapsulated in an object with private functions and variables.
    }
    History: [
        14-November-2000 "First non-recursive version"
    ]
]

Fibonaccio: make object! [
	set 'F! func [
		{
		 This function calculates the fibonaccio number for the given ordinal
using the helper functions and
		 object variables stored in the fibonaccio object.
		}
		ordinal [integer!]
	][
		ord: to-decimal ordinal
		either hi >= ord [
			get_fib ord
		][
			for count hi (ord - 1) 1 [
				add_fib (count + 1) ((get_fib (count - 1)) + (get_fib count))
			]
			get_fib ord
		]
	]
	add_fib: func [
		{
		 This is a helper function to update the memory block with the newly
calculated value.
		 It also sets the hi counter to the highest number in the memory.
		}
		one
		two
	][
		append/only (append mem one) to-block two
		hi: one
	]
	get_fib: func [
		{
		 This is a helper function that returns the fibonaccio number for the
given ordinal
		 if it is in memory, or "none" if it is not.
		}
		ordinal [decimal!]
	][
		if select mem ordinal [
			return first select mem ordinal
		]
		return none
	]
	ord:
	mem: [0.0 [0.0] 1.0 [1.0]]
	hi: 1.0
]

-----

Regards,

Bard Papegaaij

1 · 2 · 3 · 4 · 5 · [6] · 7 · 8 · See whole thread