P: n/a

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 ;)  
Share this Question
P: n/a

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
straightforward. 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  
P: n/a
 dl******@cc.usu.edu 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  
P: n/a

Ryan Winter wrote: use a double is probably the easiest as you get 52 bits of accuracy. Otherwise maybe an __in64.
__int64 :)  
P: n/a

On Fri, 10 Oct 2003 15:20:27 +0800,
Ryan Winter <wi*********@optusnet.com.au> wrote: dl******@cc.usu.edu 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  
P: n/a
 dl******@cc.usu.edu 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. http://www.google.com
Search text: "BigNum C++"

Karl Heinz Buchegger kb******@gascad.at  
P: n/a

"Sam Holden" <sh*****@flexal.cs.usyd.edu.au> wrote in message
news:slrnbocpm4.c0l.sh*****@flexal.cs.usyd.edu.au. .. On Fri, 10 Oct 2003 15:20:27 +0800, Ryan Winter <wi*********@optusnet.com.au> wrote: dl******@cc.usu.edu 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  
P: n/a

"Joost Ronkes Agerbeek" <jo***@ronkes.nl> wrote in message
news:3f***********************@news.xs4all.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
 straightforward. 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
littleendian 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  
P: n/a

"Sam Holden" <sh*****@flexal.cs.usyd.edu.au> wrote in message news:slrnbocpm4.c0l.sh*****@flexal.cs.usyd.edu.au. .. On Fri, 10 Oct 2003 15:20:27 +0800, Ryan Winter <wi*********@optusnet.com.au> wrote: dl******@cc.usu.edu 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:al****@connect.to http://mathforum.org/library/view/10978.html
=====================================  
P: n/a

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  
P: n/a

On 10 Oct 2003 18:02:07 0700, dl******@cc.usu.edu 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
nonstandard 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  
P: n/a

<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(a1)+fibonacci(a2);
}
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...nacci/fib.html \n";
for(int a=0;a<N;a++)cout<<"\nFibonacci("<<a<<")\t"<<fibona cci(a);
return 0;
}  
P: n/a

"Agent Mulder" <mb*******************@home.nl> 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::ostream& print(std::ostream& out) const {
std::copy(r.rbegin(), r.rend(),
std::ostream_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::ostream&
operator<< (std::ostream& 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:di***********@yahoo.com> <http://www.dietmarkuehl.de/>
Phaidros eaSE  Easy Software Engineering: <http://www.phaidros.com/>  
P: n/a

<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(a1)+Fibonacci(a2)
)
{
}
public:operator 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...nacci/fib.html \n";
for(int a=0;a<N;a++)cout<<"\nFibonacci("<<a<<")\t"<<Fibona cci(a);
return 0;
}  
P: n/a

<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);
}  
P: n/a

Hello,
"Agent Mulder" <mb*******************@home.nl> 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  
P: n/a

<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,
The indentation was eaten by your poorly installed newsreader, probably.
As to speed, I understand that you can do better. Show us. I didn't run
out of ideas yet.
X  
P: n/a

Hello,
"Agent Mulder" <mb*******************@home.nl> 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
implementation2}? 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
was talking about.
Bye,
Chris Dams  
P: n/a

<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>(cou t));
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;
}  
P: n/a

"Agent Mulder" <mb*******************@home.nl> wrote in message news:bm**********@news4.tilbu1.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>(cou t)); 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 15000
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_NT5.0 1.5.4(0.94/3/2)
GNU gcc version 3.3.1 (cygming special)
GNU time 1.7

No optimization
===========================================

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

Algorithm2 : 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:al****@connect.to http://mathforum.org/library/view/10978.html news://news.gmane.org/gmane.comp.lang.c++.perfometer
=====================================  
P: n/a

<Alex Vinokur>  Algorithm1 : 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
 Algorithm2 : 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
