Fibonacci Timer (fib.c edit, original by Francesco146 and LizzyFleckenstein03)

fib.c

// NoahTheBaker's edit of Francesco146 and LizzyFleckenstein03's code
// Calculate Fibonacci Numbers
// Public Domain
// https://creativecommons.org/publicdomain/zero/1.0/
#include <stdio.h>
#include <ctype.h>
#include <gmp.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

int main(int argc, char *argv[])
{
    //OUTPUT CONSTANTS: Setting either of these to 1 severely slows the total time down around 3x because of huge string I/O
    //If FIB_OUTPUT is set to 1 then COUNT_DIGITS is as well, however FIB_OUTPUT can remain 0 while COUNT_DIGITS is 1. 
    //Set both to 0 for only benchmarks, COUNT_DIGITS to 1 just for the # of digits in Fib(x), or FIB_OUTPUT to output the actual result trimmed to the DIGIT_LIMIT.
    //todo: do better, man
    int FIB_OUTPUT = 1;
    int COUNT_DIGITS = 1;
    //Where to truncate Fib Value, set to 0 for all digits (will be very laggy with large values)
    const int DIGIT_LIMIT = 100;

    const clock_t full_time_start = clock();
    // Get User Input
    if (argc != 2)
    {
        fprintf(stderr, "Usage: %s <number>\n", argv[0]);
        return EXIT_FAILURE;
    }
    long count = strtol(argv[1], NULL, 10);
    // Setup GMP
    mpz_t a, b, p, q;
    mpz_init_set_ui(a, 1);
    mpz_init_set_ui(b, 0);
    mpz_init_set_ui(p, 0);
    mpz_init_set_ui(q, 1);
    mpz_t tmp;
    mpz_init(tmp);
    // Start timing
    const clock_t start_time = clock();
    while (count > 0) {
		if (count % 2 == 0) {
			mpz_mul(tmp, q, q);
			mpz_mul(q, q, p);
			mpz_mul_2exp(q, q, 1);
			mpz_add(q, q, tmp);

			mpz_mul(p, p, p);
			mpz_add(p, p, tmp);

			count /= 2;
		} else {
			mpz_mul(tmp, a, q);

			mpz_mul(a, a, p);
			mpz_addmul(a, b, q);
			mpz_add(a, a, tmp);

			mpz_mul(b, b, p);
			mpz_add(b, b, tmp);

			count -= 1;
		}
   	}
    // End timing
    const clock_t end_time = clock();
    if (end_time == (clock_t){-1})
    {
        fprintf(stderr, "Error end_time clock()\n");
        return EXIT_FAILURE;
    }

    //Digit counting and Fib Value Output

    char *str;
    unsigned int digits = 0;

    //Todo: fix this mess
    if(COUNT_DIGITS == 1 || FIB_OUTPUT == 1){
        str = mpz_get_str(NULL, 10, b);
        char out[DIGIT_LIMIT+5];
        
        if(FIB_OUTPUT == 1){
            COUNT_DIGITS = 1;
        }

        if(COUNT_DIGITS == 1){
                digits = strlen(str);
        }

        if(FIB_OUTPUT == 1){

            if(digits > DIGIT_LIMIT && DIGIT_LIMIT != 0){
                for(int i = 0; i < DIGIT_LIMIT/2; i++){
                    out[i] = str[i];
                }
                for(int i = DIGIT_LIMIT/2; i < (DIGIT_LIMIT/2 + 5); i++){
                    out[i] = '.';
                }
                for(int i = (DIGIT_LIMIT/2 + 5); i <= DIGIT_LIMIT + 5; i++){
                    out[i] = str[(digits - (DIGIT_LIMIT+6)) + i + 1];
                }
                printf("Fibonacci Value: %s", out);
            } else {
                printf("Fibonacci Value: %s", str);
            }
            
        }
    }

    printf("\n");
    // Cleanup
    mpz_clear(a);
    mpz_clear(b);
    mpz_clear(p);
    mpz_clear(q);
    mpz_clear(tmp);
    
    //Print Digit Count
    if(COUNT_DIGITS == 1){
        if(digits > DIGIT_LIMIT && DIGIT_LIMIT != 0){
            printf("Number of Digits: %u (%u Shown, %u in .....)\n", digits, DIGIT_LIMIT, (digits - DIGIT_LIMIT));
        } else {
            printf("Number of Digits: %u\n", digits);
        }
    }

    // Print time taken
    const double time_taken = ((double) (end_time - start_time)) / (double) CLOCKS_PER_SEC;
    if (printf("Calculation Time: %.4lf seconds\n", time_taken) < 0) 
        return EXIT_FAILURE;
    if (fflush(stdout) == EOF) 
        return EXIT_FAILURE;
    
    //End total time
    const clock_t full_time_end = clock();
    const double full_time_taken = ((double) (full_time_end - full_time_start)) / (double) CLOCKS_PER_SEC;

    //Print total time
    printf("Total Time Taken: %.4lf seconds\n", full_time_taken);
	return EXIT_SUCCESS;
}

@g1rly-c0d3r Great work!

Much faster, one small bug of only n-1 instead of n shown characters but definitely much better output!

Adding this -1 fixes it for this case


Except now I notice that for this one and only case for fib(1,000,000,000) it shows the # of digits + 1 (208987641 instead of 208987640). Weird!

@NoahTheBaker That is super weird, especially if that is the only case. I don't think I have time to look at that tonight, but it is very interesting.

@NoahTheBaker I compared fib(1,000,000,000) generated by your code to fib(1,000,000,000) generated by my code, and they do give the same number. My guess would be there's some difference in mpz_get_string and mpz_sizeinbase.