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