CODEWITHSUNDEEP
algorithm
fukawi2
fukawi2

Reputation: 536

Algorithm to determine if A is within X of a multiple of B

This is not language specific, but I'm not very good with maths!

What is the most efficient way to test if A is within X of a multiple of B? The method I'm using at the moment is:

# when (A mod B) < (B/2)
if (A modulus B) < X THEN TRUE
# when (A mod B) > (B/2)
if ABS((A modulus B) - B) < X THEN TRUE

Example 1: A is 100 more than 3 x B

A=30100
B=10000
X=150

(30100 mod 10000) = 100 < (10000/2)
(30100 modulus 10000) = 100

Example 2: A is 100 less than 3 x B

A=29900
B=10000
X=150

(29900 mod 10000) = 9900 > (10000/2)
ABS((29900 modulus 10000) - 10000) = 100

Is there a better way to do this?

(To avoid an XY Problem: I'm writing a script to monitor some industrial machinery, and I want to fire an alert when a lifetime counter metric is within a range of a periodic maintenance value. When the service interval is 10000 and the alert range is 150, I want to know when that counter is between 9850 and 10150, or 19850 and 20150, etc)

Upvotes: 1

Views: 77

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59253

Your way is not bad, but it's a little faster to do:

if ((A + X) % B) <= X*2 then
    TRUE
else
    FALSE

That's for distance <= X. If you need distance < X, then: 

if ((A + X + B - 1) % B) <= X*2-2 then
    TRUE
else
    FALSE

Note that A + X + B - 1 is like A + X - 1, but protected against anything weird your language might do with the modulus operator and negative operands in the case that X == 0.

Upvotes: 2

ruakh
ruakh

Reputation: 183466

I think the best approach is whatever you find clearest; but personally I would write the equivalent of ((A + X) MOD B ≤ 2X). For example, in C / Java / Perl / JavaScript / etc.:

if ((a + x) % b <= 2 * x) {
    // A is within X of a multiple of B
}

Upvotes: 1

Related Questions