🚀 go-pugleaf

JRS:  In article <7ffeoa$avs$1@nnrp1.dejanews.com> of Mon, 19 Apr 1999
14:31:38 in news:borland.public.turbopascal, Robert AH Prins
<prinsra@williscorroon.com> wrote:
>In article <371B0391.E3122AD7@central.ntua.gr>,
>  elhadzil@central.ntua.gr wrote:
>> 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.
 
-- 
 � John Stockton, Surrey, UK.  jrs@merlyn.demon.co.uk   Turnpike v4.00   MIME. �
  Web <URL: http://www.merlyn.demon.co.uk/> - TP/BP/&c. FAQqish topics & links.
  Timo's TurboPascal <A HREF="ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip">FAQ</A>.
  <A HREF="http://www.merlyn.demon.co.uk/clpb-faq.txt">Mini-FAQ</A> of c.l.p.b.