Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Algorithm help: minimum distance to multiple

 
Garrett Rowe
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 20951
31
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 1057
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 1057
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
...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.
 
vishal saha
Ranch Hand
Posts: 30
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
result = (b^2 - a)

result = result % b

clean ? :-)
 
Ryan McGuire
Ranch Hand
Posts: 1057
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 30
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Pie
Posts: 10226
58
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic