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.

If a>b, we can write a=bn+c, and then we are summing terms like k.(bn+c)/b= kn+kc/b.

The first term is an integer, so we can take it out of the floor function, and we sum kn for k=0 to m, which equals km(m+1)/2.

The second term is the tougher part, but now we can solve it for c<b... or cannot we?

Posted by e.g. on 2005-11-23 13:14:53