rounding problem in C++

M

moscro

n00b
Joined
Oct 31, 2006
Messages
2
Hey guys,
I'd first like to apologize for being a complete noob at C++. I'm a C++ student who has had mild experience from the past, but unfortunately I have a teacher who has a bit of a language barrier. I've been able to figure things out okay to a point, but now I am at a loss. I really appreciate any and all help that you can offer.

Here's the assignment:
I'm supposed to write a program that asks the user which number from the fibonacci number series he/she would like. This number is limited to 0-96. I'm also supposed to use separate functions, and output is not allowed anywhere but the main function, hence the use of the second function. The output is not supposed to be in scientific form, and is not supposed to have any decimals at the end. The assignment suggests using long doubles, and as I know of no other variable types that will accomplish what is asked, I've used their advice. I'm also allowed to hard code for the numbers 0 and 1, which is why the if statements in the second function take care of those numbers.

Here's how far i've gotten:
I've written all of the code needed to fulfill the assignment. However, I am coming across a rounding issue with anything above number 78 in the series. Here is my code:

#include<iostream>
using namespace std;
#include<iomanip>

long double whichfib(int fib);

int main()
{
int fibNum;
cout << fixed << setprecision(0);
do
{
cout << "Which Fibonacci number would you like? ";
cin >> fibNum;
}while (fibNum < 0 || fibNum >= 97);

cout << "Fibonacci #" << fibNum << " is " << whichfib(fibNum) << endl;
return 0;
}

long double whichfib(int fibNum)
{
long double ans;
long double fib1 = 0;
long double fib2 = 1;
long double final = 0;
int count = 2;

if (fibNum == 0)
{
ans = 0;
return ans;
}

if (fibNum == 1)
{
ans = 1;
return ans;
}


while (fibNum > 1)
{
final = fib1 + fib2;
fib1 = fib2;
fib2 = final;
ans = final;
/*cout << "\nans is " << ans << " at number " << count++ << " in the series\n"; */
fibNum--;
}

return ans;
}


Now, the commented cout statement on the second function is used for diagnostics in this program only. It will be deleted before I submit it to the teacher. This is how I discovered that it started rounding at #79, and grew only progressively worse.

Here is the problem: At number 79, the answer is supposed to be 14472334024676221. However, my program outputs 14472334024676220. It gets progressively worse from there. By the time it gets to number 96, which is 51680708854858323072, it outputs 51680708854858326000, which is WAY off. I've tried modifying the variable at number 79 by telling it to increment by one, but it doesn't accept that. I've tried long long ints, those don't work. I'm racking my brains and beating my book to a pulp to figure out a solution to this one, but I haven't found anything yet. Any suggestions are welcome, thanks for your help!

Mos
 
Still, keep it in mind. Double is for floating-point numbers, and like all floats, it has a limited precision.

Edit: Line generelz said, an unsigned 64-bit int works. Try "unsigned long long int" or "uint64_t". Which OS and compiler are you using?

Using this code:
Code: 
#include<iostream>
#include<iomanip>
using namespace std;
 
unsigned long long int whichfib(int fib);
 
 int main() {
	int fibNum;
	cout << fixed << setprecision(0);
	do {
		cout << "Which Fibonacci number would you like? ";
		cin >> fibNum;
	} while (fibNum < 0 || fibNum >= 97);
	cout << "Fibonacci #" << fibNum << " is " << whichfib(fibNum) << endl;
	return 0;
}
	
unsigned long long int whichfib(int fibNum) {
	unsigned long long int ans;
	unsigned long long int fib1 = 0;
	unsigned long long int fib2 = 1;
	unsigned long long int final = 0;
	int count = 2;
	
	ans = fibNum;
	while (fibNum > 1) {
		final = fib1 + fib2;
		fib1 = fib2;
		fib2 = final;
		ans = final;
		cout << "ans is " << ans << " at number " << count++ << " in the series\n"; 
		fibNum--;
	}
	return ans;
 }

I get these results:
Code: 
ans is 5527939700884757 at number 77 in the series
ans is 8944394323791464 at number 78 in the series
ans is 14472334024676221 at number 79 in the series
ans is 23416728348467685 at number 80 in the series
Fibonacci #80 is 23416728348467685

BTW, use [code ] [/code ] - tags when you paste code here, it makes it a bit easier to read.

edit again:
The highest correct answer before that, too, overflows is fib(93).
 
New post, just to reduce the clutter a bit:
If you still need bigger numbers, you will have to use a bignum library, like GMP.
By adding "#incude <gmpxx.h>" and replacing the "unsigned long long int" above with "mpz_class", it gives a correct answer to e.g fib(1000). (I got an answer that looks plausible for fib(100000), too, but I have no way of verifying it.)

I had to compile it with "c++ -lgmpxx -lgmp -I/usr/local/include -L/usr/local/lib fib.cpp -o fib", but that depends on your OS.
 
The fibonnaci problem is a common example in computer science. I don't know where you go to school, but the CS department at my alma mater (Mississippi State) taught how to handle these problems as part of the Discrete Structures (Discrete Mathematics) course.

One of the post-doc professors there teaches the course and he's got some really good notes on it.

You can find them at :http://www.cse.msstate.edu/~cse2813/fall06/schedule.html Scroll down and look at his section on recurrence relations. I think that you'll find that while you're on the correct track, you might be able to streamline the logic (and the datatypes) a bit.

edit: I threw together some quick code before I headed out the door to work. In your whichfib() method, if you give it an unsigned long return type and use unsigned longs inside, I was able to vet (by hand) the results up to element 50 in the list as being correct. I didn't get a chance to check any more, but it didn't appear that there was any unsaturated overflow occuring.
 
You must log in or register to reply here.
Back
Top