www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4125] New: std.numeric.gcd can use a binary GCD

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4125

           Summary: std.numeric.gcd can use a binary GCD
           Product: D
           Version: future
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc



std.numeric.gcd can use a faster Binary GCD algorithm, especially when the
input type is unsigned. This page has both C code (and asm, but the C code is
probably enough in many situations):

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 24 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4125


Andrei Alexandrescu <andrei metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |andrei metalanguage.com
         AssignedTo|nobody puremagic.com        |andrei metalanguage.com


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 09 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4125


Marco Leise <Marco.Leise gmx.de> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |Marco.Leise gmx.de



Replace uint with ulong for the longer version ;)
I use this and it is notably faster than what I used before.

uint gcd(uint u, uint v)
{
    int shift;
    if (u == 0 || v == 0) return u | v;
    for (shift = 0; ((u | v) & 1) == 0; ++shift) {
        u >>= 1;
        v >>= 1;
    }
    while ((u & 1) == 0) u >>= 1;
    do {
        while ((v & 1) == 0) v >>= 1;
        if (u < v) {
            v -= u;
        } else {
            uint diff = u - v;
            u = v;
            v = diff;
        }
        v >>= 1;
    } while (v != 0);
    return u << shift;
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 31 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4125


Peter Alexander <peter.alexander.au gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |peter.alexander.au gmail.co
                   |                            |m



11:15:04 PST ---


 Replace uint with ulong for the longer version ;)
 I use this and it is notably faster than what I used before.


I implemented this (exactly as you have it) and it was slower than the
algorithm that is already there. I tested on all pairs of integers below
10,000, and also on the pairs (x^2, y) for all x,y < 10,000. At best it was 50%
slower, at worst 3x slower.

All tests used dmd -O -release -inline

I suspect the reason for the performance reduction is due to poor pipelining.
The binary version involves a lot more branching, and more loop iterations than
the standard algorithm. Also, the branches taken are highly unpredictable.

Maybe I'll look at this again in the future to try and make it faster, but it's
pretty low on my priority list.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 05 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4125







 I implemented this (exactly as you have it) and it was slower than the
 algorithm that is already there. I tested on all pairs of integers below
 10,000, and also on the pairs (x^2, y) for all x,y < 10,000. At best it was 50%
 slower, at worst 3x slower.
 ...
 Maybe I'll look at this again in the future to try and make it faster, but it's
 pretty low on my priority list.


Thank you for doing some experiments. Once the experiments are conclusive, this
enhancement can be closed.

(Then at the moment a more important function for Phobos is an efficient GCD
for bigints.)

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 06 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4125




FWIW, you can get rid of most of the conditional branches by using:

min(u,v) = v + ( (cast(int)(u-v)) >> (8*int.sizeof - 1)) & (u-v)

the shift smears the sign bit of u-v so that it makes a mask either 0x0000_0000
or 0xFFFF_FFFF.

I think the general consensus is that (at least if you use asm), binary GCD is
faster on all known processors, but not necessarily by a large amount.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 08 2013
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4125


Artem Tarasov <lomereiter gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |lomereiter gmail.com



PST ---


 std.numeric.gcd can use a faster Binary GCD algorithm, especially when the
 input type is unsigned. This page has both C code (and asm, but the C code is
 probably enough in many situations):
 
 http://en.wikipedia.org/wiki/Binary_GCD_algorithm


Maybe instead of reinventing the wheel LibTomMath library should be used? It is
in public domain, has decent performance, and is stable enough to provide
implementation of big integers in TCL and Rubinius.

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