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 <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <ctype.h>
#include <gmp.h>
#include <time.h>

long limit, i = 0;

int main(int argc, char *argv[])
{
	// Get User Input 
	if (argc != 2)
	{
		printf("Improper input. Exiting.\n");
		return -1; 
	}

	limit = strtol(argv[1], NULL, 10);

	// Setup GMP 
	mpz_t a, b, c;
	mpz_init_set_ui(a, 1);
    mpz_init_set_ui(b, 0);
   	mpz_init(c);

    // Start timing 
    clock_t start_time = clock();

   	for (i = 0; i < limit; i++)
   	{
   		// Perform the Fibonacci Calculation
   		mpz_add(c, a, b);
   		mpz_set(a, b);
   		mpz_set(b, c);
   	}

    // End timing 
    clock_t end_time = clock(); 

	// Print the results to stdout
   	printf("Fibonacci Number %ld: ", i);
   	mpz_out_str(stdout, 10, b);
   	printf("\n");

	// Cleanup
   	mpz_clear(a);
   	mpz_clear(b);
   	mpz_clear(c);

    // Print time taaken 
    double time_taken = ((double) end_time - start_time)  / CLOCKS_PER_SEC;
    printf("Calculation Time: %f seconds\n", time_taken);
	
	
	return 0;
}

one of the most basic things a compiler does is change the /2 to a bitshift operation like you wanted to do, because yes it is faster, not sure why manually doing it on your end made it slower but trust that it is doing that optimization itself when you compile

so, i've done some research and did some experiments, here's what i got:

the compiler actually did something really stupid with the /2 and *0.5, making the assembly code unnecessarily long by doing some stuff with the floating pointer instruction:

vxorpd  xmm1, xmm1, xmm1
vcvtsi2sd xmm0, xmm1, r15
vmulsd  xmm2, xmm0, QWORD PTR .LC1[rip]
vcvttsd2si r15, xmm2
test    r15, r15
jg      .L7

so i manually inserted the count >>= 1; and ran 10'000 iterations of the code and calculated the average time:

1. fib(100000) - count >>= 1; : 0,000117 seconds
2. fib(100000) - count *= 0.5; : 0,000119 seconds
3. fib(100000) - count /= 2; : 0,000118 seconds

The times are really close, but the assembly code compiled is shorter than the others, soo that's it. I'll leave the tester script, capable of testing the speed of the code and stress it with the random mode.

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

also (not really important) i've added this, away from the time calculation, to the main fib.c file because we don't really need the actual value saved

    ...
    _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;

    ...


    // 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);
    }
    ...

if I had to guess I'd say there's some other smaller optimizations that go along with it but when you optimize for it it didn't recognize it and doesn't implement them

yes, i think that too. might also be that i run this code on ARM, and the M1 is doing stuff with Rosetta. hard to know

@Francesco146 did you check your output? it may be my compiler but it doesn't check to me

not sure what are you referring to, have you installed the basic libraries?

The instruction (count % 2 == 0) can be optimized with count & 1, and the instruction count /= 2; with count *= 0.5. I've tested and:

. . .
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 *= 0.5;
}
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
//.......
return EXIT_SUCCESS;
}

@Francesco146 Testing your code out I found some weird behavior (unless I'm misunderstanding something).

Here's the output of the above code (fibtest.exe) compared to a program I made with that and some other code in the comment chain (fib.exe). I checked the output of fib.exe with WolframAlpha to make sure the results were the correct element of the fib sequence.

./fibtest.exe 1
0
Calculation Time: 0.000000 seconds
./fib.exe 1    
1
Calculation Time: 0.000000 seconds
Number of Digits: 1
./fibtest.exe 2
1
Calculation Time: 0.000000 seconds
./fib.exe 2
1
Calculation Time: 0.000000 seconds
Number of Digits: 1
./fibtest.exe 5
1
Calculation Time: 0.000000 seconds
./fib.exe 5
5
Calculation Time: 0.000000 seconds
Number of Digits: 1
./fibtest.exe 6
2
Calculation Time: 0.000000 seconds
./fib.exe 6
8
Calculation Time: 0.000000 seconds
Number of Digits: 1
./fibtest.exe 15
0
Calculation Time: 0.000000 seconds
./fib.exe 15
610
Calculation Time: 0.000000 seconds
Number of Digits: 3
./fibtest.exe 30
610
Calculation Time: 0.000000 seconds
./fib.exe 30    
832040
Calculation Time: 0.001000 seconds
Number of Digits: 6

The code I used is here, it's a mix from @Francesco146 and @LizzyFleckenstein03:

// 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[])
{
    // 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;
    }
    mpz_out_str(stdout, 10, b);
    unsigned int digits = strlen(mpz_get_str(NULL, 10, b));
    printf("\n");
    // Cleanup
    mpz_clear(a);
    mpz_clear(b);
    mpz_clear(p);
    mpz_clear(q);
    mpz_clear(tmp);
    // Print time taken
    const double time_taken = ((double) (end_time - start_time)) / (double) CLOCKS_PER_SEC;
    if (printf("Calculation Time: %lf seconds\n", time_taken) < 0) 
        return EXIT_FAILURE;
    if (fflush(stdout) == EOF) 
        return EXIT_FAILURE;
    printf("Number of Digits: %u\n", digits);
	return EXIT_SUCCESS;
}

