| |
 |
|
| Computers Forum Index » Computer Languages (Misc) » Computing Fibonacci numbers the hard way... |
|
Page 1 of 1 |
|
| Author |
Message |
| Paul N... |
 Posted: Wed Jun 24, 2009 9:23 pm |
|
|
|
Guest
|
On 24 June, 02:54, c... at (no spam) tiac.net (Richard Harter) wrote:
Quote: I suppose we are all familiar with recursive definitions of
Fibonacci numbers, e.g.
<snip>
Quote: Fibonacci numbers grow exponentially as phi^n. If we want exact
results that fit in 32 or 64 bit integers then a lookup table
suffices. If we want exact results for larger n, bignums and a
more efficient algorithm is indicated. If the result does not
have to be exact the asymptotic formula is indicated.
<big snip>
I'm not entirely sure whether you're asking a question here or making
a point, let alone exactly what the question/point might be, so you
may not get many replies.
But there was one point which I wasn't sure you were mentioning. There
is an exact formula for Fibonacci numbers:
F(k) = (r ^ k - t ^ k) / (r - t)
where r = (1 + SQR(5)) / 2 and t = 1 - r.
Since the Fibonacci numbers are all integers, as long as any errors
are less than one they can be ignored.
Hope that helps.
Paul. |
|
|
| Back to top |
|
|
|
| Richard Harter... |
| Posted: Thu Jun 25, 2009 5:17 am |
|
|
|
Guest
|
On Wed, 24 Jun 2009 14:23:06 -0700 (PDT), Paul N <gw7rib at (no spam) aol.com>
wrote:
Quote: On 24 June, 02:54, c... at (no spam) tiac.net (Richard Harter) wrote:
I suppose we are all familiar with recursive definitions of
Fibonacci numbers, e.g.
snip
Fibonacci numbers grow exponentially as phi^n. =A0If we want exact
results that fit in 32 or 64 bit integers then a lookup table
suffices. =A0If we want exact results for larger n, bignums and a
more efficient algorithm is indicated. =A0If the result does not
have to be exact the asymptotic formula is indicated.
big snip
I'm not entirely sure whether you're asking a question here or making
a point, let alone exactly what the question/point might be, so you
may not get many replies.
But there was one point which I wasn't sure you were mentioning. There
is an exact formula for Fibonacci numbers:
F(k) =3D (r ^ k - t ^ k) / (r - t)
where r =3D (1 + SQR(5)) / 2 and t =3D 1 - r.
Since the Fibonacci numbers are all integers, as long as any errors
are less than one they can be ignored.
There is indeed an exact formula; the catch is that it is more
expensive to use than the doubling formula if you want an exact
result. However it is just the thing if you want a limited
precision result.
The point, if there be such, is that an elegant but apparently
useless formulation has a real use.
Richard Harter, cri at (no spam) tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
If I do not see as far as others, it is because
I stand in the footprints of giants. |
|
|
| Back to top |
|
|
|
| cr88192... |
| Posted: Thu Jun 25, 2009 10:12 am |
|
|
|
Guest
|
"Richard Harter" <cri at (no spam) tiac.net> wrote in message
news:4a42e45b.44229468 at (no spam) text.giganews.com...
Quote: On Wed, 24 Jun 2009 14:23:06 -0700 (PDT), Paul N <gw7rib at (no spam) aol.com
wrote:
On 24 June, 02:54, c... at (no spam) tiac.net (Richard Harter) wrote:
I suppose we are all familiar with recursive definitions of
Fibonacci numbers, e.g.
snip
Fibonacci numbers grow exponentially as phi^n. =A0If we want exact
results that fit in 32 or 64 bit integers then a lookup table
suffices. =A0If we want exact results for larger n, bignums and a
more efficient algorithm is indicated. =A0If the result does not
have to be exact the asymptotic formula is indicated.
big snip
I'm not entirely sure whether you're asking a question here or making
a point, let alone exactly what the question/point might be, so you
may not get many replies.
But there was one point which I wasn't sure you were mentioning. There
is an exact formula for Fibonacci numbers:
F(k) =3D (r ^ k - t ^ k) / (r - t)
where r =3D (1 + SQR(5)) / 2 and t =3D 1 - r.
Since the Fibonacci numbers are all integers, as long as any errors
are less than one they can be ignored.
There is indeed an exact formula; the catch is that it is more
expensive to use than the doubling formula if you want an exact
result. However it is just the thing if you want a limited
precision result.
The point, if there be such, is that an elegant but apparently
useless formulation has a real use.
yep...
it works good as a "first test" for a compiler or interpreter...
if a recursive fibonacci test works (and nothing breaks or blows up), this
is a good start, and off to more involved tests.
and if it breaks, then something is so fundamentally wrong with the compiler
or interpreter that there is no real point in going forwards until at least
this much works...
|
|
|
| Back to top |
|
|
|
| Aaron Gray... |
| Posted: Sun Jul 05, 2009 1:38 am |
|
|
|
Guest
|
I thought the hard way was with rocks :)
Aaron |
|
|
| Back to top |
|
|
|
|
|
All times are GMT
The time now is Sun Nov 22, 2009 12:14 pm
|
|