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

Makefile

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

tester.sh

#!/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 "----------------------------------------"