Fast way to find the next multiple of a number

问题:

I need to find the first multiple for a number starting from a base number. For example: The first multiple of 3 from 7 is 9. My first attempt was to do this:

multiple = baseNumber
while(multiple%number !=0 )
    multiple++

At the end, "multiple" will have the first multiple of number after baseNumber. The problem is that when number becomes too large, the number of iterations becomes too many. So my question is: is there a faster way to do this?

回答1:

If everything is guaranteed to be positive, try

multiple = baseNumber + number - 1;
multiple -= (multiple % number);

That does it in constant time.

First, we add number - 1 to make sure that we have a number at least as large as the next multiple but smaller than the one after that. Then we subtract the remainder of the division by number to make sure we have the desired multiple.

If baseNumber can be negative (but number still positive), we face the problem that multiple % number may be negative if multiple < 0, so the above could skip a multiple of number. To avoid that, we can use e.g.

remainder = multiple % number;
if (remainder < 0) remainder += number;
multiple -= remainder;

If branching is too expensive, we can avoid the if at the cost of two divisions instead of one,

multiple -= (number + (multiple % number)) % number;

Generally, the if seems preferable, though.

If number can be negative, replace it with its absolute value first.

Note: The above returns, as the original code does, baseNumber if that is already a multiple of number. If that isn't desired, remove the - 1 in the first line.

回答2:

try this (Requires INTEGER division):

multiple = ((base/number) + 1) * number;

7/3 = 2. 3*(2+1) = 9.

You have an edge case where the baseNumber already is a multiple of number, which you will have to test using the modulus operation.

回答3:

Why do you need a loop?

multiple = (floor(number/baseNumber)+1)*baseNumber

回答4:

 while(multiple * number < baseNumber)
      multiple++;

so for baseNumber = 3, number = 7, your multiple is 3;

though, something tells me bignums are about to show up in here.