Re: Fibonacci implementation

Hi,

I'm looking for a non-recursive implementation of the algorithm to
calculate Fibonacci numbers. Any language is OK (C/C++, pseudo code
prefered).


It's been a while. Hope that this still works

//oktober 2003 Fast fibonacci generator for very large numbers

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

inline int dv(int a,int b){return a/10+b;}
inline int md(int a){return a%10;}
inline 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(LongInt&a){v.swap(a.v);}
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]>9)
{
int c=v[v.size()-1]/10;
v[v.size()-1]%=10;
v.push_back(c);
}}
void print()
{
copy(v.rbegin(),v.rend(),ostream_iterator<int>(cout));
cout<<endl;
}};

struct Fibonacci
{
LongInt first,second,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()
{
LongInt a(45);
LongInt b(55);
LongInt c;
c.set(a,b);
c.print();
Fibonacci(900000);
return 0;
}



.