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
Bytes IT Community
+ 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
Share on Google+
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 <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

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

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
| straight-forward. Initialization is also clean, just write:
| Huge("123456789");
|
| Another way to do it is to use multiple ints (or longs) to store the
number.
| You could probably implement this more efficiently than with strings, but
I
| think it makes the code a bit more complicated.

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

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

std::vector<int> is an option to store such a number...
Regards,
--
http://ivan.vecerina.com
Jul 19 '05 #8

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

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<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
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 have
and advice on fixing it.I am compiling it under Linux with gcc.
#include<iostream.h> #include <iostream>
int main(void) int main(){
long fib1 = 1;
long fib2 = 1;
long fib3;
long fib4;

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

cout << fib3 << endl;
cout << fib4 << endl; fib3 = fib1 + fib2;
fib4 = fib3 + fib2;
fib1 = fib3;
fib2 = fib4;

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

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

Lee,

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

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

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

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

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

You will need to implement:

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

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

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

rossum

--

The Ultimate Truth is that there is no Ultimate Truth
Jul 19 '05 #11

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(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<N;a++)cout<<"\nFibonacci("<<a<<")\t"<<fibona cci(a);
return 0;
}

Jul 19 '05 #12

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.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
Jul 19 '05 #13

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(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<N;a++)cout<<"\nFibonacci("<<a<<")\t"<<Fibona cci(a);
return 0;
}

Jul 19 '05 #14

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

Jul 19 '05 #15

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

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

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

Jul 19 '05 #19

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

Time complexity of two algorithms was compared.

Each algorithm has been run 5 times.
--
===========================================
Windows 2000 Professional
Intel(R) Celeron(R) CPU 1.70 GHz
CYGWIN_NT-5.0 1.5.4(0.94/3/2)
GNU gcc version 3.3.1 (cygming special)
GNU time 1.7
---------------
No optimization
===========================================
-----------------------
Algorithm-1 : See above
-----------------------
[1] 17.47 real, 17.16 user, 0.19 sys
[2] 17.44 real, 17.24 user, 0.15 sys
[3] 17.46 real, 17.19 user, 0.18 sys
[4] 17.36 real, 17.15 user, 0.13 sys
[5] 17.52 real, 17.22 user, 0.15 sys

--------------------------
Algorithm-2 : http://alexvn.freeservers.com/s1/fibonacci.html
--------------------------
[1] 9.26 real, 9.00 user, 0.19 sys
[2] 9.31 real, 9.06 user, 0.21 sys
[3] 9.38 real, 9.07 user, 0.24 sys
[4] 9.35 real, 9.06 user, 0.21 sys
[5] 9.33 real, 9.00 user, 0.27 sys
--
=====================================
Alex Vinokur
mailto:al****@connect.to
http://mathforum.org/library/view/10978.html
news://news.gmane.org/gmane.comp.lang.c++.perfometer
=====================================

Jul 19 '05 #20

P: n/a
<Alex Vinokur>
-----------------------
Algorithm-1 : See above
-----------------------
[1] 17.47 real, 17.16 user, 0.19 sys
[2] 17.44 real, 17.24 user, 0.15 sys
[3] 17.46 real, 17.19 user, 0.18 sys
[4] 17.36 real, 17.15 user, 0.13 sys
[5] 17.52 real, 17.22 user, 0.15 sys

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

</>

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

Jul 19 '05 #21

P: n/a
In article <bn**********@news1.tilbu1.nb.home.nl>,
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<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 counter-intuitive as anything could possibly be.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jul 19 '05 #22

P: n/a
In article <bn**********@news1.tilbu1.nb.home.nl>,
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
<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;
}

Jul 19 '05 #25

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" <mb*******************@home.nl> wrote in message news:bn**********@news1.tilbu1.nb.home.nl...
<Alex Vinokur>
-----------------------
Algorithm-1 : See above
-----------------------
[1] 17.47 real, 17.16 user, 0.19 sys
[2] 17.44 real, 17.24 user, 0.15 sys
[3] 17.46 real, 17.19 user, 0.18 sys
[4] 17.36 real, 17.15 user, 0.13 sys
[5] 17.52 real, 17.22 user, 0.15 sys

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

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<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 n-th 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 Algorithm-1b

// ###########################################
// Computing very long Fibonacci numbers : END
// Algorithm-1b
// ###########################################

Here is Algorithm-2b.

// ###########################################
// Computing very long Fibonacci numbers : BEGIN
// Algorithm-2b
// ###########################################

