mpn negation with borrow in
vincent at vinc17.org
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
Vincent Lefèvre <vincent at vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
More information about the gmp-discuss