Generic **gcd**

[damianmoz]

As somebody who likes 32-bit integers and occasionally dabbles in 16-bit integers, can I suggest the more generic and slightly tighter gcd(a,b) as a replacement within Math.chpl.

proc gcd(in a : int(?w), in b : int(w))
{
    (a, b) = (abs(a), abs(b));

    while b != 0 do
    {
        (a, b) = (b, a % b);
    }
    return a;
}

It is neither faster nor slower for int(64).

[damianmoz]

Loop unrolling as in

proc gcd(in a : int(?w), in b : int(w))
{
    (a, b) = (abs(a), abs(b));

    while b != 0 do
    {
        (a, b) = (b, a % b);
        if b == 0 then break;
        (a, b) = (b, a % b);
    }
    return a;
}

makes a marginal (maybe 2%) difference at the expense of clarity.

[lydia-duncan]

That seems reasonable to me. It'll probably get in faster if you open a PR to do it, but I'll make sure it gets tracked as "things to do before Math/AutoMath get stabilized" if you don't feel you have the cycles for it

[bradcray]

It is surprising that we don't support gcd for arbitrary integer widths... Now I'm wondering what other math routines have this issue. We also might want to support it for uints?

[damianmoz]

I have never done a PR - what is a PR? And I am a bit short of cycles right now.

Also, very quickly, I believe

proc gcd(in a : uint(?w), in b : uint(w))
{
    while b != 0 do
    {
        (a, b) = (b, a % b);
    }
    return a;
}
inline proc gcd(in a : int(?w), in b : int(w))
{
    return gcd(abs(a):uint(w), abs(b):uint(w)):int(w);
}

[lydia-duncan]

PR is short for Pull Request :)

[bradcray]

A Pull Request is how changes to the Chapel repository (code, documentation, anything stored within https://github.com/chapel-lang/chapel) are made. Like many things, they are not difficult, though doing one for the first time can take time and care. Then it becomes second nature and can be about only slightly slower to create than opening an issue. Detailed instructions are available here: https://chapel-lang.org/docs/developer/bestPractices/ContributorInfo.html#development

[damianmoz]

Silly me. Sorry. Brain must have switched off after 2am. I will look at it later today if I get time.