fibonocci sequence question
 

What is the first term in the Fibonacci sequence to contain 1000 digits?

so i made a program that finds the fibonocci's sequence (fs).
I tried to do it recursively but it takes too long for big numbers. so i made a manual one.

BUt as i count how many digits there are for each (fs). a problem exist. After F(1476)--which has 309 digits, the program stops suddenly. I think its because of memory space or something. Any ways, this is why I turned to you. any help

here is my code

#include<iostream>

#include<fstream>

#include<iomanip>

#include<cmath>

using namespace std;



int countdigits(unsigned long double x)

{        

        int count(0);



        while(x>.99999999999999)

        {

                

                x/=10;

                count++;

        }

        return count;

}







int main(){



unsigned long double result = 0.0;

unsigned long double x = 1.0;

unsigned long double y = 1.0;

unsigned long double result2 = 0.0;

int count(0);

for(int i = 3;;i++)

{

        result = x+y;

        y = x;

        x = result;

        result2 = result;

        cout<<setprecision(10)<<"F of "<<i<<" is : "<<result/1000000<<"        count is : "<<countdigits(result2)<<endl;



        if(( countdigits(result2) == 1000 ) )

        {

                

                cin.get();

        }





}



return 0;

}

try running the program to get a better understanding , and then maybe you can help be better. thanks :)

Re: fibonocci sequence question
 

Double's range is higher than int's range, but it's still way less than 1000 digits, at least on my machine.

http://www.cplusplus.com/reference/s...ic_limits.html

It's doubtful you're going to be able to do this problem with the normal data types.

Re: fibonocci sequence question
 

unsigned long double result = 0.0;

unsigned long double x = 1.0;

unsigned long double y = 1.0;

unsigned long double result2 = 0.0;

There is no such thing as an unsigned double.

As you only need to use integers, you should try using a 64-bit integer variable type instead of a double, as using a double will also give you inaccurate results. But you wont be able to get accurate big numbers using just the standard C++ library, you will need to use a seperate big number library or class such as this.

Hope this helps.

Re: fibonocci sequence question
 

If
n! is n * fac(n-1);

Then
log(n!) = n + lfac(n-1)

If you use log10, it's even better :)

Re: fibonocci sequence question
 

use a dp solution
#include<iostream.h>
#include<string.h>
#include<vector.h>
#include<iterator.h>
int main()
{
vector<long long int>v1(101);
vector<long long int>v2(101);
int i=0;
for(;i<101;i++)
{
if(i==0||i==1)
v1[i]==1;
else
v1[i]=i;
}
v2[0]=v2[1]=1;
i=2;
for(;i<101;i++)
{
v2[i]=v2[i-1]*v1[i];
}
cout<<"nter no for which u want factorial";
istream_iterator<long long int>is(cin);
ostream_iterator<long long int>os(cout,"\n");
int a;

a=*is;
*os=v2[a];
cout<<"the factorialof "<<a<<"is";
*os;
return 0;
}