mpn negation with borrow in

Vincent Lefevre vincent at
Fri Aug 22 13:41:35 UTC 2014

I was quite surprised to see that the mpn layer doesn't have a
negation with borrow in, while this is very similar to the usual
negation: indeed, in the negation algorithm, a borrow can (and
generally will) be generated at some point. Such an operation is
also natural when regarding a negation of a number of size M+N
as two negations of numbers of respective size M and N.

Doing the raw negation and taking the borrow into account separately
could yield two full passes in the worst case. However I think of
using the following method:
  * if the borrow is 0, use mpn_neg;
  * if the borrow is 1, use mpn_com.

Is this the recommended way?

I suppose that the overall speed-up improvement wouldn't be noticeable
in general due to the other operations in the program, but if there is
a simple way to do it efficiently like above, there are no reasons not
to choose it.

Note: concerning the addition with carry, it is just a particular case
of mpn_add_1.

Vincent Lefèvre <vincent at> - Web: <>
100% accessible validated (X)HTML - Blog: <>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)

More information about the gmp-discuss mailing list