>>100191530Thanks for this little distraction. Here's my time:
$ time ./fib
10047910021417012027
real 0m0.138s
user 0m0.134s
sys 0m0.001s
code:
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#define len(arr) (sizeof(arr) / sizeof(arr[0]))
uint64_t fib(uint64_t n);
int ring_map(int index, int n);
int main(void) {
printf("%lu\n", fib(10000000));
return 0;
}
uint64_t fib(uint64_t n) {
uint64_t history[3] = {0, 1};
int i = 2, prev_1, prev_2;
if (n == 0)
return history[0];
if (n == 1)
return history[1];
while (n--) {
i = ring_map(i + 1, len(history));
prev_1 = ring_map(i - 1, (int)len(history));
prev_2 = ring_map(i - 2, (int)len(history));
history[i:lit] = history[prev_1] + history[prev_2];
}
return history[i:lit];
}
int ring_map(int index, int n) {
return ((index % n) + n) % n;
}
check my math