FOn 01 Jan 2017, at 23:18, Niels Möller <[email protected]> wrote: > > > Max Horn <[email protected]> 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 _______________________________________________ gmp-bugs mailing list [email protected] https://gmplib.org/mailman/listinfo/gmp-bugs
