By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
 428,978 Members | 1,467 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 428,978 IT Pros & Developers. It's quick & easy.

# Fibonacci numbers

 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 ;-) Jul 19 '05 #1
Share this Question
28 Replies

 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 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 Jul 19 '05 #2

 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 Jul 19 '05 #3

 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 :) Jul 19 '05 #4

 P: n/a On Fri, 10 Oct 2003 15:20:27 +0800, Ryan Winter 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 Jul 19 '05 #5

 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 Jul 19 '05 #6

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

 P: n/a "Joost Ronkes Agerbeek" 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 | 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 is an option to store such a number... Regards, -- http://ivan.vecerina.com Jul 19 '05 #8

 P: n/a "Sam Holden" wrote in message news:slrnbocpm4.c0l.sh*****@flexal.cs.usyd.edu.au. .. On Fri, 10 Oct 2003 15:20:27 +0800, Ryan Winter 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 ===================================== Jul 19 '05 #9

 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 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 Jul 19 '05 #10

 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 haveand advice on fixing it.I am compiling it under Linux with gcc. #include #include 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 whatI 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 with . 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 Jul 19 '05 #11

 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. Here you have a recursive fibonacci generator: #include #include 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...nacci/fib.html \n"; for(int a=0;a

 P: n/a "Agent Mulder" wrote: 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 #include #include #include struct Int { enum { base = 10 }; typedef std::vector 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(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 + a) << '\n'; } -- Phaidros eaSE - Easy Software Engineering: Jul 19 '05 #13

 P: n/a I would appreciate any advice. And here is a class based recursive fibonacci generator: #include #include 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) ) { } 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

 P: n/a 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 #include #include #include ostream_iteratorout(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 { vectorV; vector&v; LongInt(int a=0):v(V){do v.push_back(a%10);while((a/=10)!=0);} void swap(const LongInt&a) { vector&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()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<

 P: n/a Hello, "Agent Mulder" writes: 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 Jul 19 '05 #16

 P: n/a I'm really impressed. Here is a very fast fibonacci generator for very large numbers: 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 Jul 19 '05 #17

 P: n/a Hello, "Agent Mulder" writes: Here is a very fast fibonacci generator for very large numbers: This is not fast at all. [SNIP] ...what about indentation andfunction names that describe what the function is doing? As to speed, I understand that you can do better. Show us. I didn't runout 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 was talking about. Bye, Chris Dams Jul 19 '05 #18

 P: n/a This is not fast at all. [SNIP] As to speed, I understand that you can do better. Show us. 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 #include #include 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 { vectorv; 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()=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(cou t)); cout<

 P: n/a "Agent Mulder" wrote in message news:bm**********@news4.tilbu1.nb.home.nl... This is not fast at all. [SNIP] As to speed, I understand that you can do better. Show us. 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 #include #include 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 { vectorv; 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()=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(cou t)); cout<

 P: n/a ----------------------- Algorithm-1 : See above -----------------------  17.47 real, 17.16 user, 0.19 sys  17.44 real, 17.24 user, 0.15 sys  17.46 real, 17.19 user, 0.18 sys  17.36 real, 17.15 user, 0.13 sys  17.52 real, 17.22 user, 0.15 sys -------------------------- Algorithm-2 : http://alexvn.freeservers.com/s1/fibonacci.html --------------------------  9.26 real, 9.00 user, 0.19 sys  9.31 real, 9.06 user, 0.21 sys  9.38 real, 9.07 user, 0.24 sys  9.35 real, 9.06 user, 0.21 sys  9.33 real, 9.00 user, 0.27 sys Those are promissing results. Thank you, Alex! Here is a functor-based 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 #include #include static ostream_iteratorout(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; vectorv; 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 (a)); return a; } int main() { LongInt a(0); LongInt b(1); for(int c=0;c<5000;c++)cout<

 P: n/a In article , mb*******************@home.nl says... [ ... ] Here is a functor-based 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 #include #include static ostream_iteratorout(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<

 P: n/a In article , mb*******************@home.nl says... [ ... ] Here is a functor-based 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 re-directed 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. Jul 19 '05 #23

 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 Jul 19 '05 #24

 P: n/a char&operator()(const char&a,const char&b) 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 #include #include //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 and uses carrychar struct LongInt { vectorv; 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 (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<

 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 Jul 19 '05 #26

 P: n/a "Agent Mulder" wrote in message news:bn**********@news1.tilbu1.nb.home.nl... ----------------------- Algorithm-1 : See above -----------------------  17.47 real, 17.16 user, 0.19 sys  17.44 real, 17.24 user, 0.15 sys  17.46 real, 17.19 user, 0.18 sys  17.36 real, 17.15 user, 0.13 sys  17.52 real, 17.22 user, 0.15 sys -------------------------- Algorithm-2 : http://alexvn.freeservers.com/s1/fibonacci.html --------------------------  9.26 real, 9.00 user, 0.19 sys  9.31 real, 9.06 user, 0.21 sys  9.38 real, 9.07 user, 0.24 sys  9.35 real, 9.06 user, 0.21 sys  9.33 real, 9.00 user, 0.27 sys Those are promissing results. Thank you, Alex! Thank you, Agent! Here is a functor-based 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 n-th 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 // Algorithm-1b // ########################################### #include #include #include static ostream_iteratorout(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; vectorv; 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 (a)); return a; } int main() { LongInt a(0); LongInt b(1); for(int c=0;c<5000;c++)cout< #include #include #include #include #include #include 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 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 u1 (units_); vector 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_ ; } // -------------- 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 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) == ALL_FIBS) || (option == ONE_FIB))) { cerr << "\tUSAGE : " << argv << " " << " " << 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)); (option == ALL_FIBS) ? fib.show_all() : fib.show_number(); return 0; } // ########################################### // Computing very long Fibonacci numbers : END // Algorithm-2b // ########################################### // ########################################### // Comparative performance : BEGIN // ########################################### ============================= Windows 2000 Professional Intel(R) Celeron(R) CPU 1.70. GHz CYGWIN_NT-5.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 Fibonacci-5000, Fibonacci-10000, Fibonacci-25000. -------------- Algorithm-1b : -------------- Fibonacci-5000 --------------  0.27 real, 0.25 user, 0.04 sys, 10704 max-resident  0.27 real, 0.25 user, 0.03 sys, 10704 max-resident  0.27 real, 0.25 user, 0.03 sys, 10704 max-resident  0.27 real, 0.25 user, 0.03 sys, 10704 max-resident  0.27 real, 0.26 user, 0.01 sys, 10704 max-resident Fibonacci-10000 ---------------  0.95 real, 0.94 user, 0.03 sys, 10736 max-resident  0.94 real, 0.92 user, 0.04 sys, 10736 max-resident  0.94 real, 0.92 user, 0.03 sys, 10736 max-resident  0.94 real, 0.92 user, 0.03 sys, 10736 max-resident  0.94 real, 0.92 user, 0.04 sys, 10736 max-resident Fibonacci-25000 ---------------  5.63 real, 5.61 user, 0.03 sys, 10800 max-resident  5.67 real, 5.64 user, 0.03 sys, 10800 max-resident  5.62 real, 5.59 user, 0.02 sys, 10800 max-resident  5.63 real, 5.60 user, 0.04 sys, 10800 max-resident  5.66 real, 5.62 user, 0.04 sys, 10800 max-resident -------------- Algorithm-2b : -------------- Fibonacci-5000 --------------  0.22 real, 0.20 user, 0.03 sys, 14960 max-resident  0.22 real, 0.20 user, 0.04 sys, 14960 max-resident  0.23 real, 0.20 user, 0.04 sys, 14960 max-resident  0.22 real, 0.20 user, 0.03 sys, 14960 max-resident  0.22 real, 0.19 user, 0.04 sys, 14960 max-resident Fibonacci-10000 ---------------  0.52 real, 0.50 user, 0.03 sys, 21552 max-resident  0.52 real, 0.49 user, 0.05 sys, 21552 max-resident  0.53 real, 0.51 user, 0.03 sys, 21552 max-resident  0.53 real, 0.50 user, 0.04 sys, 21552 max-resident  0.53 real, 0.50 user, 0.04 sys, 21552 max-resident Fibonacci-25000 ---------------  2.03 real, 2.00 user, 0.01 sys, 20144 max-resident  2.02 real, 1.97 user, 0.07 sys, 20144 max-resident  2.03 real, 1.98 user, 0.06 sys, 20144 max-resident  2.03 real, 1.98 user, 0.07 sys, 20144 max-resident  2.36 real, 2.31 user, 0.05 sys, 20144 max-resident Note. max-resident 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 ===================================== Jul 19 '05 #27

 P: n/a "Alex Vinokur" wrote in message news:bn************@ID-79865.news.uni-berlin.de... [snip] // ########################################### // Computing very long Fibonacci numbers : BEGIN // Algorithm-2b // ########################################### [snip] Here is Algorithm-2c for computing very long Fibonacci numbers. Algorithm-2c is an improved version of Algorithm-2b. // ##################################### // Computing very long Fibonacci numbers // Algorithm-2c // BEGIN // ##################################### #include #include #include #include #include #include #include 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 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_ ; } // -------------- 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 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) == ALL_FIBS) || (option == ONE_FIB))) { cerr << "\tUSAGE : " << argv << " " << " " << 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)); (option == ALL_FIBS) ? fib.show_all() : fib.show_number(); return 0; } // ##################################### // END // Algorithm-2c // Computing very long Fibonacci numbers // ##################################### // ################################ // Comparative performance : BEGIN // ################################ ============================= Windows 2000 Professional Intel(R) Celeron(R) CPU 1.70. GHz CYGWIN_NT-5.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 * Fibonacci-5000, * Fibonacci-10000, * Fibonacci-25000. Note. Output has been redirected to a file. ------------ Algorithm-2b ------------ Fibonacci-5000 --------------  0.22 real, 0.20 user, 0.03 sys, 14960 max-resident  0.22 real, 0.22 user, 0.03 sys, 14960 max-resident  0.22 real, 0.22 user, 0.02 sys, 14960 max-resident  0.23 real, 0.20 user, 0.03 sys, 14960 max-resident  0.22 real, 0.20 user, 0.03 sys, 14960 max-resident Fibonacci-10000 ---------------  0.52 real, 0.50 user, 0.04 sys, 21552 max-resident  0.52 real, 0.49 user, 0.04 sys, 21552 max-resident  0.52 real, 0.50 user, 0.05 sys, 21552 max-resident  0.52 real, 0.51 user, 0.03 sys, 21552 max-resident  0.52 real, 0.51 user, 0.03 sys, 21552 max-resident Fibonacci-25000 ---------------  2.01 real, 1.94 user, 0.09 sys, 20144 max-resident  2.02 real, 1.97 user, 0.06 sys, 20144 max-resident  2.00 real, 1.96 user, 0.05 sys, 20144 max-resident  2.00 real, 1.91 user, 0.11 sys, 20144 max-resident  2.00 real, 1.96 user, 0.05 sys, 20144 max-resident ------------ Algorithm-2c ------------ Fibonacci-5000 --------------  0.19 real, 0.17 user, 0.03 sys, 12384 max-resident  0.20 real, 0.19 user, 0.03 sys, 12384 max-resident  0.19 real, 0.18 user, 0.02 sys, 12384 max-resident  0.19 real, 0.17 user, 0.04 sys, 12384 max-resident  0.20 real, 0.18 user, 0.03 sys, 12384 max-resident Fibonacci-10000 ---------------  0.46 real, 0.45 user, 0.03 sys, 21600 max-resident  0.46 real, 0.42 user, 0.05 sys, 21600 max-resident  0.46 real, 0.44 user, 0.03 sys, 21600 max-resident  0.47 real, 0.43 user, 0.04 sys, 21600 max-resident  0.46 real, 0.45 user, 0.03 sys, 21600 max-resident Fibonacci-25000 ---------------  1.91 real, 1.86 user, 0.05 sys, 12608 max-resident  1.92 real, 1.87 user, 0.07 sys, 12608 max-resident  1.91 real, 1.83 user, 0.09 sys, 12608 max-resident  1.91 real, 1.88 user, 0.05 sys, 12608 max-resident  1.91 real, 1.85 user, 0.07 sys, 12608 max-resident // ############################## // 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 ===================================== Jul 19 '05 #28

 P: 1 you guys are making this to hard... i have this and it works great #include "stdafx.h" #include 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; } Jul 25 '06 #29

### This discussion thread is closed

Replies have been disabled for this discussion. 