#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
// 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
--------------
[1] 0.27 real, 0.25 user, 0.04 sys, 10704 max-resident
[2] 0.27 real, 0.25 user, 0.03 sys, 10704 max-resident
[3] 0.27 real, 0.25 user, 0.03 sys, 10704 max-resident
[4] 0.27 real, 0.25 user, 0.03 sys, 10704 max-resident
[5] 0.27 real, 0.26 user, 0.01 sys, 10704 max-resident
Fibonacci-10000
---------------
[1] 0.95 real, 0.94 user, 0.03 sys, 10736 max-resident
[2] 0.94 real, 0.92 user, 0.04 sys, 10736 max-resident
[3] 0.94 real, 0.92 user, 0.03 sys, 10736 max-resident
[4] 0.94 real, 0.92 user, 0.03 sys, 10736 max-resident
[5] 0.94 real, 0.92 user, 0.04 sys, 10736 max-resident
Fibonacci-25000
---------------
[1] 5.63 real, 5.61 user, 0.03 sys, 10800 max-resident
[2] 5.67 real, 5.64 user, 0.03 sys, 10800 max-resident
[3] 5.62 real, 5.59 user, 0.02 sys, 10800 max-resident
[4] 5.63 real, 5.60 user, 0.04 sys, 10800 max-resident
[5] 5.66 real, 5.62 user, 0.04 sys, 10800 max-resident


--------------
Algorithm-2b :
--------------

Fibonacci-5000
--------------
[1] 0.22 real, 0.20 user, 0.03 sys, 14960 max-resident
[2] 0.22 real, 0.20 user, 0.04 sys, 14960 max-resident
[3] 0.23 real, 0.20 user, 0.04 sys, 14960 max-resident
[4] 0.22 real, 0.20 user, 0.03 sys, 14960 max-resident
[5] 0.22 real, 0.19 user, 0.04 sys, 14960 max-resident
Fibonacci-10000
---------------
[1] 0.52 real, 0.50 user, 0.03 sys, 21552 max-resident
[2] 0.52 real, 0.49 user, 0.05 sys, 21552 max-resident
[3] 0.53 real, 0.51 user, 0.03 sys, 21552 max-resident
[4] 0.53 real, 0.50 user, 0.04 sys, 21552 max-resident
[5] 0.53 real, 0.50 user, 0.04 sys, 21552 max-resident
Fibonacci-25000
---------------
[1] 2.03 real, 2.00 user, 0.01 sys, 20144 max-resident
[2] 2.02 real, 1.97 user, 0.07 sys, 20144 max-resident
[3] 2.03 real, 1.98 user, 0.06 sys, 20144 max-resident
[4] 2.03 real, 1.98 user, 0.07 sys, 20144 max-resident
[5] 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" <al****@bigfoot.com> 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 <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
// 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
--------------
[1] 0.22 real, 0.20 user, 0.03 sys, 14960 max-resident
[2] 0.22 real, 0.22 user, 0.03 sys, 14960 max-resident
[3] 0.22 real, 0.22 user, 0.02 sys, 14960 max-resident
[4] 0.23 real, 0.20 user, 0.03 sys, 14960 max-resident
[5] 0.22 real, 0.20 user, 0.03 sys, 14960 max-resident
Fibonacci-10000
---------------
[1] 0.52 real, 0.50 user, 0.04 sys, 21552 max-resident
[2] 0.52 real, 0.49 user, 0.04 sys, 21552 max-resident
[3] 0.52 real, 0.50 user, 0.05 sys, 21552 max-resident
[4] 0.52 real, 0.51 user, 0.03 sys, 21552 max-resident
[5] 0.52 real, 0.51 user, 0.03 sys, 21552 max-resident
Fibonacci-25000
---------------
[1] 2.01 real, 1.94 user, 0.09 sys, 20144 max-resident
[2] 2.02 real, 1.97 user, 0.06 sys, 20144 max-resident
[3] 2.00 real, 1.96 user, 0.05 sys, 20144 max-resident
[4] 2.00 real, 1.91 user, 0.11 sys, 20144 max-resident
[5] 2.00 real, 1.96 user, 0.05 sys, 20144 max-resident

------------
Algorithm-2c
------------

Fibonacci-5000
--------------
[1] 0.19 real, 0.17 user, 0.03 sys, 12384 max-resident
[2] 0.20 real, 0.19 user, 0.03 sys, 12384 max-resident
[3] 0.19 real, 0.18 user, 0.02 sys, 12384 max-resident
[4] 0.19 real, 0.17 user, 0.04 sys, 12384 max-resident
[5] 0.20 real, 0.18 user, 0.03 sys, 12384 max-resident
Fibonacci-10000
---------------
[1] 0.46 real, 0.45 user, 0.03 sys, 21600 max-resident
[2] 0.46 real, 0.42 user, 0.05 sys, 21600 max-resident
[3] 0.46 real, 0.44 user, 0.03 sys, 21600 max-resident
[4] 0.47 real, 0.43 user, 0.04 sys, 21600 max-resident
[5] 0.46 real, 0.45 user, 0.03 sys, 21600 max-resident
Fibonacci-25000
---------------
[1] 1.91 real, 1.86 user, 0.05 sys, 12608 max-resident
[2] 1.92 real, 1.87 user, 0.07 sys, 12608 max-resident
[3] 1.91 real, 1.83 user, 0.09 sys, 12608 max-resident
[4] 1.91 real, 1.88 user, 0.05 sys, 12608 max-resident
[5] 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 <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;
}
Jul 25 '06 #29

This discussion thread is closed

Replies have been disabled for this discussion.