# Fibonacci numbers

Discussion in 'C++' started by dleecurt@cc.usu.edu, Oct 10, 2003.

1. ### Guest

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 ;-)

, Oct 10, 2003

2. ### Ryan WinterGuest

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

Ryan Winter, Oct 10, 2003

3. ### Joost Ronkes AgerbeekGuest

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

Joost Ronkes Agerbeek, Oct 10, 2003
4. ### Ryan WinterGuest

Ryan Winter wrote:

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

__int64

Ryan Winter, Oct 10, 2003
5. ### Sam HoldenGuest

On Fri, 10 Oct 2003 15:20:27 +0800,
Ryan Winter <> wrote:
> 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

Sam Holden, Oct 10, 2003
6. ### Karl Heinz BucheggerGuest

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

Karl Heinz Buchegger, Oct 10, 2003
7. ### Chris TheisGuest

"Sam Holden" <> wrote in message
news:...
> On Fri, 10 Oct 2003 15:20:27 +0800,
> Ryan Winter <> wrote:
> > 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

Chris Theis, Oct 10, 2003
8. ### Ivan VecerinaGuest

"Joost Ronkes Agerbeek" <> wrote in message
news:3f865d99\$0\$58700\$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

Ivan Vecerina, Oct 10, 2003
9. ### Alex VinokurGuest

"Sam Holden" <> wrote in message news:...
> On Fri, 10 Oct 2003 15:20:27 +0800,
> Ryan Winter <> wrote:
> > 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
mailto:
http://mathforum.org/library/view/10978.html
=====================================

Alex Vinokur, Oct 10, 2003
10. ### Guest

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

, Oct 11, 2003
11. ### rossumGuest

On 10 Oct 2003 18:02:07 -0700, wrote:

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

#include <iostream>
>
>int main(void)

int main()
>{
> 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;

fib3 = fib1 + fib2;
fib4 = fib3 + fib2;
fib1 = fib3;
fib2 = fib4;

std::cout << fib3 << std::endl;
std::cout << fib4 << std::endl;
> }
> return 0;
>}
>
>I would appriciate any advice or examples on how make the code do what
>I want.
>Lee

Lee,

I don't know exactly how much you know so my apologies if this is at
the wrong level for you. First three minor points:

1 Replace <iostream.h> with <iostream>. The ".h" headers are
non-standard and only for backward compatibility so new code should
avoid them. With the standard headers everything is declared in the
std namespace so you will need "std::cout" and so on.

2 int main(void) is unusual style, int main() is more usual. Using
void like that looks like C rather than C++.

3 You are not indentating the body of your while loop.

The major point is that you cannot fit anything into a long beyond the
maximum you have already reached. You will have to create your own
big integer class to hold larger numbers. Other people have already
made some suggestions as to how you might implement it.

Looking at your code you only do six things with your fib# variables:
you declare them, assign to them from a long, assign to them from each
other, compare them to 400000000, add them and output them. There is
also an implicit destruction when they go out of scope. Your big
integer class will have to do those six things and possibly have a
Destructor as well depending on the implementation you pick.

You will need to implement:

Constructor
Destructor [if needed]
operator= [assign from a long]
operator= [assign from a big integer]
operator+
operator<
operator<< [stream output, not a bit shift]

You will need to decide on the details of your chosen implementation
and provide at least the six or seven functions needed for the minimal
big integer class. Make sure you know how big the largest number you
want to hold is. You mentioned 10^50 which has 51 digits; Fib(5000)
has over 1000 digits.

Lastly, there is at least one extra function that you are going to
need for your class. It is not something that you actually do in your
code, but it is implied by what you have written. I am sure that you
will notice it once you start to try out your new class.

rossum

--

The Ultimate Truth is that there is no Ultimate Truth

rossum, Oct 12, 2003
12. ### Agent MulderGuest

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

</>

Here you have a recursive fibonacci generator:

