Simple fibonacci number calculator.
Usage: fib nth Fibonacci number
-
-
Save Francesco146/4cf48443959be08de2d084a7488d16ab to your computer and use it in GitHub Desktop.
Fibonacci Program
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Calculate Fibonacci Numbers | |
| // Public Domain | |
| // https://creativecommons.org/publicdomain/zero/1.0/ | |
| #include <ctype.h> | |
| #include <stdio.h> | |
| #include <gmp.h> | |
| #include <stdint.h> | |
| #include <string.h> | |
| #include <unistd.h> | |
| #include <stdlib.h> | |
| #include <time.h> | |
| /* * | |
| * Here's some time I got: | |
| * fib(1): 0.000009 seconds | |
| * fib(10): 0.000009 seconds | |
| * fib(100): 0.000009 seconds | |
| * fib(1 000): 0.000011 seconds | |
| * fib(10 000): 0.000030 seconds | |
| * fib(100 000): 0.000193 seconds | |
| * fib(1 000 000): 0.004409 seconds | |
| * fib(10 000 000): 0.047819 seconds | |
| * fib(100 000 000): 0.704643 seconds | |
| * fib(1 000 000 000): 8.852119 seconds | |
| */ | |
| int main(int argc, char *argv[]) | |
| { | |
| _Bool need_result = 0; | |
| // Get User Input | |
| if (argc < 2 || argc > 3) | |
| { | |
| fprintf(stderr, "Usage: %s <number> [--need-result]\n", argv[0]); | |
| return EXIT_FAILURE; | |
| } | |
| if (argc == 3 && strcmp(argv[2], "--need-result") == 0) | |
| need_result = 1; | |
| 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 & 1) | |
| { | |
| 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 >>= 1; | |
| } | |
| 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; | |
| } | |
| // Print time taken | |
| const double time_taken = ((double) (end_time - start_time)) / (double) CLOCKS_PER_SEC; | |
| char buffer[100]; | |
| int len = sprintf(buffer, "fib(%s): %f seconds\n", argv[1], time_taken); | |
| if (write(STDOUT_FILENO, buffer, len) == -1) | |
| { | |
| fprintf(stderr, "Error write()\n"); | |
| return EXIT_FAILURE; | |
| } | |
| if (fflush(stdout) == EOF) | |
| return EXIT_FAILURE; | |
| // Check if --need-result option is provided | |
| if (need_result) | |
| { | |
| // open file to write the result (out.txt) | |
| FILE *fp; | |
| fp = fopen("out.txt", "w"); | |
| if (fp == NULL) | |
| { | |
| fprintf(stderr, "Error opening file\n"); | |
| return EXIT_FAILURE; | |
| } | |
| mpz_out_str(fp, 10, b); | |
| } | |
| // Cleanup | |
| mpz_clear(a); | |
| mpz_clear(b); | |
| mpz_clear(p); | |
| mpz_clear(q); | |
| mpz_clear(tmp); | |
| return EXIT_SUCCESS; | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| cc = gcc | |
| cc_standard = -std=c99 | |
| cc_optimization = -Ofast -march=native | |
| cc_link = -lgmp | |
| fib: fib.c | |
| ${cc} ${cc_standard} ${cc_optimization} $^ -o $@ ${cc_link} | |
| .PHONY: clean | |
| clean: | |
| rm -rf fib |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/bin/bash | |
| # Default values | |
| num_iterations=10000 | |
| max_fibonacci_number=100000 | |
| use_random=false | |
| # Function to display script usage | |
| display_help() { | |
| echo "Usage: $0 [OPTIONS]" | |
| echo "Options:" | |
| echo " --random Use random Fibonacci numbers." | |
| echo " -n, --iterations NUM Set the number of iterations (default: $num_iterations)." | |
| echo " -m, --max-fibonacci NUM Set the maximum Fibonacci number (default: $max_fibonacci_number)." | |
| echo " -h, --help Display this help message." | |
| exit 1 | |
| } | |
| # Process command-line options | |
| while [[ "$#" -gt 0 ]]; do | |
| case "$1" in | |
| --random) | |
| use_random=true | |
| ;; | |
| -n|--iterations) | |
| num_iterations="$2" | |
| shift | |
| ;; | |
| -m|--max-fibonacci) | |
| max_fibonacci_number="$2" | |
| shift | |
| ;; | |
| -h|--help) | |
| display_help | |
| ;; | |
| *) | |
| echo "Unknown option: $1" | |
| display_help | |
| ;; | |
| esac | |
| shift | |
| done | |
| make clean | |
| make | |
| # Run the program for the first time to initialize libraries and perform a warm-up | |
| ./fib $max_fibonacci_number &>/dev/null | |
| # Initialize the variable to accumulate total time | |
| total_time=0 | |
| # Run iterations and accumulate times | |
| for ((i=1; i<=$num_iterations; i++)); do | |
| if [ "$use_random" = true ]; then | |
| # Generate a random Fibonacci number within the specified range | |
| fibonacci_number=$(( (RANDOM % $max_fibonacci_number) + 1 )) | |
| else | |
| # Use a fixed Fibonacci number | |
| fibonacci_number=$max_fibonacci_number | |
| fi | |
| # Run the command and capture the time | |
| exec_time=$(./fib $fibonacci_number | awk '/seconds/ {print $2}') | |
| total_time=$(echo "$total_time + $exec_time" | bc -l) | |
| echo -ne "fib($fibonacci_number):\t$exec_time seconds\n" | |
| done | |
| # Calculate the average time | |
| average_time=$(awk "BEGIN {printf \"%.6f\", $total_time / $num_iterations}") | |
| echo "----------------------------------------" | |
| echo "Number of iterations: $num_iterations" | |
| if [ "$use_random" = true ]; then | |
| echo "Fibonacci number range: 1 to $max_fibonacci_number (randomly generated each time)" | |
| else | |
| echo "Fibonacci number: $max_fibonacci_number" | |
| fi | |
| echo "Average time: $average_time seconds" | |
| echo "----------------------------------------" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment