Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search

[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