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

Fibonaccio - Was: Report on WinCE Rebol --- Speed Comparison

 [1/8] from: joel::neely::fedex::com at: 28-Jun-2001 23:55


Hi, Bard, Bard Papegaaij wrote:
> David Ness wrote: > >
<<quoted lines omitted: 6>>
> Mmmmm. I didn't know about that one? Any pointers I could > follow up?
How about the function? ;-) fibr: func [n [integer!] /local sr5] [ sr5: square-root 5.0 ((0.5 * (1.0 + sr5)) ** n) - ((0.5 * (1.0 - sr5)) ** n) / sr5 ] (Remember that REBOL ignores operator precedence, so the division is applied to the difference.) -jn- -- ------------------------------------------------------------ Programming languages: compact, powerful, simple ... Pick any two! joel'dot'neely'at'fedex'dot'com

 [2/8] from: bard:papegaaij:austarnet:au at: 29-Jun-2001 20:57


Hi Joe, You wrote:
>How about the function? ;-) > fibr: func [n [integer!] /local sr5] [
<<quoted lines omitted: 4>>
>(Remember that REBOL ignores operator precedence, so the >division is applied to the difference.)
Your erudition never ceases to amaze me! I didn't know anything about this possibility (I'm a poet, not a mathematician ;-). However, despite its obviously misguided aims and assumptions, my function DID teach me a lot about programming in REBOL. Thanks for the information. Bard -jn- -- ------------------------------------------------------------ Programming languages: compact, powerful, simple ... Pick any two! joel'dot'neely'at'fedex'dot'com

 [3/8] from: joel:neely:fedex at: 29-Jun-2001 1:05


Bard Papegaaij wrote:
> (I'm a poet, not a mathematician ;-). >
Ah, but Mathematics *IS* poetry, just in a different language! (PS: Of course, so is programming, as it's a branch of applied Mathematics! ;-) -jn- -- ------------------------------------------------------------ Programming languages: compact, powerful, simple ... Pick any two! joel'dot'neely'at'fedex'dot'com

 [4/8] from: dness:home at: 29-Jun-2001 9:22


Bard Papegaaij wrote:
> I understand completely. It was just that I saw you using the fib function, > and
<<quoted lines omitted: 9>>
> Regards, > Bard
No problem. I figure the thread is `ours' not `mine'. I just wanted to make sure it was clear I wasn't making any claims for it being a `good' fibonacci evaluatior. And `analysis' is always interesting when you can do it in any particular situation.

 [5/8] from: ryanc:iesco-dms at: 29-Jun-2001 8:52


Mathematics is an interpetation of reality, programming is a reality of interpetation. At least it sounds good anyways, --Ryan Joel Neely wrote:
> Bard Papegaaij wrote: > >
<<quoted lines omitted: 13>>
> [rebol-request--rebol--com] with "unsubscribe" in the > subject, without the quotes.
-- Ryan Cole Programmer Analyst www.iesco-dms.com 707-468-5400

 [6/8] 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

 [7/8] from: dness:home at: 29-Jun-2001 1:36


Bard Papegaaij wrote:
> Hi, > I noticed you are using a recursive fibonaccio function to measure speed on
<<quoted lines omitted: 3>>
> - an iterating definition instead of the recursive one to get rid of stack > overflows;
[snip] ... If one were actually interested in generating fibonacci numbers then neither recursion nor iteration nor memory functions are needed as there is, IIRC, a straightforward closed form for the fibonnaci which would evaluate for any N at the cost of a couple of logs and a couple of exponentials. The objective here was, of course, to compare the machines and thus we wanted to use functions that consumed some detectable amount of time. Trying to make those functions `efficient' doesn't, it is clear, make sense for that purpose.

 [8/8] from: bard:papegaaij:austarnet:au at: 29-Jun-2001 15:59


David Ness wrote:
>Bard Papegaaij wrote: >> >> 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; >[snip] >... > >If one were actually interested in generating fibonacci numbers then
neither
>recursion nor iteration nor memory functions are needed as there is, IIRC, >a straightforward closed form for the fibonnaci which would evaluate for >any N at the cost of a couple of logs and a couple of exponentials.
Mmmmm. I didn't know about that one? Any pointers I could follow up? As far as I know, the fibanoccio series approximates - but never quite reaches - a true logarithmic progression. A solution using logs and exponentials sounds interesting.
>The objective here was, of course, to compare the machines and thus we
wanted
>to use functions that consumed some detectable amount of time. Trying to >make those functions `efficient' doesn't, it is clear, make sense for that >purpose.
I understand completely. It was just that I saw you using the fib function, and thought it would be nice to share my attempts at coding the same function using a number of different 'solutions' for some of the problems posed by that simple recursive definition (speed, inability to calculate higher than fib 42, stack overflow). Sorry if I have thrown you off track by 'hi-jacking' your thread for something like this. It won't happen again I ('m not sure I can) promise ;-). Regards, Bard

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted