fast determination of sign of sum
Torbjorn Granlund
tg at swox.com
Wed Jan 21 11:46:33 CET 2009
<keith.briggs at bt.com> writes:
I would be grateful for suggestions on these questions:
1. Given two large mpz_t (say, of order 2^1000000), what is the best way
to determine the sign of their sum? Is it better just to add them, or to
do several comparisons and sign tests?
2. If it is better not to add them, is it still better to use the
comparison and sign test method recursively to determine the sign of the
sum of more than two integers? (In my actual application, there are
four.)
Adding an m-bit and an n-bit integer is a O(max(m,n)) operation in the
worst case (or O(min(m,n)) on average, also assuming the result is to be
stored in the largest of the two operands).
A comparison is O(min(m,n)) in the worst case, and just O(1) for random
data.
For your large operands, you have millions of cycles to save by not
performing the additions.
--
Torbjörn
More information about the gmp-discuss
mailing list