#include <iostream>
#include <string>
static const int N=21;
int fibonacci(int a)
{
return
a==0?0:
a==1?1:
a==2?1:
fibonacci(a-1)+fibonacci(a-2);
}
int main()
{
cout<<
"Fibonacci and the original problem about rabbits where the series \n\
first appears, the family trees of cows and bees, the golden ratio \n\
and the Fibonacci series, the Fibonacci Spiral and sea shell \n\
shapes, branching plants, flower petal and seeds, leaves and petal \n\
arrangements, on pineapples and in apples, pine cones and leaf \n\
arrangements. All involve the Fibonacci numbers - and here's how \n\
and why. \n\n\
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html \n";
for(int a=0;a<N;a++)cout<<"\nFibonacci("<<a<<")\t"<<fibonacci(a);
return 0;
}

Agent Mulder, Oct 13, 2003
13. ### Dietmar KuehlGuest

"Agent Mulder" <> wrote:
> <Lee>
> > I am trying to use extremely large numbers, I would like
> > to use up to 10^50 or so.

> Here you have a recursive fibonacci generator:

It is really a brilliant idea to use a recursive function for huge
Fibonacci numbers! For one it really solves the problem of how to
represent the result in the first place and it is also blindingly
fast. I'm really impressed.

To make things a little bit more constructive: below is a solution
to the actual problem. Still not the fastest one, though.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

struct Int
{
enum { base = 10 };
typedef std::vector<unsigned char> Cont;
typedef Cont::const_iterator Cit;
Int(unsigned int i): r(1, i % base) {
while (i /= base) r.push_back(i % base);
}

std:stream& print(std:stream& out) const {
std::copy(r.rbegin(), r.rend(),
std:stream_iterator<int>(out));
return out;
}

Int& operator+= (Int const& i) {
Cont t;
unsigned char c = 0;
for (Cit b1 = r.begin(), e1 = r.end(),
b2 = i.r.begin(), e2 = i.r.end();
b1 != e1 || b2 != e2 || c; c /= base)
t.push_back((c += (b1!=e1?*b1++:0)
+ (b2!=e2?*b2++:0)) % base);
t.swap(r);
return *this;
}
private:
Cont r;
};

std:stream&
operator<< (std:stream& out, Int const& i) {
return i.print(out);
}

Int operator+ (Int const& i1, Int const& i2) {
return Int(i1) += i2;
}

int main()
{
Int a[] = { Int(1), Int(0) };

for (int i = 0; i < 500; ++i)
std::cout << (a[i%2] = a[0] + a[1]) << '\n';
}
--
<mailto:> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>

Dietmar Kuehl, Oct 14, 2003
14. ### Agent MulderGuest

<Lee>
> I would appreciate any advice.

</>

And here is a class based recursive fibonacci generator:

#include <iostream>
#include <string>
static const int N=21;
class Fibonacci
{
public:Fibonacci(int a)
:
result
(
a==0?0:
a==1?1:
a==2?1:
Fibonacci(a-1)+Fibonacci(a-2)
)
{
}
publicperator int(){return result;}
private:int result;
};
int main()
{
cout<<
"Fibonacci and the original problem about rabbits where the series \n\
first appears, the family trees of cows and bees, the golden ratio \n\
and the Fibonacci series, the Fibonacci Spiral and sea shell \n\
shapes, branching plants, flower petal and seeds, leaves and petal \n\
arrangements, on pineapples and in apples, pine cones and leaf \n\
arrangements. All involve the Fibonacci numbers - and here's how \n\
and why. \n\n\
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html \n";
for(int a=0;a<N;a++)cout<<"\nFibonacci("<<a<<")\t"<<Fibonacci(a);
return 0;
}

Agent Mulder, Oct 14, 2003
15. ### Agent MulderGuest

<Dietmar Kuehl>
> I'm really impressed.
>
> To make things a little bit more constructive: below is a solution
> to the actual problem. Still not the fastest one, though.

</>

