Fibonacci Numbers?

Fibonacci Numbers?

[S. Hegede]

Hey!  I'm an a beginning Ada programmer and I've been stuck for a while
on trying to write a program in which a user can get the number in a
Fibonacci series( Ex.  1,1,2,3,5,8,13,21...) by typing its position in
the series.  I only need help on getting the formula down that would
calculate the next number in the series.  Thanks for the help.
.

Re: Fibonacci Numbers?

[Weiqi Gao]

In article <35fl28$1h3@garuda.csulb.edu>, S. Hegede <zoltan@csulb.edu> wrote:
>
>Hey!  I'm an a beginning Ada programmer and I've been stuck for a while
>on trying to write a program in which a user can get the number in a
>Fibonacci series( Ex.  1,1,2,3,5,8,13,21...) by typing its position in
>the series.  I only need help on getting the formula down that would
>calculate the next number in the series.  Thanks for the help.
>.
>
>


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

\/\/eiqi Gao
weiqigao@crl.com

Re: Fibonacci Numbers?

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

Re: Fibonacci Numbers?

[Philip Brashear]

In article <35gii7$3ef@crl.crl.com> weiqigao@crl.com (Weiqi Gao) writes:
>In article <35fl28$1h3@garuda.csulb.edu>, S. Hegede <zoltan@csulb.edu> wrote:
>>
>>Hey!  I'm an a beginning Ada programmer and I've been stuck for a while
>>on trying to write a program in which a user can get the number in a
>>Fibonacci series( Ex.  1,1,2,3,5,8,13,21...) by typing its position in
>>the series.  I only need help on getting the formula down that would
>>calculate the next number in the series.  Thanks for the help.
>>.
>>
>>
>
>
>fib(n) = 1/sqrt(5) * [ ( 1 + sqrt(5))^n - ( 1 - sqrt(5))^n ] / 2^n.
>
>\/\/eiqi Gao
>weiqigao@crl.com


I'd be willing to bet that the assignment's intent was that the program
use the "standard" recursive definition of Fib:

  Fib (1) = 1
  Fib (2) = 1
  For N > 2, Fib (N) = Fib (N-1) + Fib (N-2)

At least that's where I always used the Fibonacci sequence: in showing
a non-trivial recursively defined function.

Phil Brashear

Re: Fibonacci Numbers?

[Robert Firth]

In article <35fl28$1h3@garuda.csulb.edu> zoltan@csulb.edu (S. Hegede) writes:

>Hey!  I'm an a beginning Ada programmer and I've been stuck for a while
>on trying to write a program in which a user can get the number in a
>Fibonacci series( Ex.  1,1,2,3,5,8,13,21...) by typing its position in
>the series.  I only need help on getting the formula down that would
>calculate the next number in the series.  Thanks for the help.

F0 = 0; F1 = 1; Fn = Fn-1 + Fn-2

There's also a closed form, but since it involves exponentiation
of real numbers it's probably faster to compute via the recurrence
formula.

Re: Fibonacci Numbers?

[Keith Thompson @pulsar]

In <35fl28$1h3@garuda.csulb.edu> zoltan@csulb.edu (S. Hegede) writes:
> Hey!  I'm an a beginning Ada programmer and I've been stuck for a while
> on trying to write a program in which a user can get the number in a
> Fibonacci series( Ex.  1,1,2,3,5,8,13,21...) by typing its position in
> the series.  I only need help on getting the formula down that would
> calculate the next number in the series.

It's 34.

>                                           Thanks for the help.

You're welcome.

8-)} 8-)} 8-)} 8-)}

-- 
Keith Thompson (The_Other_Keith)  kst@alsys.com
TeleSoft^H^H^H^H^H^H^H^H Alsys, Inc.
10251 Vista Sorrento Parkway, Suite 300, San Diego, CA, USA, 92121-2718
/user/kst/.signature: I/O error (core dumped)

Re: Fibonacci Numbers?

[Robert Dewar]

