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(3): Jump Start-typo? by goFish)

"there is a "+1" missing and the rhs should read floor(Ka) (floor(Kb)+1). "  YES. Correction made in my post. Sorry for losing the 1.

The observations of the first two posts are important here: integers contained in the argument of a floor (or ceiling) function can be pulled out. Doing this in each step (including the 0th step if a>b) provides the simplification that makes the algorithm effective. You need to keep using the formula over and over with the same K but with a or b getting smaller each time.  There is a very well-known (and ancient) algorithm embedded in this!

Edited on February 19, 2006, 2:53 pm

Posted by Richard on 2005-12-30 13:06:47