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@puremagic.com
        ReportedBy: bearophile_hugs@eml.cc


--- Comment #0 from bearophile_hugs@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: -------

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


Don <clugdbug@yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |clugdbug@yahoo.com.au


--- Comment #1 from Don <clugdbug@yahoo.com.au> 2011-12-13 08:34:07 PST ---
There are a few interesting issues here:

Firstly, GCD for bigints is an important primitive operation, but it's very complicated (the sub-quadratic algorithms are highly non-trivial). It's completely different to algorithms used for built-in types (where the cost of arithmetic is independent of the magnitude of the integer). So it can't sensibly be made generic.

Secondly, Euclid's algorithm is always inferior to the binary GCD algorithm, whenever the latter applies. The generic version should be using binary GCD.

Finally, it's Euclid's algorithm, not Eulers!

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

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


bearophile_hugs@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |INVALID


--- Comment #2 from bearophile_hugs@eml.cc 2011-12-13 10:02:29 PST ---
(In reply to comment #1)
> There are a few interesting issues here:
> 
> Firstly, GCD for bigints is an important primitive operation, but it's very complicated (the sub-quadratic algorithms are highly non-trivial). It's completely different to algorithms used for built-in types (where the cost of arithmetic is independent of the magnitude of the integer). So it can't sensibly be made generic.
> 
> Secondly, Euclid's algorithm is always inferior to the binary GCD algorithm, whenever the latter applies. The generic version should be using binary GCD.
> 
> Finally, it's Euclid's algorithm, not Eulers!

So this code is useless... Thank you for your comments, Don.

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

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


bearophile_hugs@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|INVALID                     |


--- Comment #3 from bearophile_hugs@eml.cc 2012-04-06 05:11:00 PDT ---
Instead of opening a new enhancement request, I reopen this one, because the request is essentially the same.

I suggest to add this bignum specialization to std.numeric.gcd (or add a GCD in std.bigint, but I'd like to have a single function for both bigints and built-in ints).

Even if this isn't the fastest multi-precision GCD algorithm of the world, it seems better than not being able to compute GCD on bigints, and it looks short, both the Python prototype and the C patch are not long.

http://en.wikipedia.org/wiki/Lehmer%27s_GCD_algorithm

http://bugs.python.org/issue1682

http://bugs.python.org/file9464/lehmer_gcd.py

http://bugs.python.org/file9486/lehmer_gcd.patch


See also Issue 4125

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