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;
}

@Francesco146 I believe I used the latest one you posted (Oct 27th), at least that's the last one I see aside from your timing script? I could be pulling a dumb

@Francesco146 I believe I used the latest one you posted (Oct 27th), at least that's the last one I see aside from your timing script? I could be pulling a dumb

after the bit-shift analysis, I replaced the 0.5 with that, I'll send you the full version which I ask you to test right here. perhaps with some optimizations I made a simplification that changes the actual result. I would be happy if you decided to test it in order to exclude quick but incorrect calculations.

@Francesco146 I believe I used the latest one you posted (Oct 27th), at least that's the last one I see aside from your timing script? I could be pulling a dumb

after the bit-shift analysis, I replaced the 0.5 with that, I'll send you the full version which I ask you to test right here. perhaps with some optimizations I made a simplification that changes the actual result. I would be happy if you decided to test it in order to exclude quick but incorrect calculations.

3rd Edit: Fixed a mistake I made
When running your code it gives the following values:

./fibtest.exe 15      
fib(15): 0.000000 seconds
0
./fibtest.exe 30
fib(30): 0.000000 seconds
610
./fibtest.exe 1000
fib(1000): 0.000000 seconds
700601527838707533318724871765523284890968696066716357168446685359555050818763462119969522887130023714
./fibtest.exe 10000
fib(10000): 0.000000 seconds
511865913905822858393252140857692303019370496328583286846703611276316160829121874839117811096377890223341760784520464441363883635008221595005409607506796552046773590457456727956781799070386310526276130521173224078490428727580439211685193830890011304948013193753096345077838097891781185513053353450228725836492609250758663599068124138189622708238726010261183052860309857905748834

But running my code gives:

./fib.exe 15    
Fibonacci Value: 610
Number of Digits: 3
Calculation Time: 0.0000 seconds
Total Time Taken: 0.0020 seconds
./fib.exe 30
Fibonacci Value: 832040
Number of Digits: 6
Calculation Time: 0.0000 seconds
Total Time Taken: 0.0020 seconds
./fib.exe 1000     
Fibonacci Value: 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
Number of Digits: 209
./fib.exe 10000
Fibonacci Value: 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088.....
Number of Digits: 2090
Calculation Time: 0.0000 seconds
Total Time Taken: 0.0520 seconds

And checking with WolframAlpha gives:

fib(15) = 610
fib(30) = 832040
fib(1000) = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
fib(10000) = 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088.....

2nd Edit: Here is the current version that I am using with verified Fibonacci values up to F(100,000,000), but I cannot check further than that as WolframAlpha seems to break.

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