## digitalmars.D.learn - Optimizing a bigint fibonacci

• helxi (29/29) Dec 06 2017 This is question not directly related to language concepts, it's
• Jonathan M Davis (35/42) Dec 06 2017 On a complete sidenote, if you want to correctly time stuff, you should ...
• codephantom (2/5) Dec 06 2017 Compile it with ldc ;-)
• codephantom (6/12) Dec 06 2017 also, fyi....in my test, when compiling with dmd and using -m32
• Biotronic (36/42) Dec 06 2017 Here's my version:, based on fast squaring:
• helxi (3/20) Dec 06 2017 Oh I see. We should definitely be careful with that :D
• Biotronic (10/17) Dec 06 2017 Just playing around a bit. The alternative is to assign to a
helxi <brucewayneshit gmail.com> writes:
This is question not directly related to language concepts, it's
got more to do with the application. I would appreciate if anyone
would point to me how I could optimize this bit of code
auto fib(const int n)
{
import std.bigint;

if (n == 0)
return BigInt(0);

if (n == 1)
return BigInt(1);

BigInt next;
for (BigInt i = 0, j = 1, count = 1; count < n; ++count)
{
next = i + j;
i = j;
j = next;
}
return next;
}

void main()
{
import std.stdio, std.datetime;

auto t0 = Clock.currTime;
writeln(fib(100_000));
writeln(Clock.currTime - t0);
}

I also noticed that if I try to compute it in the compile time
with enum x = fib(100000) the compiler freezes. What could cause
this?
Dec 06 2017
Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Wednesday, December 06, 2017 09:12:08 helxi via Digitalmars-d-learn
wrote:
void main()
{
import std.stdio, std.datetime;

auto t0 = Clock.currTime;
writeln(fib(100_000));
writeln(Clock.currTime - t0);
}
On a complete sidenote, if you want to correctly time stuff, you should use a monotonic clock rather than the wall clock, since the wall clock can be shifted by the system, whereas a monotonic clock is guaranteed to always move forward at a fixed rate. So, you'd either want to do something like import std.stdio, std.datetime; auto t0 = MonoTime.currTime; writeln(fib(100_000)); writeln(MonoTime.currTime - t0); or import std.stdio, std.datetime.stopwatch; auto sw = StopWatch(AutoStart.yes); writeln(fib(100_000)); writeln(sw.peek); That way, you don't have to worry about the timing being wrong due to the clock being shifted. Such shifting happens infrequently enough that it won't _usually_ create a problem, but it can create a serious problem if a shift occurs and you're doing something like waiting for the clock to reach a certain point in time. It's just better to get in the habit of using the monotonic clock for timing stuff. Note however that for the time being, if you want to use anything in std.datetime.stopwatch, you'll need to either just import it and not std.datetime or use selective import such as import std.datetime.stopwatch : StopWatch; This is because the old versions of the benchmarking stuff like benchmark and StopWatch are in std.datetime.package and have been deprecated (they use core.time.TickDuration which will soon be deprecated) and replaced with nearly identical versions in std.datetime.stopwatch which use core.time.MonoTime and core.time.Duration. Until the old versions have gone through the full deprecation cycle and have been removed, they'll conflict with the new ones, so std.datetime.stopwatch is not yet publicly imported in std.datetime.package, and if you import both, then selective imports are needed in order to deal with the symbol conflict. - Jonathan M Davis
Dec 06 2017
codephantom <me noyb.com> writes:
On Wednesday, 6 December 2017 at 09:12:08 UTC, helxi wrote:
This is question not directly related to language concepts,
it's got more to do with the application. I would appreciate if
anyone would point to me how I could optimize this bit of code
Compile it with ldc ;-)
Dec 06 2017
codephantom <me noyb.com> writes:
On Wednesday, 6 December 2017 at 09:59:12 UTC, codephantom wrote:
On Wednesday, 6 December 2017 at 09:12:08 UTC, helxi wrote:
This is question not directly related to language concepts,
it's got more to do with the application. I would appreciate
if anyone would point to me how I could optimize this bit of
code
Compile it with ldc ;-)
also, fyi....in my test, when compiling with dmd and using -m32 (instead of -m64) it timed *twice as fast* compared to the timing of the 64bit run; whereas compiling with ldc, both the 32bit and 64bit run timed at about the same speed. lesson? don't 'just' look at how to optimise your 'code' ;-)
Dec 06 2017
Biotronic <simen.kjaras gmail.com> writes:
On Wednesday, 6 December 2017 at 09:12:08 UTC, helxi wrote:
This is question not directly related to language concepts,
it's got more to do with the application. I would appreciate if
anyone would point to me how I could optimize this bit of code
Here's my version:, based on fast squaring: auto fib(ulong n) { import std.bigint : BigInt; import std.meta : AliasSeq; import std.typecons : tuple; BigInt a = 0; BigInt b = 1; auto bit = 63; while (bit > 0) { AliasSeq!(a, b) = tuple( a * (2*b - a), a*a + b*b); if (n & (BigInt(1) << bit)) { AliasSeq!(a, b) = tuple(b, a+b); } --bit; } return a; } unittest { import std.stdio : writeln; import std.datetime : MonoTime; auto t0 = MonoTime.currTime; writeln(fib(10_000_000)); writeln(MonoTime.currTime - t0); } Takes around 600 milliseconds to compute fib(1_000_000), and 50 seconds for fib(10_000_000). Fast squaring algorithm found and described here: https://www.nayuki.io/page/fast-fibonacci-algorithms
I also noticed that if I try to compute it in the compile time
with enum x = fib(100000) the compiler freezes. What could
cause this?
That's because the poor compiler isn't as good at optimizing compile-time code as run-time code, and because fib(100000) is frigging ginormous. -- Biotronic
Dec 06 2017
helxi <brucewayneshit gmail.com> writes:
On Wednesday, 6 December 2017 at 10:00:48 UTC, Biotronic wrote:
On Wednesday, 6 December 2017 at 09:12:08 UTC, helxi wrote:
[...]
Here's my version:, based on fast squaring: auto fib(ulong n) { import std.bigint : BigInt; import std.meta : AliasSeq; import std.typecons : tuple; BigInt a = 0; BigInt b = 1; auto bit = 63; while (bit > 0) { AliasSeq!(a, b) = tuple( a * (2*b - a), a*a + b*b); [...]
Nice. But why the AliasSeq?
That's because the poor compiler isn't as good at optimizing
compile-time code as run-time code,
Oh I see. We should definitely be careful with that :D
Dec 06 2017
Biotronic <simen.kjaras gmail.com> writes:
On Wednesday, 6 December 2017 at 10:16:16 UTC, helxi wrote:
On Wednesday, 6 December 2017 at 10:00:48 UTC, Biotronic wrote:
AliasSeq!(a, b) = tuple(
a * (2*b - a),
a*a + b*b);

[...]
Nice. But why the AliasSeq?
Just playing around a bit. The alternative is to assign to a temporary: auto c = a * (2*b - a); b = a*a + b*b;' a = c; The resulting behavior is the same, and apart from the cludgy names I kinda like doing (a,b) = (c,d). -- Biotronic
Dec 06 2017