fib.c

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

uint64_t* fibs;
size_t fib_len;

int
expand_fibs(uint64_t x)
{
    uint64_t* new_fibs;
    uint64_t n = x + 1;

    if (n < fib_len)
        return 0;
    if (n < 2)
        n = 2;
    new_fibs = realloc(fibs, sizeof(*fibs) * n);
    if (!new_fibs) {
        fprintf(stderr, "alloc\n");
        return -1;
    }
    if (fib_len < 2) {
        new_fibs[0] = 0;
        new_fibs[1] = 1;
        fib_len = 2;
    }
    for (; fib_len < n; ++fib_len) {
        new_fibs[fib_len] = new_fibs[fib_len - 1] + new_fibs[fib_len - 2];
        if (new_fibs[fib_len] < new_fibs[fib_len - 1]) {
            fprintf(stderr, "overflow\n");
            return -1;
        }
    }
    fibs = new_fibs;
    return 0;
}

uint64_t
fib(uint64_t x)
{
    if (fib_len <= x) {
        if (-1 == expand_fibs(x)) {
            exit(1);
        }
    }
    return fibs[x];
}


int main() {
    int i;
    printf("%20c %llx\n\n", ' ', ~0ull);
    for (i = 0; i <= 0x5d; ++i) {
        printf("%20" PRIu64 " %-16" PRIx64 "\n", fib(i), fib(0x5d - i));
    }
    printf("\n%llu\n", ~0ull);
    return 0;
}