wood burning stoves 2.0*
The moose likes Programming Diversions and the fly likes Algorithm help: minimum distance to multiple Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Algorithm help: minimum distance to multiple" Watch "Algorithm help: minimum distance to multiple" New topic
Author

Algorithm help: minimum distance to multiple

Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
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?


Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

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

Joined: Feb 18, 2005
Posts: 1006
    
    3
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

Joined: Feb 18, 2005
Posts: 1006
    
    3
...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

Joined: Jul 27, 2013
Posts: 30
result = (b^2 - a)

result = result % b

clean ? :-)
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1006
    
    3
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

Joined: Jul 27, 2013
Posts: 30
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

Joined: Mar 17, 2011
Posts: 7552
    
  18

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

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Algorithm help: minimum distance to multiple
 
Similar Threads
Self Test Question on Arrays by Kathy's Book
Can you tell me how to answer such question?
please have a look
Once more about Array
Connection Array into an adjacency Matrix