[Issue 7102] New: std.numeric.gcd with BigInts too

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=7102

           Summary: std.numeric.gcd with BigInts too
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Keywords: patch
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2011-12-13 01:34:31 PST ---
This is part of std.numeric.gcd (DMD 2.057beta), it doesn't work with BigInts
because they (correctly) don't define a "min" and they (because of bug 4120)
can't be used in a boolean context yet:


        static if (T.min < 0) {
            enforce(a >= 0 && b >=0);
        }
        while (b) {



Unfortunately std.traits.isSigned works with built-in types only, and
std.BigInt is not regarded as a citizen. So I have had to define a
isSignedNumber, maybe there are ways to improve its code. Here you find an
improved gcd() that seems to work with BigInts too:


import std.traits: Unqual, isSigned;
import std.exception: enforce;

template isSignedNumber(T) {
    enum bool isSignedNumber = isSigned!T ||
                               (__traits(compiles, {return T.init - 1 < 0;}) &&
                                (T.init - 1) < 0);
}

/**
Computes the greatest common divisor of $(D a) and $(D b) by using
Euler's algorithm.
 */
T gcd(T)(T a, T b) {
    static if (is(T == const) || is(T == immutable)) {
        return gcd!(Unqual!T)(a, b);
    } else {
        static if (isSignedNumber!T) {
            enforce(a >= 0 && b >=0);
        }
        while (b != 0) { // BUG 4120
            auto t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}

unittest {
    assert(gcd(2 * 5 * 7 * 7, 5 * 7 * 11) == 5 * 7);
    immutable int a = 5 * 13 * 23 * 23,
                  b = 13 * 59;
    assert(gcd(a, b) == 13);
    assert(gcd(BigInt("334158684640375"), BigInt("18505861418625")) ==
           BigInt("150454157875"));
}



See also bug 4125

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------