Thread: fibonacci(10,000)

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    41

    fibonacci(10,000)

    Greetings,

    Ok I know how to code fibonacci using both iterative and recursive functions. However, I have no idea how to go about calculating the 10,000 fibonacci. That is a very very very big number. I think I may have to use an array of sometype to solve this because i dont think visual studios has a data type that can handle such a gigantic number. But I dont know how to begin. If any you could provide insight and suggestions I would greatly appreciate it. Thanks.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Use a bignum library - http://www.swox.com/gmp/
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User MathFan's Avatar
    Join Date
    Apr 2002
    Posts
    190
    Take a look at this page http://www.codearchive.com/list.php?go=0716. - almost at the bottom of it. Here you can download source code of an example program that can handle really large fibonacci numbers.

    Here is some more source code you can look at http://sourceforge.net/project/showf...kage_id=125989


    Hope this helps
    The OS requirements were Windows Vista Ultimate or better, so we used Linux.

  4. #4
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Quote Originally Posted by blindman858
    Greetings,

    Ok I know how to code fibonacci using both iterative and recursive functions. However, I have no idea how to go about calculating the 10,000 fibonacci. That is a very very very big number. I think I may have to use an array of sometype to solve this because i dont think visual studios has a data type that can handle such a gigantic number. But I dont know how to begin. If any you could provide insight and suggestions I would greatly appreciate it. Thanks.
    To calculate a fibonacci of this size you don't use an iterative or recursive approach. Instead you find the formula that lets you solve directly.

    http://en.wikipedia.org/wiki/Fibonacci_number

    And of course you use bignum libraries

  5. #5
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    I've already done this long time ago
    Code:
    #include<stdio.h>
    
    #define SIZE_NUM 1000000000
    #define VECTOR_DIM 234//enough to hold fib(10000)
    
    /*MACRO output number*/
    #define display_arr(vec)\
    	/*display the array code*/
    
    				
    int main()
    {
    	int i=-1, opt;
    	int indfin=1, ref=1;
    	unsigned int n0[VECTOR_DIM] = {0}, n1[VECTOR_DIM] = {1};
    	unsigned int temp;
    
    	scanf("%d", &opt);
    
    	if(!opt)
    	printf("The Fibonacci number for 0 is 0");
    	else{
    		while(i++<opt){/*sum cicle*/
    			/*...............*/
    		}
    		
    		/*	display*/
    		printf("The Fibonacci number for %d is ", opt);
    		if(ref)  display_arr(n0)
    		else   display_arr(n1)
    	}
    	putchar('\n');
    	
    	getchar();
    	return 0;
    }
    Beg for the full source if you want

Popular pages Recent additions subscribe to a feed