fast determination of sign of sum
keith.briggs at bt.com
keith.briggs at bt.com
Fri Jan 23 11:52:18 CET 2009
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
More information about the gmp-discuss
mailing list