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.

(In reply to re(2): Jump Start by Richard)

Richard

You wrote

"I claim that it is always the case that for general a,b, and K

Sum_{0<=k<=Kb} floor(ka/b) + Sum_{0<=l<=Ka} ceiling(lb/a) = floor(Ka)floor(Kb)"

Let a = 5, b = 17, m = 23, K = 23/17, then this becomes

70 + 74 = 144 but 6 * 23 = 138 so I suspect there is a "+1" missing and the rhs should read floor(Ka) (floor(Kb)+1).

If I do this and rewrite in terms of the given iterator,k, and parameters a, b and m, I obtain

s( a, b, m) = (m+1) Floor [ a m / b] - Sum (for k = 0 to a m / b) Ceiling [ k b / a]

(for a given (a, b,m) K is not totally independent and I have used K = m/b).

I have tested this and found no errors.  However this formulation is not very efficient since, for example, if a>b then the length of the residual series is actually greater than the original.

Posted by goFish on 2005-12-30 06:50:07