* ---- Fibonacci Numbers ---- *

TimHDG · #1 21-Nov-2004, 10:47

I need help processing large numbers with my code:

CPP / C++ / C Code:

/*****************************\
* ---- Fibonacci Numbers ---- *
* ------- 11/21/2004 -------- *
*                             *
*   This program calculates   *
*      fibonacci numbers      *
*                             *
\*****************************/

#include <stdio.h>
#include <conio.h>
#include <process.h>

int main(){

	unsigned double num1 = 0, num2 = 1, ans = 0, count, reps;

	printf(" Fibonacci Numbers \n\n");
	printf(" How many numbers would you like to calculate?\t\n");
	scanf("%lf", &reps);

	for(count = 0; count <= reps; ++count){
		
		ans = num1 + num2;
		
		printf("\n%.0lf", ans);
		
		num1 = num2;
		num2 = ans;
		}
	return 0;
}

around the 90th number calulated the numbers seems to become inaccurate.

please help

davekw7x · #2 21-Nov-2004, 13:34

Quote:

Originally Posted by TimHDG

I need help processing large numbers with my code:

around the 90th number calulated the numbers seems to become inaccurate.

please help

What's an "unsigned double"? My compilers choked on this. So I just used "double"

Actually, with standard doubles, you start picking up roundoff errors about fibonacci numberr 79.

Here are a few numbers (exact):

78 : 8944394323791464
79 : 14472334024676221
80 : 23416728348467685

Here's what I got from running your program (double precision):

78 8944394323791464
79 14472334024676220
80 23416728348467684

The maximum integer that can be represented exactly is

17976931348623158

so I am not surprised to see things starting to fall apart about this value.

(This is no fault of your code; it is a fundamental limitation of the standard types of variables represented in my computer --- probably yours too.)

If you can use long doubles, you may get about three more significant digits but you are still going to run out of precision at about number 90.

[edit]
Exact numbers:

92 : 7540113804746346429
93 : 12200160415121876738
94 : 19740274219868223167

Calculation with long doubles gives:

92 7540113804746346429
93 12200160415121876740
94 19740274219868223170
[/edit]

If you want more precision, use or implement a multiple-precision arithmetic package. Digits are held as array elements and addition, multiplication, etc. are carried out digit-by-digit. Precision is limited only by the amount of memory on your machine (and your compiler's ability to handle large memory arrays).

I like exercises because they make us think about all of those numbers spinning around inside the computer, and make us (well, me at least) think about "what does all of this really mean."

Regards,

Dave

================================================

"The purpose of computing is insight not numbers."

---Richard W. Hamming

================================================

"Everything is made of little numbers, whizzing around so fast that they
become stuff.

---Terry Pratchett
The Truth

================================================

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
prime numbers	quasimof	C++ Forum	1	01-Nov-2004 19:35
Help with random numbers	da_bomb50	MySQL / PHP Forum	3	04-Aug-2004 19:34
Factorial of numbers	cior	C++ Forum	7	09-Jun-2004 20:08
[CONTEST?]Data Structure Test	dsmith	C Programming Language	2	06-Jun-2004 15:13
Best way to validate numbers (ids)?	JdS	MySQL / PHP Forum	1	20-Jan-2003 03:55