Fibonacci Program

README.md

Fib

Simple fibonacci number calculator.

Usage: fib nth Fibonacci number

fib.c

// Calculate Fibonacci Numbers 
// Public Domain
// https://creativecommons.org/publicdomain/zero/1.0/
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <ctype.h>
#include <gmp.h>
#include <time.h>

long limit, i = 0;

int main(int argc, char *argv[])
{
	// Get User Input 
	if (argc != 2)
	{
		printf("Improper input. Exiting.\n");
		return -1; 
	}

	limit = strtol(argv[1], NULL, 10);

	// Setup GMP 
	mpz_t a, b, c;
	mpz_init_set_ui(a, 1);
    mpz_init_set_ui(b, 0);
   	mpz_init(c);

    // Start timing 
    clock_t start_time = clock();

   	for (i = 0; i < limit; i++)
   	{
   		// Perform the Fibonacci Calculation
   		mpz_add(c, a, b);
   		mpz_set(a, b);
   		mpz_set(b, c);
   	}

    // End timing 
    clock_t end_time = clock(); 

	// Print the results to stdout
   	printf("Fibonacci Number %ld: ", i);
   	mpz_out_str(stdout, 10, b);
   	printf("\n");

	// Cleanup
   	mpz_clear(a);
   	mpz_clear(b);
   	mpz_clear(c);

    // Print time taaken 
    double time_taken = ((double) end_time - start_time)  / CLOCKS_PER_SEC;
    printf("Calculation Time: %f seconds\n", time_taken);
	
	
	return 0;
}

GMP function mpz_fib_ui() does the same computation. Here's how they compare on my slowest laptop:

./fib     100000000
Calculation Time: 6.037008 seconds
./fib-gmp 100000000
Calculation Time: 1.592325 seconds
./fib     1000000000
Calculation Time: 82.556466 seconds
./fib-gmp 1000000000
Calculation Time: 20.184274 seconds

It uses the low-level mpn_*() functions with lots of bit shifting and manual memory allocations. A lot of optimization work appears to have gone into it.

See https://gmplib.org/repo/gmp/file/tip/mpz/fib_ui.c

@NoahTheBaker i couldn't find the problem in my optimization, you came to what conclusion?

@Francesco146 Sorry to necro, basically I couldn't get your version to give me the right output. If you look through my examples from my last comment your code gives fib(15) = 0 and fib(30) = 610 when the correct answer should be fib(15) = 610 and fib(30) = 832,040. Not sure what's wrong and if it's only on my end.

The bug in @Francesco146 's code is this line:

if (count & 1)

To fix: change it to

if (!(count & 1))

oh, i almost forgot about this project.. I'll test your suggestions asap, thanks