From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_00,INVALID_DATE
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,55603c56db8d8307
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 1994-09-20 05:11:47 PST
Path: 
 bga.com!news.sprintlink.net!howland.reston.ans.net!europa.eng.gtefsd.com!MathWorks.Com!news.duke.edu!eff!blanket.mitre.org!linus.mitre.org!linus!mbunix!eachus
From: eachus@spectre.mitre.org (Robert I. Eachus)
Newsgroups: comp.lang.ada
Subject: Re: Fibonacci Numbers?
Date: 19 Sep 94 14:16:57
Organization: The Mitre Corp., Bedford, MA.
Message-ID: <EACHUS.94Sep19141657@spectre.mitre.org>
References: <35fl28$1h3@garuda.csulb.edu> <35gii7$3ef@crl.crl.com>
NNTP-Posting-Host: spectre.mitre.org
In-reply-to: weiqigao@crl.com's message of 17 Sep 1994 22:17:59 -0700
Date: 1994-09-19T14:16:57+00:00
List-Id: <comp.lang.ada>

In article <35gii7$3ef@crl.crl.com> weiqigao@crl.com (Weiqi Gao) writes:

 > fib(n) = 1/sqrt(5) * [ ( 1 + sqrt(5))^n - ( 1 - sqrt(5))^n ] / 2^n.

    If you re-organize this as:

    fib(n) = 1/sqrt(5) * [ ((1+sqrt(5))/2)^n - ((1-sqrt(5)/2)^n ] 

    ....substitute the constants...

    fib(n) = 0.44721... * [1.618033988...^n - (-0.618033988...)^n]

    ...and distribute:

    fib(n) = 0.44721... * 1.618033988...^n - 0.44721...* (-0.618033988...)^n

    You will notice that the absolute value of the second term
(for n = 0 or greater) is always less than 1/2.   Therefore:

    function Fibonacci(N: in Natural) return Natural is
      Sqrt_5_over_2: constant := 0.4472135955;
      Phi:           constant := 1.61803398875;
    begin
      return Integer(Sqrt_5_Over_2*Phi**N);
    end Fibonacci;

    Of course, if you want more range, use the ADAR_Integer_Types
package, or return a Float value, but as you can see, that takes more
work.  For 32 bit Integers, you might want to test this program out:

    with Text_IO; with Fibonacci;
    procedure Test_Fib is
    begin
      for I in 1..46 loop  -- chosen assuming 32 bit integers.
        Text_IO.Put_Line("Fib(" & Integer'IMAGE(I) & ") is "
            & Integer'IMAGE(Fibonacci(I)) & ".");
      end loop;
    end Test_Fib;

    By the way, if you change that 46 above, you may run into a nasty
bug in at least one version of a popular Ada compiler.  I got badly
burned by this bug over the last month, and on my list of things to do
this week was to come up with a "short" example of the bug.  Cross
that off the ToDo list!  What happens is the conversion to Integer
doesn't test for overflow, but returns Integer'LAST instead.  I'm not
sure how processor/OS specific this bug is, I was going to try it on
several machines, so if you want to report your results to me--and to
the vendor--I'll collect the results.

    Why didn't I name the vendor above?  Because I haven't gone
through the effort to determine if it is a SPARC architecture
violation in some chips, an OS run-time routine bug, or a compiler
bug.  So this may occur with more than one compiler...or it may occur
on other architectures.


--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...