fibonacci programme
Author Message
fibonacci programme

do you know how can I create non-recursive programme in Pascal that will
be able to estimate every term of the Fibonacci sequence?

Wed, 18 Jun 1902 08:00:00 GMT
fibonacci programme

Quote:

> do you know how can I create non-recursive programme in pascal that will
> be able to estimate every term of the Fibonacci sequence?

An explicit representation of the members of the Fibonacci sequence is

((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n
f(n) = -------------------------------------
sqrt(5)

f(0) = 0 ; f(1)=1

Regards
Horst

Wed, 18 Jun 1902 08:00:00 GMT
fibonacci programme
Mr Kraemer,

in Pascal programming.
More specifically my source code on which I'm working Iwould like to be like
this:

program (main programme )
...
procedure FIBONACCI

((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n
f(n) = -------------------------------------
sqrt(5)

f(0) = 0 ; f(1)=1

begin (main programme)
.....
FIBONACCI(procedure)

end.

Quote:

> > do you know how can I create non-recursive programme in pascal that will
> > be able to estimate every term of the Fibonacci sequence?

> An explicit representation of the members of the Fibonacci sequence is

>                ((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n
>         f(n) = -------------------------------------
>                                sqrt(5)

>         f(0) = 0 ; f(1)=1

> Regards
> Horst

Wed, 18 Jun 1902 08:00:00 GMT
fibonacci programme

Quote:

> do you know how can I create non-recursive programme in pascal that
> will
> be able to estimate every term of the Fibonacci sequence?

You want a non-recursive program, but I assume that you don't mind
having an iterative program (one with loops).  You also say you want to
"estimate every term",
but I'm again assuming you want to list the first N terms (where N is
some reasonably
small number, such that you can represent the Nth number as an integer).

Do you know how to generate the Fibonacci sequence?  What steps do
you take?
What do you have to do to get the "next" number?  If I pointed you to
the middle of the
sequence, what would you have to know to continue?  [Feel free to use
pencil and paper

All you now have to do is translate your pencil/paper routine into
Pascal code.  Give it
a try (don't worry about writing "correct" Pascal, just put down the
steps of the algorithm,
without even worrying about correct punctuation) and show us the
results.  You'll be sure
to get suggestions for improvements, or hints for places where you get
stuck.

Bob Schor
Pascal Enthusiast

Wed, 18 Jun 1902 08:00:00 GMT
fibonacci programme

Quote:

>> do you know how can I create non-recursive programme in pascal that will
>> be able to estimate every term of the Fibonacci sequence?

>There is a closed form available to give the mathematical exact value, the one
>below! It's based on the fact that

>lim fib(n+1)/fib(n) = (sqrt(5) + 1) / 2 (aka the golden ratio)
>n->oo

>r5     = sqrt(5)
>fib(n) = (((1 + r5) ** n - ((1 - r5)) ** n)) / 2 ** n / r5

>A quick test in Rexx (which, through it's "numeric digits n" feature, offers
>precision only limited to the amount of storage you throw at it) showed that
>the above formula is correct, well at least up to n = 1000. FYI, fib(1000) =

>434665576869374564356885276750406258025646605173717804024817
>290895365554179490518904038798400792551692959225930803226347
>752096896232398733224711616429964409065331879382989696499285
>16003704476137795166849228875

From memory, that formula cannot be far from one I have known of, which
is exact.  IIRC, one only needs the first term if one rounds to the
nearest integer; that *might* not work for VERY small N, but I think it
does.

By prompt>longcalc 1000 #fn
I confirm that samples of your result match mine; happily, you have 60
digits per line as longcalc.pas gives, though that also has commas.

Of course, the original question is best answered (IMHO) by an iterative
approach, as used in longcalc.pas (which interprets the following) :

function F_fn(var SP : PLET) : boolean ; FAR ;
begin F_fn :=
RPN('(F_fn. ) wrt   /q0 fed /q1 0 def /q2 1 def', SP)
and RPN('(pop q1 q2 add  /q1 q2 def  /q2 fed) 2 q0 for ', SP)
and RPN('q2 dup wrt wln', SP) ;
end {F_fn} ;

A new longcalc.exe (BP7, DOS) should be uploaded with this.  Compiled
with DCC32, longcalc might exceed Fib(1,000,000) - in time.

--

Web <URL: http://www.merlyn.demon.co.uk/> - TP/BP/&c. FAQqish topics & links.
<A HREF="http://www.merlyn.demon.co.uk/clpb-faq.txt">Mini-FAQ</A> of c.l.p.b.

Wed, 18 Jun 1902 08:00:00 GMT
fibonacci programme
On Mon, 19 Apr 1999 19:50:39 +0100, Dr John Stockton

Quote:

> From memory, that formula cannot be far from one I have known of, which
> is exact.  IIRC, one only needs the first term if one rounds to the
> nearest integer; that *might* not work for VERY small N, but I think it
> does.

It works for every n from 1 up:

fib(n) = round ( (1+sqrt(5))^n / sqrt(5) )

Regards
Horst

Wed, 18 Jun 1902 08:00:00 GMT

 Page 1 of 1 [ 10 post ]

Relevant Pages