fast determination of sign of sum

[keith.briggs at bt.com]

Thanks to Torbjörn for the very useful reply.   This is turning out quite an interesting problem and I now wonder if there has been any theoretical work on the complexity (in terms of number of additions) of determining the sign of the sum of n numbers.  The python codes below express my algorithms for 2 and 4 numbers.   While the function for 2 numbers uses no additions, the functions for 4 numbers uses on average about 0.4 additions per call, for iid inputs uniformly distributed on an interval symmetric about zero.   Can this be improved?  What about for an arbitrary number of summands?
Keith

def sign_sum2(z0,z1):
  s0=cmp(z0,0) # python built-in: -1 if z0<0; 0 if z0=0; 1 else.
  s1=cmp(z1,0)
  if s1==0: return s0
  if s0==0: return s1
  if s0>0:
    if s1>0: return 1  # z0>0, z1>0
    return cmp(z0,-z1) # z0>0, z1<0
  else: # z0<0
    if s1<0: return -1 # z0<0, z1<0
    return cmp(z1,-z0) # z0<0, z1>0

def sign_sum4(z):
  x=z[:] # copy
  x.sort()
  if x[0]==x[3]: return cmp(x[0],0) # all equal
  # now at least one is non-zero
  s=[cmp(q,0) for q in x]
  if s[0]>0: return  1 # all +ve
  if s[3]<0: return -1 # all -ve
  if s[0]==0 and (s[1]>0 or s[2]>0): return 1
  if s[0]<0<=s[1]: # exactly one -ve
    a0=-x[0]
    if x[3]>a0 or x[2]>a0 or x[1]>a0: return 1
    s=x[2]+x[3]
    if s>a0: return 1
    s+=x[1]
    if s>a0: return 1
    return cmp(s,a0)
  if s[1]<0<s[2]: # exactly two -ve - try not to add
    if x[3]>-x[0] and x[2]>-x[1]: return  1
    if x[3]<-x[0] and x[2]<-x[1]: return -1
    if x[2]>-x[0] and x[3]>-x[1]: return  1
    if x[2]<-x[0] and x[3]<-x[1]: return -1
    return cmp(x[2]+x[3],-(x[0]+x[1]))
  # exactly three -ve
  x[0],x[1],x[2]=-x[0],-x[1],-x[2]
  if x[0]>x[3] or x[1]>x[3] or x[2]>x[3]: return -1
  s=x[0]+x[1]
  if s>x[3]: return -1
  s+=x[2]
  if s>x[3]: return -1
  return cmp(x[3],s)
 
-----Original Message-----
From: tg at swox.com [mailto:tg at swox.com] 
Sent: 21 January 2009 10:47
To: Briggs,KM,Keith,CXR2 R
Cc: gmp-discuss at swox.com
Subject: Re: fast determination of sign of sum

<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