Let a, b, and m be positive whole numbers. Required is a fast algorithm for evaluating Σ_k=0..m floor(ka/b), floor(x) being the greatest integer that does not exceed the real number x.

Same basic idea as eg.

write a= xb + r (0 <= r <b )

Then rewrite as a/b = x + r/b = x + y/z where y/z is r/b reduced so that y and z are co-prime (no common divisors other than 1).

(Edit: x,y and z are of course non-negative integers, z>0)

Now summing k = 0...m.

sum(ka/b)=sum(xk) + sum (ky/z)

= x sum(k) + y sum(k/z)

Using notation [x] = floor(x)...

sum( [ ka/b] ) = (x/2) (m)(m+1) + y sum( [k/z] ) since now it only matters if z divides k.  I think this is summable and will try later but have no objection is someone finds it first.

Edited on November 23, 2005, 6:16 pm

Posted by goFish on 2005-11-23 18:11:09