45 lines
1.1 KiB
D
45 lines
1.1 KiB
D
import std.bigint, std.math;
|
|
|
|
// Algorithm from: Takahashi, Daisuke,
|
|
// "A fast algorithm for computing large Fibonacci numbers".
|
|
// Information Processing Letters 75.6 (30 November 2000): 243-246.
|
|
// Implementation from:
|
|
// pythonista.wordpress.com/2008/07/03/pure-python-fibonacci-numbers
|
|
BigInt fibonacci(in ulong n)
|
|
in {
|
|
assert(n > 0, "fibonacci(n): n must be > 0.");
|
|
} body {
|
|
if (n <= 2)
|
|
return 1.BigInt;
|
|
BigInt F = 1;
|
|
BigInt L = 1;
|
|
int sign = -1;
|
|
immutable uint n2 = cast(uint)n.log2.floor;
|
|
auto mask = 2.BigInt ^^ (n2 - 1);
|
|
foreach (immutable i; 1 .. n2) {
|
|
auto temp = F ^^ 2;
|
|
F = (F + L) / 2;
|
|
F = 2 * F ^^ 2 - 3 * temp - 2 * sign;
|
|
L = 5 * temp + 2 * sign;
|
|
sign = 1;
|
|
if (n & mask) {
|
|
temp = F;
|
|
F = (F + L) / 2;
|
|
L = F + 2 * temp;
|
|
sign = -1;
|
|
}
|
|
mask /= 2;
|
|
}
|
|
if ((n & mask) == 0) {
|
|
F *= L;
|
|
} else {
|
|
F = (F + L) / 2;
|
|
F = F * L - sign;
|
|
}
|
|
return F;
|
|
}
|
|
|
|
void main() {
|
|
10_000_000.fibonacci;
|
|
}
|