Here is a very fast fibonacci generator for very large numbers:

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
ostream_iterator<int>out(cout,"");
int dv(int a,int b){return a/10+b;}
int md(int a){return a%10;}
int sm(int a,int b){return a+b;}
struct LongInt
{
vector<int>V;
vector<int>&v;
LongInt(int a=0):v(V){do v.push_back(a%10);while((a/=10)!=0);}
void swap(const LongInt&a)
{
vector<int>&b=v;
v=a.v;
a.v=b;
}
void set(const LongInt&a,const LongInt&b)
{
v.resize(a.v.size());
copy(a.v.begin(),a.v.end(),v.begin());
v.resize(a.v.size()<b.v.size()?b.v.size():a.v.size());
transform(b.v.begin(),b.v.end(),v.begin(),v.begin(),sm);
transform(v.begin(),v.end()-1,v.begin()+1,v.begin()+1,dv);
transform(v.begin(),v.end()-1,v.begin(),md);
if(v[v.size()-1]>10)
{
int c=v[v.size()-1]/10;
v[v.size()-1]%=10;
v.push_back(c);
}}
void print()
{
copy(v.rbegin(),v.rend(),out);
cout<<endl;
}};
struct Fibonacci
{
LongInt first;
LongInt second;
LongInt third;
Fibonacci(int a)
:
first(0),
second(1),
third(1)
{
for(int b=0;b<a;b++)
{
first.print();
first.swap(second);
second.swap(third);
third.set(second,first);
}}};
int main()
{
Fibonacci(500);
}

Agent Mulder, Oct 14, 2003
16. ### Agent MulderGuest

<Dietmar Kuehl>
>> I'm really impressed.

</>

<Agent Mulder>
>Here is a very fast fibonacci generator for very large numbers:

</>

<Chris Dams>
This is not fast at all. [SNIP] ...what about indentation and
function names that describe what the function is doing?
</>

Hi Chris,

As to speed, I understand that you can do better. Show us. I didn't run
out of ideas yet.

-X

Agent Mulder, Oct 15, 2003
17. ### Chris DamsGuest

Hello,

"Agent Mulder" <> writes:

><Dietmar Kuehl>
>> I'm really impressed.
>>
>> To make things a little bit more constructive: below is a solution
>> to the actual problem. Still not the fastest one, though.

></>

>Here is a very fast fibonacci generator for very large numbers:

This is not fast at all. Since when is storing each decimal digits of a
number an efficient way? Perhaps Agent Mulder should have substituted each
occurance of 10 in his code by the const int
number_of_fingers_of_a_human_being, so that the rest of us could have set
this to a more reasonable value then 10. Also what about indentation and
function names that describe what the function is doing?

Bye,
Chris Dams

Chris Dams, Oct 15, 2003
18. ### Chris DamsGuest

Hello,

"Agent Mulder" <> writes:

><Agent Mulder>
>>Here is a very fast fibonacci generator for very large numbers:

></>

><Chris Dams>
> This is not fast at all. [SNIP] ...what about indentation and
>function names that describe what the function is doing?
></>

>As to speed, I understand that you can do better. Show us. I didn't run
>out of ideas yet.

Well, as I already suggested, try your own program with the 10 replaced
by something reasonable. What about 2^{number of bits in int in your
implementation-2}? Another idea is to use the closed formula for the
nth Fibonacci number. If you only need one Fibonacci number with n large,
I would suspect this to be much faster, but that statement would need some
testing that I do not feel very much inclined to do. This is because this
formula involves two real numbers to the power n. It would depend on how
fast you can calculate this power. I bet there exist nice tricks for this.
Generally, I would not write my own arbitrary precision class, but use
some library like gmp. These libraries will know about the "nice tricks" I

Bye,
Chris Dams

Chris Dams, Oct 15, 2003
19. ### Agent MulderGuest

<Chris Dams>
>This is not fast at all. [SNIP]

</>

<Agent Mulder>
>As to speed, I understand that you can do better. Show us.

</>

<Chris Dams>
>that statement would need some testing that I do not feel very much inclined to do.

</>

This is an improved version of the Fibonacci generator for very large numbers
that I posted yesterday.

