Archive for July, 2008

A summation trick

Here is a trick to calculate the summation related to floor function Sum{ floor((a+d*i)/m) | 0<=i<n}.
Let’s count in another way. Let g(k) be the number of i such that floor((a+d*i)/m)>=k,
then the summation would be Sum{ g(k) | 1<=k}. The second summation would be in the form
of Sum{floor( (a’+m*k)/d )+ constants | 1<=k}, so we can let m=m%d and the denominator decrease.
We can recursively apply the above transformation until the coefficient of variable i becomes 0.
The whole recursive procedure is just like that of Euclid’s algorithm for greatest common divisor,
so the time complexity is logarithmic.

Read Full Post »

A bitwise trick

Low(x): ((x^(x-1))&x) is well-known.
How about calculate sum[i]= Sum{ A[j] |  j is a  subset  of  i}?
The common tricks don’t work.
One trick is to calculate partSum[i][b]= partSum[i][b+1] + ((1<<b)&i)?partSum[i^(1<<b)][b+1]:0.
Here partSum[i][b] denotes sum of A[k] such that the b low bits of k  and i are the same, and the high bits from bit b of k is a subset of that of i.
The time complexity is n2^n. Is there faster method?

Read Full Post »