ixid:
It's a pity that the D standard library seems to lack rather a
lot of these things.
I've taken a better look at your code, for this program a deque
wasn't so needed.
This is quick:
import std.stdio;
ulong hFib(in uint k, in uint n) pure nothrow {
auto nums = new ulong[k + n + 1];
nums[k - 1] = 1;
ulong total = 1;
foreach (i; k .. n + 1) {
nums[i] = total % (10 ^^ 8);
total += nums[i] - nums[i - k];
}
return nums[n];
}
void main() {
hFib(100, 10_000).writeln();
hFib(3 ^^ 13, 5 ^^ 10).writeln();
}
In C:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
uint64_t hFib(const int k, const int n) {
uint64_t *nums = calloc(k + n + 1, sizeof(uint64_t));
if (nums == NULL)
return 0;
nums[k - 1] = 1;
uint64_t total = 1;
for (int i = k; i < n + 1; i++) {
nums[i] = total % 100000000LLU;
total += nums[i] - nums[i - k];
}
return nums[n];
}
int main() {
printf("%llu\n", hFib(100, 10000));
printf("%llu\n", hFib(1594323, 9765625));
return 0;
}
DMD 32 bit:
L5A: mov EDX,020h[ESP]
mov EAX,01Ch[ESP]
mov EBX,05F5E100h
push ESI
xor ECX,ECX
push EDI
call near ptr __ULDIV@
pop EDI
pop ESI
mov EDX,018h[ESP]
mov EAX,ESI
mov [ESI*8][EDX],EBX
sub EAX,EDI
mov 4[ESI*8][EDX],ECX
sub EBX,[EAX*8][EDX]
sbb ECX,4[EAX*8][EDX]
add 01Ch[ESP],EBX
adc 020h[ESP],ECX
inc ESI
cmp ESI,EBP
jb L5A
GCC 4.7.1:
L6:
movl %esi, (%esp)
movl %edi, 4(%esp)
movl $100000000, 8(%esp)
movl $0, 12(%esp)
call ___umoddi3
movl %eax, (%ebx,%ebp,8)
movl %edx, 4(%ebx,%ebp,8)
subl (%ebx), %eax
sbbl 4(%ebx), %edx
addl %eax, %esi
adcl %edx, %edi
addl $8, %ebx
cmpl 24(%esp), %ebx
jne L6
LLVM:
.LBB0_2: # =>This Inner Loop
Header: Depth=1
movl %esi, 4(%esp)
movl %edi, (%esp)
movl $0, 12(%esp)
movl $100000000, 8(%esp) # imm = 0x5F5E100
calll __umoddi3
movl 24(%esp), %ecx # 4-byte Reload
movl %eax, (%ecx,%ebp,8)
movl %edx, 4(%ecx,%ebp,8)
addl %edi, %eax
adcl %esi, %edx
subl -800(%ecx,%ebp,8), %eax
sbbl -796(%ecx,%ebp,8), %edx
addl $1, %ebp
adcl $0, %ebx
cmpl $10001, %ebp # imm = 0x2711
movl %eax, %edi
movl %edx, %esi
jne .LBB0_2
Run-time, D 0.75 seconds (dmd 2.060alpha 32 bit, -O - release
-inline), C 0.40 seconds (gcc 4.7.1 32 bit, -Ofast -flto -S
-std=c99).
Permutation functions are also an annoying one not to have. =/
Try this:
http://rosettacode.org/wiki/Permutations#Faster_Lazy_Version
Bye,
bearophile
