Re: Fibonacci Numbers?

[eachus@spectre.mitre.org (Robert I. Eachus)]

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...