Velocity Reviews > C++ > Fibonacci numbers

# Fibonacci numbers

dleecurt@cc.usu.edu
Guest
Posts: n/a

 10-10-2003
Hello, I have a small problem, I am trying to write a program that
will calculate the Fibonacci number series, and I have the code
complete with one problem. I used a long in to store the numbers, and
when the numbers get too large it maxes out the int and I can't count
any higher. I am trying to use extremely large numbers, I would like
to use up to 10^50 or so. So my question is how do I do this? I'm just
learning the language and I can't think of any way around variable
storage limitations. I would appreciate any advice.
Lee

Ryan Winter
Guest
Posts: n/a

 10-10-2003
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> Hello, I have a small problem, I am trying to write a program that
> will calculate the Fibonacci number series, and I have the code
> complete with one problem. I used a long in to store the numbers, and
> when the numbers get too large it maxes out the int and I can't count
> any higher. I am trying to use extremely large numbers, I would like
> to use up to 10^50 or so. So my question is how do I do this? I'm just
> learning the language and I can't think of any way around variable
> storage limitations. I would appreciate any advice.
> Lee

use a double is probably the easiest as you get 52 bits of accuracy.
Otherwise maybe an __in64.

Ryan

Joost Ronkes Agerbeek
Guest
Posts: n/a

 10-10-2003
You will have to write your own class for that and overload the arithmic
operators, especially the + in your case.

Of course there is the question of how to store the number. One way to do
it, is to store it as a string. It might not be the most efficient way in
terms of memory and speed, but it does make the implementation
straight-forward. Initialization is also clean, just write:
Huge("123456789");

Another way to do it is to use multiple ints (or longs) to store the number.
You could probably implement this more efficiently than with strings, but I
think it makes the code a bit more complicated.

hth,
Joost

Ryan Winter
Guest
Posts: n/a

 10-10-2003
Ryan Winter wrote:

> use a double is probably the easiest as you get 52 bits of accuracy.
> Otherwise maybe an __in64.

__int64

Sam Holden
Guest
Posts: n/a

 10-10-2003
On Fri, 10 Oct 2003 15:20:27 +0800,
Ryan Winter <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
>> Hello, I have a small problem, I am trying to write a program that
>> will calculate the Fibonacci number series, and I have the code
>> complete with one problem. I used a long in to store the numbers, and
>> when the numbers get too large it maxes out the int and I can't count
>> any higher. I am trying to use extremely large numbers, I would like
>> to use up to 10^50 or so. So my question is how do I do this? I'm just
>> learning the language and I can't think of any way around variable
>> storage limitations. I would appreciate any advice.
>> Lee

>
> use a double is probably the easiest as you get 52 bits of accuracy.
> Otherwise maybe an __in64.

Those won't be useful since 167 bits are needed for 10^50.

A reasonably simple cless could be written to represent such a number,
or an existing implementation of arbitrary precision numbers.

--
Sam Holden

Karl Heinz Buchegger
Guest
Posts: n/a

 10-10-2003

(E-Mail Removed) wrote:
>
> Hello, I have a small problem, I am trying to write a program that
> will calculate the Fibonacci number series, and I have the code
> complete with one problem. I used a long in to store the numbers, and
> when the numbers get too large it maxes out the int and I can't count
> any higher. I am trying to use extremely large numbers, I would like
> to use up to 10^50 or so. So my question is how do I do this? I'm just
> learning the language and I can't think of any way around variable
> storage limitations. I would appreciate any advice.
> Lee

Search the web for some big number library.
Eg.

Search text: "BigNum C++"

--
Karl Heinz Buchegger
(E-Mail Removed)

Chris Theis
Guest
Posts: n/a

 10-10-2003

"Sam Holden" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed). ..
> On Fri, 10 Oct 2003 15:20:27 +0800,
> Ryan Winter <(E-Mail Removed)> wrote:
> > (E-Mail Removed) wrote:
> >> Hello, I have a small problem, I am trying to write a program that
> >> will calculate the Fibonacci number series, and I have the code
> >> complete with one problem. I used a long in to store the numbers, and
> >> when the numbers get too large it maxes out the int and I can't count
> >> any higher. I am trying to use extremely large numbers, I would like
> >> to use up to 10^50 or so. So my question is how do I do this? I'm just
> >> learning the language and I can't think of any way around variable
> >> storage limitations. I would appreciate any advice.
> >> Lee

