Ad:

C++ Discussion Thread
Unsolved
Views: 1084

Jan 3rd, 2009

fibonocci sequence question

Expand Post »

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

C++ Syntax (Toggle Plain Text)
#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;
}
#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

firstPerson

Reputation Points: 840

Solved Threads: 594

Senior Poster

Offline

3,862 posts
since Dec 2008

Permalink

Jan 3rd, 2009

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.

VernonDozier

Featured Poster

Reputation Points: 2614

Solved Threads: 687

Posting Expert

Offline

5,372 posts
since Jan 2008

Permalink

Jan 3rd, 2009

Re: fibonocci sequence question

C++ Syntax (Toggle Plain Text)
unsigned long double result = 0.0;
unsigned long double x = 1.0;
unsigned long double y = 1.0;
unsigned long double result2 = 0.0;
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.

William Hemsworth

Reputation Points: 1429

Solved Threads: 129

Posting Virtuoso

Offline

1,542 posts
since Mar 2008

Permalink

Jan 3rd, 2009

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

Salem

Team Colleague

Reputation Points: 5862

Solved Threads: 950

Posting Sage

Offline

7,164 posts
since Dec 2005

Permalink

Jan 7th, 2009

-1

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

aryansmit3754

Reputation Points: 9

Solved Threads: 0

Newbie Poster

Offline

4 posts
since Jan 2009

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Linked Lists using struct

Next Thread in C++ Forum Timeline: for and while HELP

DaniWeb Message

Cancel Changes

User Name
Password