[Issue 16200] New: Faster pow implementation for integral exponents

[via Digitalmars-d-bugs]

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 at puremagic.com
          Reporter: andrei at 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.

--