</>
Those are promissing results. Thank you, Alex!
Here is a functorbased Fibonacci generator. It is quicker than ever.
The bottleneck is in the output to the screen, that slows down the
program considerably. I guess this program can run 4 times faster than
it does now. If you want to impress us, fiddle with ios_base. Dietmar?
#include<iostream>
#include<algorithm>
#include<vector>
static ostream_iterator<int>out(cout);
static char base=10;
static char carry=0;
struct CarryChar
{
char&operator()(const char&a,const char&b)
{
char c=a+b+carry;
carry=0;
if(c>=base){c=base;carry=1;}
return c;
}};
struct LongInt
{
CarryChar carrychar;
vector<char>v;
LongInt(char a){do v.push_back(a%base);while((a/=base)!=0);}
LongInt&operator()(LongInt&a)
{
carry=0;
v.resize(a.v.size());
transform(v.begin(),v.end(),a.v.begin(),v.begin(), carrychar);
if(carry)v.push_back(1);
v.swap(a.v);
return*this;
}};
ostream&operator<<(ostream&a,const LongInt&b)
{
copy(b.v.rbegin(),b.v.rend(),ostream_iterator<int> (a));
return a;
}
int main()
{
LongInt a(0);
LongInt b(1);
for(int c=0;c<5000;c++)cout<<a(b)<<'\n';
return 0;
}  
P: n/a

