fib-bigint.c

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#define NOB_IMPLEMENTATION
#include "nob.h"

#define BIGINT_BASE 1000000000000000000ULL

typedef struct {
    uint64_t *items;
    size_t count;
    size_t capacity;
} Bigint;

void bigint_print(Bigint a)
{
    for (size_t i = 0; i < a.count; ++i) {
        // if (i > 0) printf("|");
        if (i == 0) {
            printf("%"PRIu64, a.items[a.count - i - 1]);
        } else {
            printf("%018"PRIu64, a.items[a.count - i - 1]);
        }
    }
    printf("\n");
}

void bigint_add(Bigint *a, Bigint b)
{
    // a = 12345....
    // b = 12345..
    uint64_t carry = 0;
    size_t n = a->count;
    if (n > b.count) n = b.count;
    for (size_t i = 0; i < n; ++i) {
        uint64_t c = a->items[i] + b.items[i] + carry;
        a->items[i] = c%BIGINT_BASE;
        carry = c/BIGINT_BASE;
    }
    if (a->count < b.count) {
        for (size_t i = n; i < b.count; ++i) {
            uint64_t c = b.items[i] + carry;
            da_append(a, c%BIGINT_BASE);
            carry = c/BIGINT_BASE;
        }
    } else if (a->count > b.count) {
        TODO("");
    }

    if (carry > 0) {
        da_append(a, carry);
    }
}

void bigint_copy(Bigint *a, Bigint b)
{
    a->count = 0;
    da_foreach(uint64_t, x, &b) {
        da_append(a, *x);
    }
}

int main()
{
    Bigint a = {0};
    Bigint b = {0};
    Bigint c = {0};
    da_append(&a, 0);
    da_append(&b, 1);
    for (size_t i = 0; i < 1000*1000; ++i) {
        bigint_copy (&c, a);
        bigint_add  (&c, b);
        bigint_copy (&a, b);
        bigint_copy (&b, c);
    }
    bigint_print(a);
    return 0;
}