C++ RSS C++ RSS

fibonocci sequence question

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

•
•
Join Date: Dec 2008
Posts: 1,120
Reputation: firstPerson is just really nice firstPerson is just really nice firstPerson is just really nice firstPerson is just really nice 
Solved Threads: 143
firstPerson's Avatar
firstPerson firstPerson is offline Offline
Veteran Poster

fibonocci sequence question

 
0
  #1
Jan 3rd, 2009
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) 
  1. #include<iostream>
  2. #include<fstream>
  3. #include<iomanip>
  4. #include<cmath>
  5. using namespace std;
  6.  
  7. int countdigits(unsigned long double x)
  8. {	
  9. 	int count(0);
  10.  
  11. 	while(x>.99999999999999)
  12. 	{
  13.  
  14. 		x/=10;
  15. 		count++;
  16. 	}
  17. 	return count;
  18. }
  19.  
  20.  
  21.  
  22. int main(){
  23.  
  24. unsigned long double result = 0.0;
  25. unsigned long double x = 1.0;
  26. unsigned long double y = 1.0;
  27. unsigned long double result2 = 0.0;
  28. int count(0);
  29. for(int i = 3;;i++)
  30. {
  31. 	result = x+y;
  32. 	y = x;
  33. 	x = result;
  34. 	result2 = result;
  35. 	cout<<setprecision(10)<<"F of "<<i<<" is : "<<result/1000000<<"	count is : "<<countdigits(result2)<<endl;
  36.  
  37. 	if(( countdigits(result2) == 1000 ) )
  38. 	{
  39.  
  40. 		cin.get();
  41. 	}
  42.  
  43.  
  44. }
  45.  
  46. return 0;
  47. }

try running the program to get a better understanding , and then maybe you can help be better. thanks
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2008
Posts: 3,810
Reputation: VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute 
Solved Threads: 501
Featured Poster
VernonDozier VernonDozier is offline Offline
Senior Poster

Re: fibonocci sequence question

 
0
  #2
Jan 3rd, 2009
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2008
Posts: 1,400
Reputation: William Hemsworth has much to be proud of William Hemsworth has much to be proud of William Hemsworth has much to be proud of William Hemsworth has much to be proud of William Hemsworth has much to be proud of William Hemsworth has much to be proud of William Hemsworth has much to be proud of William Hemsworth has much to be proud of William Hemsworth has much to be proud of 
Solved Threads: 113
Sponsor
William Hemsworth William Hemsworth is offline Offline
Nearly a Posting Virtuoso

Re: fibonocci sequence question

 
0
  #3
Jan 3rd, 2009
C++ Syntax (Toggle Plain Text) 
  1. unsigned long double result = 0.0;
  2. unsigned long double x = 1.0;
  3. unsigned long double y = 1.0;
  4. 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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2005
Posts: 5,850
Reputation: Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute 
Solved Threads: 749
Team Colleague
Salem's Avatar
Salem Salem is offline Offline
Void main'ers are DOOMed

Re: fibonocci sequence question

 
0
  #4
Jan 3rd, 2009
If
n! is n * fac(n-1);

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

If you use log10, it's even better
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2009
Posts: 4
Reputation: aryansmit3754 is an unknown quantity at this point 
Solved Threads: 0
aryansmit3754 aryansmit3754 is offline Offline
Newbie Poster

Re: fibonocci sequence question

 
-1
  #5
Jan 7th, 2009
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;
}
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Other Threads in the C++ Forum
Thread Tools Search this Thread



api array based beginner binary c++ c/c++ calculator char char* class classes code compile compiler console conversion count delete deploy desktop directshow dll download dynamic dynamiccharacterarray email encryption error file forms fstream function functions game givemetehcodez google graph gui homeworkhelp homeworkhelper iamthwee ifstream input int integer java lib linkedlist linker linux list loop looping loops map math matrix memory news numbertoword output parameter pointer problem program programming project proxy python random read recursion recursive reference return rpg sorting string strings struct temperature template templates test text text-file tree unix url variable vector video visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC