Algorithm help: minimum distance to multiple

[Garrett Rowe]

I'm not sure if this belongs in this forum, but it is more an algorithm question than a programming, or language specific question.

Given a function that takes 2 integer parameters, f(a, b), it should return a number representing how much you have to add to a to make it a multiple of b.

So:

f(1, 2) = 1
f(2, 2) = 0
f(1, 3) = 2
f(4, 3) = 2
f(5, 3) = 1
f(6, 3) = 0

What I have seems correct, but overly complicated:

f(a, b) = (b - (a % b)) % b

Is there a better cleaner way?

[Paul Clapham]

Some quick scribbling suggests to me that

b - (a % b)

works just as well. Am I right?

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.

[Ryan McGuire]

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.

How about...

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.

[Ryan McGuire]

...or just use Paul's formula with an if() for the special case:

answer = b - (a % b);
if (answer == b)
    answer = 0;

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.

[vishal saha]

result = (b^2 - a)

result = result % b

clean ? :-)

[Ryan McGuire]

vishal saha wrote:result = (b^2 - a)

result = result % b

clean ? :-)

This assumes that b^2 > a.

For f(14, 3), b^2 - a in this case would be -5. In Java, -5 % 3 = -2. If I understand the requirements correctly, the answer should be 1.

[vishal saha]

Ryan McGuire wrote:
This assumes that b^2 > a.

great catch .

if a >= b ^2 then a = a % b then do rest .. . please post further if you find any other hole ....

edit:

i.e, pre condition -> if a = 0 then result = b

f(a, b) then convert f(a % b , b) first .

[Winston Gutkowski]

Ryan McGuire wrote:...or just use Paul's formula with an if() for the special case...

With two variables you could save yourself a subtraction, viz:

int mod = a % b;
int answer = mod == 0 ? 0 : b - mod;

I suspect also that comparison with 0 is quicker, but it might all be offset by having an extra variable.

Ain't optimization fun?

Winston