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

same makefile as well.

@g1rly-c0d3r Trying out your code it doesn't seem to be returning the proper Fibonacci value (fib.exe is my old one, fibtest2.exe is your provided code). Not sure if this is a problem just for me, would you mind checking the values you get against WolframAlpha or something?

But I admit I definitely could have done the output better, the digit counting and output change was just a quick fun edit I slapped together :) glad you're carrying on the torch and trying to improve it though!

thats my mistake, i somehow incrimented all of the numbers in the source file, here is the corrected code

// g1rly-c0d3r's edit of 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>
#include <stdbool.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
  bool FIB_OUTPUT = 1;
  bool COUNT_DIGITS = 1;
  //Where to truncate Fib Value, set to 0 for all digits (will be very laggy with large values)
  const size_t 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);
  //long count = 12;
  // 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){0})
  {
      fprintf(stderr, "Error end_time clock()\n");
      return EXIT_FAILURE;
  }

  //Digit counting and Fib Value Output

  size_t digits = 1;
  mpz_t mostSig, leastSig,modulo;
  mpz_init(mostSig);
  mpz_init(leastSig);
  mpz_init(modulo);

  if(FIB_OUTPUT){
    digits = mpz_sizeinbase(b, 10);

    if(digits > DIGIT_LIMIT && DIGIT_LIMIT != 1){
      mpz_ui_pow_ui(modulo, 10, digits - DIGIT_LIMIT/2);
      mpz_tdiv_q(mostSig,b,modulo);

      mpz_ui_pow_ui(modulo, 10, DIGIT_LIMIT/2);
      mpz_mod(leastSig,b,modulo);

      gmp_printf("Fibonacci Value: %Zd.....%Zd", mostSig, leastSig);
    } else {
      gmp_printf("Fibonacci Value: %Zd", b);
    }
  }
  else if (COUNT_DIGITS) {
    digits = mpz_sizeinbase(b,10);
  }
  

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

  // Print time taken
  const double time_taken = ((double) (end_time - start_time)) / (double) CLOCKS_PER_SEC;
  if (printf("Calculation Time: %.5lf 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: %.5lf 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.