In article <bn**********@news1.tilbu1.nb.home.nl>, mb*******************@home.nl says...
[ ... ] Here is a functorbased Fibonacci generator. It is quicker than ever.
Right now, it looks to me mostly like proof that you use a (badly)
broken compiler.
The bottleneck is in the output to the screen, that slows down the program considerably. I guess this program can run 4 times faster than it does now. If you want to impress us, fiddle with ios_base. Dietmar?
#include<iostream> #include<algorithm> #include<vector> static ostream_iterator<int>out(cout);
The compiler _should_ complain about 'cout' being an undeclared name (I
suspect you intended to use std::cout).
char&operator()(const char&a,const char&b) { char c=a+b+carry; carry=0; if(c>=base){c=base;carry=1;} return c; }};
This returns a reference to a local variable, which almost inevitably
leads to undefined behavior.
[ ...]
int main() { LongInt a(0); LongInt b(1); for(int c=0;c<5000;c++)cout<<a(b)<<'\n';
And _this_ is about as counterintuitive as anything could possibly be.

Later,
Jerry.
The universe is a figment of its own imagination.  
P: n/a

In article <bn**********@news1.tilbu1.nb.home.nl>, mb*******************@home.nl says...
[ ... ] Here is a functorbased Fibonacci generator. It is quicker than ever. The bottleneck is in the output to the screen, that slows down the program considerably. I guess this program can run 4 times faster than it does now. If you want to impress us, fiddle with ios_base. Dietmar?
Just for reference, I wrote up a short little Fibonacci number generator
using NTL. I then ran both it and your program (after fixing it) on my
machine, with the output redirected to NUL (/dev/null for UNIX types)
to mostly remove the I/O from the picture.
The NTL program was approximately 4 times as fast as your's. If you
want to impress us, write some code that's correct and readable...

Later,
Jerry.
The universe is a figment of its own imagination.  
P: n/a

Agent Mulder wrote:
struct CarryChar { char&operator()(const char&a,const char&b)
what is the point in passing a single character per reference?
Dito for the return value.

Karl Heinz Buchegger kb******@gascad.at  
P: n/a

<Agent Mulder> char&operator()(const char&a,const char&b)
</>
<Karl Heinz Buchegger> what is the point in passing a single character per reference? Dito for the return value.
</>
No point. Just forgot to remove it. I did remove comment
and indentation, by accident. I put it back in, but remember
"to road to perdition is paved with good indentation"
Andrei Alexandrescu
//fast Fibonacci generator for large numbers. Email to mb******@home.nl
#include<iostream>
#include<algorithm>
#include<vector>
//global data base, carry. Used by CarryChar and LongInt
static char base=10;
static char carry=0;
//struct CarryChar is used as functor in the STL transform algorithm
struct CarryChar
{
char operator()(const char a,const char b)
{
char c=a+b+carry;
carry=0;
if(c>=base){c=base;carry=1;}
return c;
}};
//global data carrychar, one instance of the above struct CarryChar
CarryChar carrychar;
//struct LongInt holds an expanding vector<char> and uses carrychar
struct LongInt
{
vector<char>v;
LongInt(char a){do v.push_back(a%base);while((a/=base)!=0);}
LongInt&operator()(LongInt&a)
{
v.resize(a.v.size());
carry=0;
transform(v.begin(),v.end(),a.v.begin(),v.begin(), carrychar);
if(carry)v.push_back(1);
v.swap(a.v);
return*this;
}};
//operator<< outputs a LongInt object (to the screen)
ostream&operator<<(ostream&a,const LongInt&b)
{
copy(b.v.rbegin(),b.v.rend(),ostream_iterator<int> (a));
return a;
}
//main. Note how LongInt(0) is forced cout<< to produce 0,1,1,2,3,5,8,13...
int main()
{
LongInt a(0);
LongInt b(1);
cout<<a<<'\n';
for(int c=0;c<20;c++)cout<<a(b)<<'\n';
return 0;
}  
P: n/a

I hate to misspell a quote, so here once again:
"the road to perdition is paved with good indentation"
Andrei Alexandrescu
X  
P: n/a

"Agent Mulder" <mb*******************@home.nl> wrote in message news:bn**********@news1.tilbu1.nb.home.nl... <Alex Vinokur>  Algorithm1 : 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
 Algorithm2 : 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 </>
Those are promissing results. Thank you, Alex!
Thank you, Agent! Here is a functorbased Fibonacci generator. It is quicker than ever. The bottleneck is in the output to the screen, that slows down the program considerably.
I think, one should measure getting only nth Fibonacci number (not all Fibonacci number 1 until n)
I guess this program can run 4 times faster than it does now. If you want to impress us, fiddle with ios_base. Dietmar?
// ###########################################
// Computing very long Fibonacci numbers : BEGIN
// Algorithm1b
// ########################################### #include<iostream> #include<algorithm> #include<vector> static ostream_iterator<int>out(cout); static char base=10; static char carry=0; struct CarryChar { char&operator()(const char&a,const char&b) { char c=a+b+carry; carry=0; if(c>=base){c=base;carry=1;} return c; }}; struct LongInt { CarryChar carrychar; vector<char>v; LongInt(char a){do v.push_back(a%base);while((a/=base)!=0);} LongInt&operator()(LongInt&a) { carry=0; v.resize(a.v.size()); transform(v.begin(),v.end(),a.v.begin(),v.begin(), carrychar); if(carry)v.push_back(1); v.swap(a.v); return*this; }}; ostream&operator<<(ostream&a,const LongInt&b) { copy(b.v.rbegin(),b.v.rend(),ostream_iterator<int> (a)); return a; } int main() { LongInt a(0); LongInt b(1); for(int c=0;c<5000;c++)cout<<a(b)<<'\n'; return 0; }
To get only nth number I changed main() as following :
 main 
int main(int argc, char** argv)
{
assert (argc == 2);
LongInt a(0);
LongInt b(1);
const int number (atoi(argv[1])  1);
for (int c = 0 ; c < number; c++) a(b);
cout << a(b) << "\n";
return 0;
}

I also changed
char& operator()(const char&a,const char&b)
to
char operator()(const char&a,const char&b)
because of compilation warning : " warning: reference to local variable `c' returned" (GNU g++ 3.3.1)
Program above (with changes) is called Algorithm1b
// ###########################################
// Computing very long Fibonacci numbers : END
// Algorithm1b
// ###########################################
Here is Algorithm2b.
// ###########################################
// Computing very long Fibonacci numbers : BEGIN
// Algorithm2b
// ###########################################
#include <assert.h>
#include <string>
#include <sstream>
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
#define MAX_VALUE(x,y) ((x) > (y) ? (x) : (y))
#define ASSERT(x)
// #define ASSERT(x) assert(x)
#define MAX_UNIT_VALUE (ULONG_MAX >> 2)
#define BASE 10
typedef unsigned int uint;
typedef unsigned long ulong;
// ==============
class BigInt
// ==============
{
friend class Aux;
friend ostream& operator<< (ostream& o, const BigInt& ins_i);
private :
static ulong base_s;
vector<ulong> units_;
static void Set_Full_Base ();
const BigInt operator+ (const BigInt& rhs_i) const;
public :
BigInt () {}
BigInt (ulong unit_i)
{
if (base_s == 1) Set_Full_Base ();
ASSERT (unit_i < base_s);
units_.push_back (unit_i);
}
BigInt (const BigInt& lhs_i, const BigInt& rhs_i)
{
(*this) = lhs_i + rhs_i;
}
~BigInt () {}
};
// 
class Aux
{
private :
ulong& head;
public :
ulong operator() (ulong n1, ulong n2)
{
ulong value = n1 + n2 + head;
head = value/BigInt::base_s;
return (value%BigInt::base_s);
}
Aux (ulong& head_io) : head (head_io) {}
};
// 
inline const BigInt BigInt::operator+ (const BigInt& rhs_i) const
{
BigInt ret;
const ulong max_size = MAX_VALUE (units_.size (), rhs_i.units_.size ());
vector<ulong> u1 (units_);
vector<ulong> u2 (rhs_i.units_);
u1.resize(max_size);
u2.resize(max_size);
ret.units_.resize(max_size);
ulong head = 0;
transform (u1.begin(), u1.end(), u2.begin(), ret.units_.begin(), Aux (head));
if (head) ret.units_.push_back (head);
return ret;
}
// 
inline ostream& operator<< (ostream& os, const BigInt& ins_i)
{
ASSERT (!ins_i.units_.empty ());
for (ulong i = (ins_i.units_.size ()  1); i > 0; i)
{
os << ins_i.units_ [i] << setw (BASE  1) << setfill ('0');
}
return os << ins_i.units_ [0];
}
// 
void BigInt::Set_Full_Base ()
{
ASSERT (base_s == 1);
// 
for (ulong i = 1; i <= (BASE  1); i++)
{
base_s *= BASE;
ASSERT (!(base_s >= MAX_UNIT_VALUE)  (base_s == 0));
ASSERT (BASE * ((base_s/BASE) + 1) < MAX_UNIT_VALUE);
ASSERT (base_s != 0);
}
}
// =====================
class Fibonacci
// =====================
{
private :
vector<BigInt> fibs_;
BigInt get_number (uint n_i = 0);
public :
void show_all () const;
void show_number () const;
Fibonacci (uint n_i = 0) { get_number (n_i); }
~Fibonacci () {}
};
// 
BigInt Fibonacci::get_number (uint n_i)
{
const uint cur_size = fibs_.size ();
for (uint i = cur_size; i <= n_i; i++)
{
switch (i)
{
case 0 :
fibs_.push_back (BigInt(0));
break;
case 1 :
if (fibs_.empty ()) fibs_.push_back (BigInt (0));
fibs_.push_back(BigInt (1));
break;
default :
fibs_.push_back (BigInt (get_number (i  2), get_number (i  1)));
break;
}
}
ASSERT (n_i < fibs_.size());
return fibs_ [n_i];
}
// 
void Fibonacci::show_all () const
{
ostringstream oss;
for (uint i = 0; i < fibs_.size (); i++)
{
oss << "Fib [" << i << "] = " << fibs_ [i] << "\n";
}
cout << oss.str();
}
// 
void Fibonacci::show_number () const
{
ostringstream oss;
oss << "Fib [" << (fibs_.size()  1) << "] = " << fibs_.back() << "\n";
cout << oss.str();
}
// 
ulong BigInt::base_s (1);
// ==============================
#define ALL_FIBS "all"
#define ONE_FIB "th"
int main (int argc, char **argv)
{
string option;
if ((argc <= 2)  !(((option = argv[2]) == ALL_FIBS)  (option == ONE_FIB)))
{
cerr << "\tUSAGE : " << argv[0] << " " << "<N  number> " << ALL_FIBS << "" << ONE_FIB << endl;
if (argc < 2) return 1;
cerr << "\t " << "" << endl;
cerr << "\t " << setw(3) << std::left << ALL_FIBS << "  Fibonacci [0  N]" << endl;
cerr << "\t " << setw(3) << std::left << ONE_FIB << "  Fibonacci [N]" << endl;
cerr << "\t " << "" << endl;
return 2;
}
Fibonacci fib(atoi(argv[1]));
(option == ALL_FIBS) ? fib.show_all() : fib.show_number();
return 0;
}
// ###########################################
// Computing very long Fibonacci numbers : END
// Algorithm2b
// ###########################################
// ###########################################
// Comparative performance : BEGIN
// ###########################################
=============================
Windows 2000 Professional
Intel(R) Celeron(R) CPU 1.70. GHz
CYGWIN_NT5.0 1.5.4(0.94/3/2)
GNU g++ version 3.3.1 (cygming special)
GNU time 1.7
=============================
Complexity of two algorithms has been compared while computing Fibonacci5000, Fibonacci10000, Fibonacci25000.

Algorithm1b :

Fibonacci5000

[1] 0.27 real, 0.25 user, 0.04 sys, 10704 maxresident
[2] 0.27 real, 0.25 user, 0.03 sys, 10704 maxresident
[3] 0.27 real, 0.25 user, 0.03 sys, 10704 maxresident
[4] 0.27 real, 0.25 user, 0.03 sys, 10704 maxresident
[5] 0.27 real, 0.26 user, 0.01 sys, 10704 maxresident
Fibonacci10000

[1] 0.95 real, 0.94 user, 0.03 sys, 10736 maxresident
[2] 0.94 real, 0.92 user, 0.04 sys, 10736 maxresident
[3] 0.94 real, 0.92 user, 0.03 sys, 10736 maxresident
[4] 0.94 real, 0.92 user, 0.03 sys, 10736 maxresident
[5] 0.94 real, 0.92 user, 0.04 sys, 10736 maxresident
Fibonacci25000

[1] 5.63 real, 5.61 user, 0.03 sys, 10800 maxresident
[2] 5.67 real, 5.64 user, 0.03 sys, 10800 maxresident
[3] 5.62 real, 5.59 user, 0.02 sys, 10800 maxresident
[4] 5.63 real, 5.60 user, 0.04 sys, 10800 maxresident
[5] 5.66 real, 5.62 user, 0.04 sys, 10800 maxresident

Algorithm2b :

Fibonacci5000

[1] 0.22 real, 0.20 user, 0.03 sys, 14960 maxresident
[2] 0.22 real, 0.20 user, 0.04 sys, 14960 maxresident
[3] 0.23 real, 0.20 user, 0.04 sys, 14960 maxresident
[4] 0.22 real, 0.20 user, 0.03 sys, 14960 maxresident
[5] 0.22 real, 0.19 user, 0.04 sys, 14960 maxresident
Fibonacci10000

[1] 0.52 real, 0.50 user, 0.03 sys, 21552 maxresident
[2] 0.52 real, 0.49 user, 0.05 sys, 21552 maxresident
[3] 0.53 real, 0.51 user, 0.03 sys, 21552 maxresident
[4] 0.53 real, 0.50 user, 0.04 sys, 21552 maxresident
[5] 0.53 real, 0.50 user, 0.04 sys, 21552 maxresident
Fibonacci25000

[1] 2.03 real, 2.00 user, 0.01 sys, 20144 maxresident
[2] 2.02 real, 1.97 user, 0.07 sys, 20144 maxresident
[3] 2.03 real, 1.98 user, 0.06 sys, 20144 maxresident
[4] 2.03 real, 1.98 user, 0.07 sys, 20144 maxresident
[5] 2.36 real, 2.31 user, 0.05 sys, 20144 maxresident
Note. maxresident is Maximum resident set size of the process during its lifetime, in Kilobytes.
// ###########################################
// Comparative performance : END
// ###########################################

=====================================
Alex Vinokur
mailto:al****@connect.to http://mathforum.org/library/view/10978.html news://news.gmane.org/gmane.comp.lang.c++.perfometer
=====================================  
P: n/a

"Alex Vinokur" <al****@bigfoot.com> wrote in message news:bn************@ID79865.news.uniberlin.de...
[snip] // ########################################### // Computing very long Fibonacci numbers : BEGIN // Algorithm2b // ###########################################
[snip]
Here is Algorithm2c for computing very long Fibonacci numbers.
Algorithm2c is an improved version of Algorithm2b.
// #####################################
// Computing very long Fibonacci numbers
// Algorithm2c
// BEGIN
// #####################################
#include <assert.h>
#include <string>
#include <sstream>
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
#define MAX_VALUE(x,y) ((x) > (y) ? (x) : (y))
#define ASSERT(x)
// #define ASSERT(x) assert(x)
#define MAX_UNIT_VALUE (ULONG_MAX >> 2)
#define BASE 10
typedef unsigned int uint;
typedef unsigned long ulong;
// ==============
class BigInt
// ==============
{
friend ostream& operator<< (ostream& o, const BigInt& ins_i);
private :
static ulong head_s;
static ulong base_s;
vector<ulong> units_;
static void Set_Full_Base ();
public :
BigInt (ulong unit_i)
{
if (base_s == 1) Set_Full_Base ();
ASSERT (unit_i < base_s);
units_.push_back (unit_i);
}
BigInt (BigInt lhs_i, BigInt rhs_i)
{
const ulong max_size = MAX_VALUE (lhs_i.units_.size (), rhs_i.units_.size ());
lhs_i.units_.resize(max_size);
rhs_i.units_.resize(max_size);
units_.resize(max_size);
head_s = 0;
transform (lhs_i.units_.begin(), lhs_i.units_.end(), rhs_i.units_.begin(), units_.begin(), *this);
if (head_s) units_.push_back (head_s);
}
ulong operator() (ulong n1, ulong n2)
{
ulong value = n1 + n2 + head_s;
head_s = value/base_s;
return (value%base_s);
}
};
// 
inline ostream& operator<< (ostream& os, const BigInt& ins_i)
{
ASSERT (!ins_i.units_.empty ());
for (ulong i = (ins_i.units_.size ()  1); i > 0; i)
{
os << ins_i.units_ [i] << setw (BASE  1) << setfill ('0');
}
return os << ins_i.units_ [0];
}
// 
void BigInt::Set_Full_Base ()
{
ASSERT (base_s == 1);
// 
for (ulong i = 1; i <= (BASE  1); i++)
{
base_s *= BASE;
ASSERT (!(base_s >= MAX_UNIT_VALUE)  (base_s == 0));
ASSERT (BASE * ((base_s/BASE) + 1) < MAX_UNIT_VALUE);
ASSERT (base_s != 0);
}
}
// =====================
class Fibonacci
// =====================
{
private :
vector<BigInt> fibs_;
BigInt get_number (uint n_i = 0);
public :
void show_all () const;
void show_number () const;
Fibonacci (uint n_i = 0) { get_number (n_i); }
~Fibonacci () {}
};
// 
BigInt Fibonacci::get_number (uint n_i)
{
const uint cur_size = fibs_.size ();
for (uint i = cur_size; i <= n_i; i++)
{
switch (i)
{
case 0 :
fibs_.push_back (BigInt(0));
break;
case 1 :
if (fibs_.empty ()) fibs_.push_back (BigInt (0));
fibs_.push_back(BigInt (1));
break;
default :
fibs_.push_back (BigInt (get_number (i  2), get_number (i  1)));
break;
}
}
ASSERT (n_i < fibs_.size());
return fibs_ [n_i];
}
// 
void Fibonacci::show_all () const
{
ostringstream oss;
for (uint i = 0; i < fibs_.size (); i++)
{
oss << "Fib [" << i << "] = " << fibs_ [i] << "\n";
}
cout << oss.str();
}
// 
void Fibonacci::show_number () const
{
ostringstream oss;
oss << "Fib [" << (fibs_.size()  1) << "] = " << fibs_.back() << "\n";
cout << oss.str();
}
// 
ulong BigInt::head_s (0);
ulong BigInt::base_s (1);
// ==============================
#define ALL_FIBS "all"
#define ONE_FIB "th"
int main (int argc, char **argv)
{
string option;
if ((argc <= 2)  !(((option = argv[2]) == ALL_FIBS)  (option == ONE_FIB)))
{
cerr << "\tUSAGE : " << argv[0] << " " << "<N  number> " << ALL_FIBS << "" << ONE_FIB << endl;
if (argc < 2) return 1;
cerr << "\t " << "" << endl;
cerr << "\t " << setw(3) << std::left << ALL_FIBS << "  Fibonacci [0  N]" << endl;
cerr << "\t " << setw(3) << std::left << ONE_FIB << "  Fibonacci [N]" << endl;
cerr << "\t " << "" << endl;
return 2;
}
Fibonacci fib(atoi(argv[1]));
(option == ALL_FIBS) ? fib.show_all() : fib.show_number();
return 0;
}
// #####################################
// END
// Algorithm2c
// Computing very long Fibonacci numbers
// #####################################
// ################################
// Comparative performance : BEGIN
// ################################
=============================
Windows 2000 Professional
Intel(R) Celeron(R) CPU 1.70. GHz
CYGWIN_NT5.0 1.5.4(0.94/3/2)
GNU g++ version 3.3.1 (cygming special)
GNU time 1.7
=============================
Complexity of two algorithms has been compared while computing
* Fibonacci5000,
* Fibonacci10000,
* Fibonacci25000.
Note. Output has been redirected to a file.

Algorithm2b

Fibonacci5000

[1] 0.22 real, 0.20 user, 0.03 sys, 14960 maxresident
[2] 0.22 real, 0.22 user, 0.03 sys, 14960 maxresident
[3] 0.22 real, 0.22 user, 0.02 sys, 14960 maxresident
[4] 0.23 real, 0.20 user, 0.03 sys, 14960 maxresident
[5] 0.22 real, 0.20 user, 0.03 sys, 14960 maxresident
Fibonacci10000

[1] 0.52 real, 0.50 user, 0.04 sys, 21552 maxresident
[2] 0.52 real, 0.49 user, 0.04 sys, 21552 maxresident
[3] 0.52 real, 0.50 user, 0.05 sys, 21552 maxresident
[4] 0.52 real, 0.51 user, 0.03 sys, 21552 maxresident
[5] 0.52 real, 0.51 user, 0.03 sys, 21552 maxresident
Fibonacci25000

[1] 2.01 real, 1.94 user, 0.09 sys, 20144 maxresident
[2] 2.02 real, 1.97 user, 0.06 sys, 20144 maxresident
[3] 2.00 real, 1.96 user, 0.05 sys, 20144 maxresident
[4] 2.00 real, 1.91 user, 0.11 sys, 20144 maxresident
[5] 2.00 real, 1.96 user, 0.05 sys, 20144 maxresident

Algorithm2c

Fibonacci5000

[1] 0.19 real, 0.17 user, 0.03 sys, 12384 maxresident
[2] 0.20 real, 0.19 user, 0.03 sys, 12384 maxresident
[3] 0.19 real, 0.18 user, 0.02 sys, 12384 maxresident
[4] 0.19 real, 0.17 user, 0.04 sys, 12384 maxresident
[5] 0.20 real, 0.18 user, 0.03 sys, 12384 maxresident
Fibonacci10000

[1] 0.46 real, 0.45 user, 0.03 sys, 21600 maxresident
[2] 0.46 real, 0.42 user, 0.05 sys, 21600 maxresident
[3] 0.46 real, 0.44 user, 0.03 sys, 21600 maxresident
[4] 0.47 real, 0.43 user, 0.04 sys, 21600 maxresident
[5] 0.46 real, 0.45 user, 0.03 sys, 21600 maxresident
Fibonacci25000

[1] 1.91 real, 1.86 user, 0.05 sys, 12608 maxresident
[2] 1.92 real, 1.87 user, 0.07 sys, 12608 maxresident
[3] 1.91 real, 1.83 user, 0.09 sys, 12608 maxresident
[4] 1.91 real, 1.88 user, 0.05 sys, 12608 maxresident
[5] 1.91 real, 1.85 user, 0.07 sys, 12608 maxresident
// ##############################
// Comparative performance : END
// ##############################

=====================================
Alex Vinokur
mailto:al****@connect.to http://mathforum.org/library/view/10978.html news://news.gmane.org/gmane.comp.lang.c++.perfometer
=====================================  
P: 1

you guys are making this to hard... i have this and it works great
#include "stdafx.h"
#include <iostream>
using namespace std;
unsigned long fibo(unsigned long n, unsigned long x)
{
long sum;
cout << x << " ";
sum=n + x;
if (n < 21474836472555287542348456436846546345675643216374 8648675412)
{
return sum + fibo(x,sum);
}
else
{
return x;
}
};
int main(int argc, char* argv[])
{
int y;
fibo(0,1);
cin >> y;
return 0;
}
  This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 12451
 replies: 28
 date asked: Jul 19 '05
