Re: Greatest Common Divisor

On 04/01/2020 10:34, Fabien COELHO wrote:
> Code comments: gcd(n, 0) = abs(n), not n?


OK, changed.


> Add unlikely() where appropriate.


Any particular place in mind where I didn't already put it?


> I'd deal with int_min and 0 at the beginning and then proceed with
> absoluting the values, rather than the dance around a1/arg1, a2/arg2,
> and other arg2 = -arg2, and arg1 = -arg1 anyway in various places,
> which does not make the code that easy to understand.
>
> Pseudo code could be:
>
>    if ((a1 == min && (a2 == min || a2 == 0)) ||
>        (a2 == min && a1 == 0))
>      error;
>    a1 = abs(a1), a2 = abs(a2);
>    euclids;
>    return;


This would cause one of my tests to fail.  Please stop suggesting it.


> Note: in the numeric code you abs the value, ISTM consistent to do it
> as well in the other implementations.


As noted in the comments, numeric does not have the INT_MIN problem.


> Would it make sense that NAN is returned on NUMERIC when the
> computation cannot be performed, eg on non integer values?


I don't think so, no.


> Why the positive constraint on LCM(NUMERIC, NUMERIC)? Why not absoluting? 


I didn't see a definition for negative inputs, but now I see one so I've
lifted the restriction.


On 04/01/2020 10:37, Dean Rasheed wrote:
>
> BTW, there is actually no need to restrict the inputs to integral
> values because GCD is something that has a perfectly natural extension
> to floating point inputs (see for example [1]). Moreover, since we
> already have a mod(numeric, numeric) that works for arbitrary inputs,
> Euclid's algorithm just works.
> [...]
> If it were more work to support non-integer inputs, I'd say that it's
> not worth the effort, but since it's actually less work to just allow
> it, then why not?


Okay, I allow that now, but I've still left it for lcm.  I can't find
anything anywhere that defines lcm for floating point (I do find it for
fractions) and the result of abs(a*b)/gcd(a,b) certainly doesn't match
"lowest" in the examples I tried.


On 04/01/2020 18:01, Tom Lane wrote:
> Dean Rasheed <dean.a.rasheed@gmail.com> writes:
>> OTOH, for numeric inputs, this could easily end up needing many
>> thousands of divisions and it's not hard to construct inputs that take
>> minutes to compute, although this is admittedly with ridiculously
>> large inputs (~10^130000), and AFAICS, the performance is OK with
>> "normal" sized inputs. Should we put a limit on the size of the
>> inputs?
> No, but a CHECK_FOR_INTERRUPTS in the loop would be well-advised,
> if there's not one already inside the called functions.


Good idea.  Added.

-- 

Vik Fearing