Typo in the manual, and clarification for mpn_gcd

[Max Horn]

FOn 01 Jan 2017, at 23:18, Niels Möller <nisse at lysator.liu.se> wrote:
> 
> 
> Max Horn <max at quendi.de> writes:
> 
>> mpn/generic/gcd.c:1:/* mpn/gcd.c: mpn_gcd for gcd of two odd integers.
>> mpn/generic/gcd.c:283:  /* Due to the calling convention for mpn_gcd, at most one can be
>> 
>> However, the documentation for mpn_gcd does not actually state this
>> requirement, see
>> <https://gmplib.org/manual/Low_002dlevel-Functions.html#index-mpn_005fgcd>.
>> 
>> It would be very nice if this could be clarified in the documentation.
> 
> I agree this is appear a bit confused. The gcd implementation on GMP
> used to be a variant of bianry gcd, requiring odd inputs. In the current
> implementation, most of the code doesn't depend on operands being odd,
> but gcd_2 (and the logic where it is called) seems to still do.

Aha, that probably explains what I experienced: Not removing powers of the
arguments actually works "most of the time", but I encountered instances
where the final gcd was off from the correct result by a factor 2^b.

> 
> Not sure if we should update the code or the documentation.

Of course this is your choice, but if I may state my thoughts on this: I
think it would be great if you could update the documentation regardless of
what you do -- even if you change the code, then the docs could still say
"note that in GMP version X to Y, ...." as that would help people who like
me need to write code which is compatible with all GMP 6.x versions (so I
couldn't really take advantage of the code improvements anyway).


> 
>> (2) I tried using mpn_gcd in some code (sadly, in that code I can only
>> use the mpn_ functions, as memory allocations are a no-go)
> 
> Note that many mpn_ functions, including mpn_gcd, do allocate memory.
> But for small operands, they usually allocate needed storage on the
> stack.

Thanks for pointing this out! I just came to the same conclusion, while
poking through mpn_gcd's code. I am surprised this worked, as I was told our
garbage collector would interact badly with any malloc/free operations
performed by GMP. I'll have to get to the bottom to it, but it would be
great news, as I could then start using mpz_* functions (I'd still have to
immediately copy and then free any data allocated by GMP, but if that allows
me to take advantage of, say, mpz_bin_ui, it'd still be a great win over the
existing naive binomial implementation.


Cheers,
Max