Keith, I can't believe you would make such a mistake, 34 indeed, doesn't
everyone know that THE ANSWER is 42.

By the way, I have a suggestion. When people
ask a truly elementary question, defined as one which
we can pretty much assume that all the readers of the newsgroup know the
answer to, then it's probably better to EMAIL responses, we have now had
half a dozen posts giving the formula for Fibonacci numbers, which is not
very enlightening.

Now if someone knows the question to which 42 is the answer, that would
be really interesting and worth posting, though probably not to this
newsgroup.

Re: Fibonacci Numbers?

[David Weller]

In article <35n2ec$5ng@gnat.cs.nyu.edu>, Robert Dewar <dewar@cs.nyu.edu> wrote:
>Keith, I can't believe you would make such a mistake, 34 indeed, doesn't
>everyone know that THE ANSWER is 42.
>
(Raising hand, waving frantically)  I do! I do! :-)

>By the way, I have a suggestion. When people
>ask a truly elementary question, defined as one which
>we can pretty much assume that all the readers of the newsgroup know the
>answer to, then it's probably better to EMAIL responses, we have now had
>half a dozen posts giving the formula for Fibonacci numbers, which is not
>very enlightening.
>
Better still, it amazes me that nobody said, "Um, was this problem
assigned for a programming project?"  It just seemed so damn basic to
me.  Of course, Rob E.'s clever algorithm was interesting (yeah,
yeah, I'm sure it can be found in any NM cookbook :-)

>Now if someone knows the question to which 42 is the answer, that would
>be really interesting and worth posting, though probably not to this
>newsgroup.
>
Yup...maybe I should set Followup To to "alt.fan.douglas-adams" :-)


-- 
Proud (and vocal) member of Team Ada! (and Team OS/2)        ||This is not your
             Ada 9X -- It doesn't suck                       ||  father's Ada
For all sorts of interesting Ada 9X tidbits, run the command:||________________
"finger dweller@starbase.neosoft.com | more" (or e-mail with "finger" as subj.)
   ObNitPick: Spelling Ada as ADA is like spelling C++ as CPLUSPLUS. :-) 

Re: Fibonacci Numbers?

[Joseph Skinner]

In article <35n2ec$5ng@gnat.cs.nyu.edu> dewar@cs.nyu.edu (Robert Dewar) writes:
>Keith, I can't believe you would make such a mistake, 34 indeed, doesn't
>everyone know that THE ANSWER is 42.
>
>By the way, I have a suggestion. When people
>ask a truly elementary question, defined as one which
>we can pretty much assume that all the readers of the newsgroup know the
>answer to, then it's probably better to EMAIL responses, we have now had
>half a dozen posts giving the formula for Fibonacci numbers, which is not
>very enlightening.
>
>Now if someone knows the question to which 42 is the answer, that would
>be really interesting and worth posting, though probably not to this
>newsgroup.
>

From memory that would have to be 6*9
which as an interesting aside 6*9=13#42#

Joe.

--
===============================================================================
Joseph Skinner                      | Invercargill
usenet: joe@jsnode.equinox.gen.nz   | New Zealand

There is no such thing as a wizard who minds his own business
                          - Berengis the Black
                            Court Mage to the Earl Caeline

Re: Fibonacci Numbers?

[Jeffrey J. Hallman]

In article <35n2ec$5ng@gnat.cs.nyu.edu> dewar@cs.nyu.edu (Robert Dewar) writes:
   Now if someone knows the question to which 42 is the answer, that would
   be really interesting and worth posting, though probably not to this
   newsgroup.

Sure. Isn't it The Meaning of Life, the Universe, and Everything?

Jeff Hallman

Re: Fibonacci Numbers?

[pk]

In article <35fl28$1h3@garuda.csulb.edu>, zoltan@csulb.edu (S. Hegede) says:
> I only need help on getting the formula down that would
>calculate the next number in the series.

f(n+1) = f(n) + f(n-1)