Which also gave me these times:

./fib.exe 100000
Calculation Time: 0.000000 seconds
Number of Digits: 20899
./fib.exe 1000000
Calculation Time: 0.008000 seconds
Number of Digits: 208988
./fib.exe 10000000
Calculation Time: 0.097000 seconds
Number of Digits: 2089877
./fib.exe 100000000
Calculation Time: 1.316000 seconds
Number of Digits: 20898764
./fib.exe 1000000000
Calculation Time: 16.641000 seconds
Number of Digits: 208987640

Fun!

@NoahTheBaker not sure what's going on here, can you test the latest code? that version is a bit outdated

@Francesco146 I believe I used the latest one you posted (Oct 27th), at least that's the last one I see aside from your timing script? I could be pulling a dumb

@Francesco146 I believe I used the latest one you posted (Oct 27th), at least that's the last one I see aside from your timing script? I could be pulling a dumb

after the bit-shift analysis, I replaced the 0.5 with that, I'll send you the full version which I ask you to test right here. perhaps with some optimizations I made a simplification that changes the actual result. I would be happy if you decided to test it in order to exclude quick but incorrect calculations.

@Francesco146 I believe I used the latest one you posted (Oct 27th), at least that's the last one I see aside from your timing script? I could be pulling a dumb

after the bit-shift analysis, I replaced the 0.5 with that, I'll send you the full version which I ask you to test right here. perhaps with some optimizations I made a simplification that changes the actual result. I would be happy if you decided to test it in order to exclude quick but incorrect calculations.

3rd Edit: Fixed a mistake I made
When running your code it gives the following values:

./fibtest.exe 15      
fib(15): 0.000000 seconds
0
./fibtest.exe 30
fib(30): 0.000000 seconds
610
./fibtest.exe 1000
fib(1000): 0.000000 seconds
700601527838707533318724871765523284890968696066716357168446685359555050818763462119969522887130023714
./fibtest.exe 10000
fib(10000): 0.000000 seconds
511865913905822858393252140857692303019370496328583286846703611276316160829121874839117811096377890223341760784520464441363883635008221595005409607506796552046773590457456727956781799070386310526276130521173224078490428727580439211685193830890011304948013193753096345077838097891781185513053353450228725836492609250758663599068124138189622708238726010261183052860309857905748834

But running my code gives:

./fib.exe 15    
Fibonacci Value: 610
Number of Digits: 3
Calculation Time: 0.0000 seconds
Total Time Taken: 0.0020 seconds
./fib.exe 30
Fibonacci Value: 832040
Number of Digits: 6
Calculation Time: 0.0000 seconds
Total Time Taken: 0.0020 seconds
./fib.exe 1000     
Fibonacci Value: 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
Number of Digits: 209
./fib.exe 10000
Fibonacci Value: 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088.....
Number of Digits: 2090
Calculation Time: 0.0000 seconds
Total Time Taken: 0.0520 seconds

And checking with WolframAlpha gives:

fib(15) = 610
fib(30) = 832040
fib(1000) = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
fib(10000) = 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088.....

2nd Edit: Here is the current version that I am using with verified Fibonacci values up to F(100,000,000), but I cannot check further than that as WolframAlpha seems to break.

GMP function mpz_fib_ui() does the same computation. Here's how they compare on my slowest laptop:

./fib     100000000
Calculation Time: 6.037008 seconds
./fib-gmp 100000000
Calculation Time: 1.592325 seconds
./fib     1000000000
Calculation Time: 82.556466 seconds
./fib-gmp 1000000000
Calculation Time: 20.184274 seconds

It uses the low-level mpn_*() functions with lots of bit shifting and manual memory allocations. A lot of optimization work appears to have gone into it.

See https://gmplib.org/repo/gmp/file/tip/mpz/fib_ui.c

@NoahTheBaker i couldn't find the problem in my optimization, you came to what conclusion?

@Francesco146 Sorry to necro, basically I couldn't get your version to give me the right output. If you look through my examples from my last comment your code gives fib(15) = 0 and fib(30) = 610 when the correct answer should be fib(15) = 610 and fib(30) = 832,040. Not sure what's wrong and if it's only on my end.