> >
> > use a double is probably the easiest as you get 52 bits of accuracy.
> > Otherwise maybe an __in64.

>
> Those won't be useful since 167 bits are needed for 10^50.
>
> A reasonably simple cless could be written to represent such a number,
> or an existing implementation of arbitrary precision numbers.
>

A very common way to solve this problem is either splitting or representing
the numbers as a string. For a simple example how you could do this take a
look at http://www.codeproject.com/cpp/largenumber.asp

HTH
Chris

Ivan Vecerina
Guest
Posts: n/a

 10-10-2003
"Joost Ronkes Agerbeek" <(E-Mail Removed)> wrote in message
news:3f865d99\$0\$58700\$(E-Mail Removed)4all.nl...
| You will have to write your own class for that and overload the arithmic
| operators, especially the + in your case.
|
| Of course there is the question of how to store the number. One way to do
| it, is to store it as a string. It might not be the most efficient way in
| terms of memory and speed, but it does make the implementation
| straight-forward. Initialization is also clean, just write:
| Huge("123456789");
|
| Another way to do it is to use multiple ints (or longs) to store the
number.
| You could probably implement this more efficiently than with strings, but
I
| think it makes the code a bit more complicated.

Not necessarily more complicated.
Instead of using characters to represent decimal digits, you can use
short integers that store a base 10000 digit (0 to 9999).
(this keeps the product of two such digits in range for 'long').
It is easier than dealing with characters, as you don't need to offset
the values by '0' everywhere. Printing the number is also simple enough.

Also, for many computations, it is easier to manipulate the numbers in
little-endian format (units to the left/lower adresses), rather than
the way that we write numbers in strings (units at the end).

std::vector<int> is an option to store such a number...

Regards,
--
http://ivan.vecerina.com

Alex Vinokur
Guest
Posts: n/a

 10-10-2003

"Sam Holden" <(E-Mail Removed)> wrote in message news:(E-Mail Removed). ..
> On Fri, 10 Oct 2003 15:20:27 +0800,
> Ryan Winter <(E-Mail Removed)> wrote:
> > (E-Mail Removed) wrote:
> >> Hello, I have a small problem, I am trying to write a program that
> >> will calculate the Fibonacci number series, and I have the code
> >> complete with one problem. I used a long in to store the numbers, and
> >> when the numbers get too large it maxes out the int and I can't count
> >> any higher. I am trying to use extremely large numbers, I would like
> >> to use up to 10^50 or so. So my question is how do I do this? I'm just
> >> learning the language and I can't think of any way around variable
> >> storage limitations. I would appreciate any advice.
> >> Lee

> >
> > use a double is probably the easiest as you get 52 bits of accuracy.
> > Otherwise maybe an __in64.

>
> Those won't be useful since 167 bits are needed for 10^50.
>
> A reasonably simple cless could be written to represent such a number,
> or an existing implementation of arbitrary precision numbers.
>
> --
> Sam Holden
>

Computing Very Long Fibonacci Numbers (for instance Fibonacci[5,000,000]) :
http://alexvn.freeservers.com/s1/fibonacci.html

=====================================
Alex Vinokur
(E-Mail Removed)
http://mathforum.org/library/view/10978.html
=====================================

dleecurt@cc.usu.edu
Guest
Posts: n/a

 10-11-2003
Here is the code that I wrote, It is quite simple. Dose anyone have
and advice on fixing it.I am compiling it under Linux with gcc.

#include<iostream.h>

int main(void)
{
long fib1 = 1;
long fib2 = 1;
long fib3;
long fib4;

while (fib4 < 400000000)
{
fib3 = fib1 + fib2;
fib4 = fib3 + fib2;
fib1 = fib3;
fib2 = fib4;

cout << fib3 << endl;
cout << fib4 << endl;
}
return 0;
}

I would appriciate any advice or examples on how make the code do what
I want.
Lee