how to get a number A which is divisible by a specific number B?

Hello,

Suppose that I have two numbers, A and B. A is supposed to be divisable by B ( residual is zero) but it is not ! Thus, I increment it using a loop until I got the first divisable number by B after the main A. For example, A=10 and B=3 and the first divisable number after A is 12 so A supposed to be 12. But the following code doesnt give me this result. So can anyone help me to edit it !

A= 10;
B= 3;
r= rem(A,B);
while  r~=0
    A= A+1;
    N= A/B;
    r= rem(N,3);
end
 N= A/B;

Answer 1

[John D'Errico]

As an alternative to the one proposed by Madhan Ravi (which is the correct way to modify the proposed code to actually solve the problem), but can we solve the problem without recourse to a loop?

You wish to solve for the unknown variable X, such that

mod(A + X,B) == 0

where X is the smallest possible positive integer offset to A. For example, for A=10, B = 3, X would then be 2, as the increment (X) to add to A to make A+X divisible by B. Since we know that X must be the smallest possible value such that the above modular equation holds, just expand the expression as:

mod(A,B) + mod(X,B) == 0

That is, the distributive law applies to modular expressions (as I expanded it). If X is the smallest value such that the above holds, then it must be true that both

0 <= X

AND

X < B.

In that case, we have that mod(X,B) = X. So our problem reduces to:

mod(A,B) + X == 0

This allows us to trivially solve for X. We also know that mod(A,B) lies in the interval [0,B). Thus if mod(A,B)==0, then X=0. Otherwise, X=B-mod(A,B).

We can write this simply in one line as:

X = mod(-mod(A,B),B);

See that it resolves the case where X==0 neatly. No loops are required. Merely some simple analysis as I did to convince yourself it is valid. Try it out:

A = 10;
B = 3;
X = mod(-mod(A,B),B)
X =
     2

And we then see that A+X=12, which is clearly divisible by 3. Since for large values of A and B, the loop would be rather time consuming, try a problem with big numbers, randomly typed at the keyboard by me:

A = 2345235345453;
B = 124234443643;

log2(2345235345453) % well short of the maximum allowed
ans =
          41.0928698437691

X = mod(-mod(A,B),B)
X =
               15219083764
               
mod(A + X,B) % verification step
ans =
     0

(A+X)/B
ans =
    19

A/B
ans =
          18.8774970666932

As we showed above, there is no smaller positive value of X that will satisfy the requirement. Had we used a simple loop to solve the problem, a brute force loop would have taken over 15 BILLION iterations before it terminated in this case, and A and B could easily have been larger.

Is there another solution? Could we have solved this using floating point arithmetic? Well, in fact, yes. We could have done it as

X = ceil(A/B)*B - A
X =
               15219083764

I'll let you think about why this works. Will it always work? Well, at least, as long as A and B are not excessively large, so as to cause floating point problems? Lets try a nasty example.

A = 2^53 - 1;
B = 2^52 - 1;
X1 = mod(-mod(A,B),B)
X1 =
      4.50359962737049e+15
X2 = ceil(A/B)*B - A
X2 =
      4.50359962737049e+15
X1 == X2
ans =
  logical
   0

So even though they look the same, they are not so. In fact, X1 is correct. The modular formula I gave you first is slightly more stable.

uint64(X1)
ans =
  uint64
   4503599627370494
   
uint64(X2)
ans =
  uint64
   4503599627370493

In fact, the latter solution I give here is risky only when (A+X)*B exceeds 2^53-1. So it is not a bad thing.

When mathematics is available to solve a problem in an elegant way, brute force is generally not a better choice.

Answer 2

[madhan ravi]

A=10;
B=3;
r=rem(A,B);
while r~=0
    A=A+1;
    r=rem(A,B);
end
A

[John D'Errico]

As long as A and B are integers, no larger than 2^53-1, AND as long as the final result is also no larger than 2^53-1, this will work, and is a reasonable solution. It is also the solution which follows that posed by Sarah as closely as possible.

Note that it may be a long running solution if A and B are sufficiently large.

[madhan ravi]

Thank you John D'Errico .