This is becoming a "fixed size circular queue". But maybe a
modulus is faster than a branch here.
I have tried, and it's slower both in D and C. I don't know why.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
uint64_t hFib(const uint32_t k, const uint32_t n) {
uint64_t *nums = calloc(k + 1, sizeof(uint64_t));
if (nums == NULL)
exit(1);
uint32_t iter = k;
nums[k] = 1;
uint64_t total = 1;
for (uint32_t i = k; i < n + 1; i++) {
const uint32_t iter_next = (iter + 1 > k) ? 0 : (iter +
1);
total += nums[iter] - nums[iter_next];
nums[iter_next] = total % 100000000LLU;
iter = iter_next;
}
return nums[iter];
}
int main() {
printf("%llu\n", hFib(100, 10000));
printf("%llu\n", hFib(1594323, 9765625));
return 0;
}
Runtime of this C version: about 240 ms.
Bye,
bearophile
