459,212 Members | 1,370 Online Need help? Post your question and get tips & solutions from a community of 459,212 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
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 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 