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