#include<iostream>
#include<algorithm>
#include<vector>
const static base=10;
inline int dv(int a,int b){return a/base+b;}
inline int md(int a){return a%base;}
inline int sm(int a,int b){return a+b;}
struct LongInt
{
vector<int>v;
LongInt(int a=0){do v.push_back(a%base);while((a/=base)!=0);}
void swap(LongInt&a){v.swap(a.v);}
void plus(const LongInt&a)
{
v.resize(v.size()<a.v.size()?a.v.size():v.size());
transform(a.v.begin(),a.v.end(),v.begin(),v.begin(),sm);
transform(v.begin(),v.end()-1,v.begin()+1,v.begin()+1,dv);
transform(v.begin(),v.end()-1,v.begin(),md);
if(v[v.size()-1]>=base)
{
int c=v[v.size()-1]/base;
v[v.size()-1]%=base;
v.push_back(c);
}}
void print()
{
copy(v.rbegin(),v.rend(),ostream_iterator<int>(cout));
cout<<endl;
}};
struct Fibonacci
{
LongInt first,second;
Fibonacci(int a):first(0),second(1)
{
for(int b=0;b<a;b++)
{
first.print();
first.swap(second);
second.plus(first);
}}};
int main()
{
Fibonacci(5000);
return 0;
}

Agent Mulder, Oct 15, 2003
20. ### Alex VinokurGuest

"Agent Mulder" <> wrote in message news:bmkbar\$2to\$1.nb.home.nl...
> <Chris Dams>
> >This is not fast at all. [SNIP]

> </>
>
> <Agent Mulder>
> >As to speed, I understand that you can do better. Show us.

> </>
>
> <Chris Dams>
> >that statement would need some testing that I do not feel very much inclined to do.

> </>
>
> This is an improved version of the Fibonacci generator for very large numbers
> that I posted yesterday.
>
> #include<iostream>
> #include<algorithm>
> #include<vector>
> const static base=10;
> inline int dv(int a,int b){return a/base+b;}
> inline int md(int a){return a%base;}
> inline int sm(int a,int b){return a+b;}
> struct LongInt
> {
> vector<int>v;
> LongInt(int a=0){do v.push_back(a%base);while((a/=base)!=0);}
> void swap(LongInt&a){v.swap(a.v);}
> void plus(const LongInt&a)
> {
> v.resize(v.size()<a.v.size()?a.v.size():v.size());
> transform(a.v.begin(),a.v.end(),v.begin(),v.begin(),sm);
> transform(v.begin(),v.end()-1,v.begin()+1,v.begin()+1,dv);
> transform(v.begin(),v.end()-1,v.begin(),md);
> if(v[v.size()-1]>=base)
> {
> int c=v[v.size()-1]/base;
> v[v.size()-1]%=base;
> v.push_back(c);
> }}
> void print()
> {
> copy(v.rbegin(),v.rend(),ostream_iterator<int>(cout));
> cout<<endl;
> }};
> struct Fibonacci
> {
> LongInt first,second;
> Fibonacci(int a):first(0),second(1)
> {
> for(int b=0;b<a;b++)
> {
> first.print();
> first.swap(second);
> second.plus(first);
> }}};
> int main()
> {
> Fibonacci(5000);
> return 0;
> }
>
>
>
>
>

Computing Fibonacci 1-5000

Time complexity of two algorithms was compared.

Each algorithm has been run 5 times.

--
===========================================
Windows 2000 Professional
Intel(R) Celeron(R) CPU 1.70 GHz
CYGWIN_NT-5.0 1.5.4(0.94/3/2)
GNU gcc version 3.3.1 (cygming special)
GNU time 1.7
---------------
No optimization
===========================================

-----------------------
Algorithm-1 : See above
-----------------------
[1] 17.47 real, 17.16 user, 0.19 sys
[2] 17.44 real, 17.24 user, 0.15 sys
[3] 17.46 real, 17.19 user, 0.18 sys
[4] 17.36 real, 17.15 user, 0.13 sys
[5] 17.52 real, 17.22 user, 0.15 sys

--------------------------
Algorithm-2 : http://alexvn.freeservers.com/s1/fibonacci.html
--------------------------
[1] 9.26 real, 9.00 user, 0.19 sys
[2] 9.31 real, 9.06 user, 0.21 sys
[3] 9.38 real, 9.07 user, 0.24 sys
[4] 9.35 real, 9.06 user, 0.21 sys
[5] 9.33 real, 9.00 user, 0.27 sys

--
=====================================
Alex Vinokur
mailto:
http://mathforum.org/library/view/10978.html
news://news.gmane.org/gmane.comp.lang.c++.perfometer
=====================================

Alex Vinokur, Oct 17, 2003