On 6/23/2016 10:22 AM, Andrei Alexandrescu wrote:
https://dpaste.dzfl.pl/e53acb41885a
Paste bin links are ephemeral. The code from the link: /** */ int pow(int lhs, uint rhs, ref bool overflow) { return powImpl(lhs, rhs, overflow); } /// ditto long pow(long lhs, uint rhs, ref bool overflow) { return powImpl(lhs, rhs, overflow); } /// ditto uint pow(uint lhs, uint rhs, ref bool overflow) { return powImpl(lhs, rhs, overflow); } /// ditto ulong pow(ulong lhs, uint rhs, ref bool overflow) { return powImpl(lhs, rhs, overflow); } // Inspiration: http://www.stepanovpapers.com/PAM.pdf private T powImpl(T)(T b, uint e, ref bool overflow) { import core.checkedint : muls, mulu; import std.traits : isUnsigned; static if (isUnsigned!T) alias mul = mulu; else alias mul = muls; if (e <= 1) { if (e == 1) return b; if (b == 0) overflow = true; return 1; } T r = b; assert(e > 1); --e; // Loop invariant: r * (b ^^ e) is the actual result outer: for (;;) { if (e % 2 != 0) goto geeba; for (;;) { b = mul(b, b, overflow); e /= 2; continue outer; geeba: r = mul(r, b, overflow); if (e == 1) return r; } } assert(0); } unittest { import std.stdio; bool overflow; foreach (uint i; 0 .. 21) { assert(pow(3u, i, overflow) == 3u ^^ i); assert(!overflow); } assert(pow(3u, 21u, overflow) == 3u ^^ 21); assert(overflow); } void main(){}