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


--- Comment #0 from bearophile_hugs@eml.cc 2010-04-24 16:57:35 PDT ---
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: -------

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: -------

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


--- Comment #1 from Marco Leise <Marco.Leise@gmx.de> 2012-01-31 12:11:35 PST ---
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: -------

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


--- Comment #2 from Peter Alexander <peter.alexander.au@gmail.com> 2013-01-05 11:15:04 PST ---
(In reply to comment #1)
> 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: -------

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



--- Comment #3 from bearophile_hugs@eml.cc 2013-01-06 03:44:33 PST ---
(In reply to comment #2)

> 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: -------

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



--- Comment #4 from Don <clugdbug@yahoo.com.au> 2013-01-08 02:37:41 PST ---
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: -------

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


Artem Tarasov <lomereiter@gmail.com> changed:

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


--- Comment #5 from Artem Tarasov <lomereiter@gmail.com> 2013-01-08 06:42:51 PST ---
(In reply to comment #0)
> 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: -------