Paul Clapham wrote:
Edit: If a is already a multiple of b then my formula returns b and your formula returns 0. You might think yours is "righter" than mine in that case but both satisfy the stated requirements.
I would call Garrett's solution "righter" because you "have to" add 0 to 6 to make it a multiple of 3, but you don't "have to" add 3. I interpreted the original problem statement to say we're looking for the minimum non-negative integer that satisfies the condition.
b - 1 - ((a -1 ) % b)
That formula replaces the second MOD operation from Garrett's version with an extra +1 and -1. However, it has a minor fail when a=0, in which case a-1 == -1 and -1 % b == -1. We could modify it a bit so that the left side of the % doesn't go negative for non-negative values of a:
(b-1) - ((a + (b-1)) % b)
That looks like a total of four addition and subtractions. However, you could cache the value for b-1:
c = b-1
answer = c - ((a + c) % b)
So... three addition/subtractions and one MOD.
Joined: Feb 18, 2005
...or just use Paul's formula with an if() for the special case:
One MOD, one subtraction, one comparison and one extra assignment one time out of b on average. The comparison and possibly extra assignment are probably cheaper computationally than a second MOD.