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.

With more than a little help from some hints, I've found that this problem analogizes excellently to triangles on a grid of lattice points. (lattice points are points with integer coordinates)

Before I go into details about the analogy, I'll say that there is a theorem that can be used to calculate the area of any polygon with vertices on lattice points.  If I recall correctly, the area is equal to 0.5 * (the number of lattice points on the sides of the polygon) + (the number of lattice points inside the polygon) - 1.  I'm fairly sure I couldn't prove this theorem if I tried, at least not very quickly, so I will take it as a given.  Now, if I could only remember the name of the theorem.

The algorithm's output is related to the number of lattice points inside a particular triangle.  The boundaries of this triangle (on a plane with a x- and k- axis):
x > 0
k <= m
k >= bx/a

Where are these boundary inequalities coming from?  The number of points in each "row" of lattice points is equal to floor(ka/b).  Therefore, the sum of all the points within the boundaries is the output we're looking for.

It must be noted that one of the vertices of this triangle, (ma/b,m) is not necessarily a lattice point. 


Uh oh, this is taking a little longer than I expected.  I'll have to come back to this solution, perhaps after Christmas.

Posted by Tristan on 2005-12-24 02:11:24