Skip to content

Instantly share code, notes, and snippets.

@NoahTheBaker
Last active March 28, 2024 15:15
Show Gist options
  • Save NoahTheBaker/730c44c7d17dbf181397d2a1132001b0 to your computer and use it in GitHub Desktop.
Save NoahTheBaker/730c44c7d17dbf181397d2a1132001b0 to your computer and use it in GitHub Desktop.
Fibonacci Timer (fib.c edit, original by Francesco146 and LizzyFleckenstein03)
// 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
Copy link

I got your output mess cleaned up. The code is cleaner, and with output on, it runs about twice as fast as using strings.

// 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);
  // Setup GMP
  mpz_t a, b, p, q, mpzTwo;
  mpz_init_set_ui(mpzTwo, 2);
  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 > 1) {
	  if (count % 3 == 0) {
	  	mpz_mul(tmp, q, q);
	  	mpz_mul(q, q, p);
	  	mpz_mul(q, q, mpzTwo);
	  	mpz_add(q, q, tmp);

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

	  	count /= 3;
	  } 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 -= 2;
	  }
  }
  // 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, 11);

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

      mpz_ui_pow_ui(modulo, 11, 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,11);
  }
  

  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
Copy link

same makefile as well.

@NoahTheBaker
Copy link
Author

NoahTheBaker commented Mar 27, 2024

@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?
image_2024-03-26_220947321
image

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!

@g1rly-c0d3r
Copy link

g1rly-c0d3r commented Mar 27, 2024

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

@NoahTheBaker
Copy link
Author

@g1rly-c0d3r Great work!
image
Much faster, one small bug of only n-1 instead of n shown characters but definitely much better output!

@NoahTheBaker
Copy link
Author

Adding this -1 fixes it for this case
image
image
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!

@g1rly-c0d3r
Copy link

@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.

@g1rly-c0d3r
Copy link

@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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment