fib.c

Last Updated: 19 June 2026

One of my most popular YouTube videos is my demonstration of a fast Fibonacci number finder in C. The code is available below and on GitHub. With clever programming (and with GMP -- the GNU Multiple Precision Arithmetic Library, as well as refinements from others), this program can calculate, and print out, Fibonacci numbers with millions of digits in fractions of a second. The algorithm is based on the fast doubling method, which allows us to compute Fibonacci numbers in logarithmic time. Ie: O log n.

The results speak for themselves. The 100 millionth fibonacci number is calculated and printed to standard out in 1.46 seconds on my machine.

This is a number with over 20 million digits, and that if we pipe to a file yeilds us a twenty megabyte text file.

If we search for the five billionth Fibonacci number, we get a number with over 1.04 billion digits. It takes just 1 minute and 56 seconds to calculate and print this almighty number, and the resulting text file is over a full gigabyte in size.

Developed on Linux and cross-compiled to Windows and MS-DOS.

Video Demo

Source Code


/*
Calculate Fibonacci Numbers
Originally written by Softwave (https://s0ftwave.net/)
(https://github.com/Softwave)
Additions by by Francesco146] (https://github.com/Francesco146)
and LizzyFleckenstein03 (https://github.com/LizzyFleckenstein03)
And more by Softwave ^_^
Public Domain
https://creativecommons.org/publicdomain/zero/1.0/
Last updated: 19 June 2026
*/

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <gmp.h>

#ifdef _WIN32
#include <windows.h>
static double now_seconds(void)
{
    LARGE_INTEGER freq, t;
    QueryPerformanceFrequency(&freq);
    QueryPerformanceCounter(&t);
    return (double) t.QuadPart / (double) freq.QuadPart;
}
#else
#include <time.h>
static double now_seconds(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double) ts.tv_sec + (double) ts.tv_nsec / 1e9;
}
#endif

int main(int argc, char *argv[])
{
    // Get User Input
    if (argc < 2 || argc > 3)
    {
        printf("usage: %s [-p] NUM\n", argv[0]);
        return EXIT_FAILURE;
    }

    int plain = 0;
    char *num_arg = NULL;

    if (argc == 3)
    {
        if (strcmp(argv[1], "-p") == 0 || strcmp(argv[1], "--plain") == 0)
        {
            plain = 1;
        }
        else
        {
            printf("usage: %s [-p] NUM\n", argv[0]);
            return EXIT_FAILURE;
        }
        num_arg = argv[2];
    }
    else
    {
        num_arg = argv[1];
    }

    long count = strtol(num_arg, 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 double start_time = now_seconds();

    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 double end_time = now_seconds();

    // Print the result to standard out
    mpz_out_str(stdout, 10, b);
    printf("\n");

    // Cleanup
    mpz_clear(a);
    mpz_clear(b);
    mpz_clear(p);
    mpz_clear(q);
    mpz_clear(tmp);

    // Print time taken (unless plain mode)
    if (!plain)
    {
        const double time_taken = end_time - start_time;
        if (printf("Calculation Time: %lf seconds\n", time_taken) < 0)
        {
            return EXIT_FAILURE;
        }
        if (fflush(stdout) == EOF)
        {
            return EXIT_FAILURE;
        }
    }

    return EXIT_SUCCESS;
}