Sign on result of GCD is unpredictable

[TyOverby]

When numbers are small, the result of a call to gcd is positive when one parameter is zero, and the other parameter is negative.

However, when the negative value is "large", it returns a negative number.

At first glance, it appears that the "normalization" in the small-case happens here:
https://github.com/ocaml/Zarith/blob/master/caml_z.c#L1743

  let gcd_helper a b = gcd (Z.of_string a) (Z.of_string b) |> Z.print

  let%expect_test "" =
    gcd_helper "0" "-350854590609916240021621339209265605473999635689";
    [%expect "-350854590609916240021621339209265605473999635689"]
  ;;

  let%expect_test "" =
    gcd_helper "0" "-55";
    [%expect "55"]
  ;;

[xavierleroy]

I would expect the result of Z.gcd to be nonnegative in all cases, consistently with mpz_gcd (see https://gmplib.org/manual/Number-Theoretic-Functions.html#Number-Theoretic-Functions).

From a quick look at the Zarith code, the only case where a negative result can occur is when one of the arguments is 0, in which case the other argument is returned, while maybe its absolute value should be returned. (To be discussed.)

[antoinemine]

Yes, I think we should follow mpz_gcd and always return a non-negative result. So, gcd(a,0) = gcd(0,a) = abs(a). Thus, the case for large values of a needs fixing.

Also, I now realize that we are only fixing gcd. Maybe gcdext and lcm also need fixing for negative or nul arguments.

[antoinemine]

See PR #59 for a fix for gcd, and also lcm, gcdext.
What do you think?

[antoinemine]

Merged!