www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 7102] New: std.numeric.gcd with BigInts too

reply d-bugmail puremagic.com writes:
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



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: -------
Dec 13 2011
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7102


Don <clugdbug yahoo.com.au> changed:

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



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: -------
Dec 13 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7102


bearophile_hugs eml.cc changed:

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





 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: -------
Dec 13 2011
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7102


bearophile_hugs eml.cc changed:

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



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: -------
Apr 06 2012