digitalmars.D.bugs - [Issue 16200] New: Faster pow implementation for integral exponents
- via Digitalmars-d-bugs (72/72) Jun 24 2016 https://issues.dlang.org/show_bug.cgi?id=16200
https://issues.dlang.org/show_bug.cgi?id=16200 Issue ID: 16200 Summary: Faster pow implementation for integral exponents Product: D Version: D2 Hardware: x86_64 OS: Linux Status: NEW Severity: enhancement Priority: P1 Component: dmd Assignee: nobody puremagic.com Reporter: andrei erdani.com Stepanov discusses in http://www.stepanovpapers.com/PAM.pdf how the usual pow implementation does more computing than strictly necessary and proposes a better version. That has duplicated code, which can also be eliminated as follows: double newPow(double b, uint e) { if (e <= 1) { if (e == 1) return b; return 1; } double r = b; --e; // Loop invariant: r * (b ^^ e) is the actual result for (;; e /= 2) { if (e % 2) { r *= b; if (e == 1) break; } b *= b; } return r; } void main(string[] args) { import std.datetime: benchmark, Duration; import std.stdio: writeln, writefln; import std.conv: to; auto a = 5.0; auto b = 25; auto l = 0.0; void f0() { l += newPow(a, b); } void f1() { import std.math; l += std.math.pow(a, b); } void f2() { l += a ^^ b; } auto rs = benchmark!(f0, f1, f2)(100_000_000); foreach(j,r;rs) { version (GNU) writefln("%d %d secs %d ms", j, r.seconds(), r.msecs()); else writeln(j, " ", r.to!Duration); } // prevent any optimization writeln(l); } When built with dmd -O -inline -release gd/powtest.d&& ./powtest the code above prints: 0 986 ms, 913 μs, and 4 hnsecs 1 2 secs, 321 ms, 606 μs, and 6 hnsecs 2 4 secs, 957 ms, 933 μs, and 5 hnsecs 8.9407e+25 i.e. a large improvement in performance. Therefore the code above should be included in the built-in ^^ operator and pow implementation. See more discussion, including gdc/ldc, at http://forum.dlang.org/thread/nkh5tf$1ch1$1 digitalmars.com. --
Jun 24 2016