Szybki sposób na znalezienie następnej wielokrotności numeru

Question

Potrzebuję znaleźć pierwszą wielokrotność numeru zaczynającego się od numeru bazowego. Na przykład: Pierwszy wielokrotnością 3 z 7 9. Moja pierwsza próba była to zrobić:

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

Na koniec, „stwardnienie” będzie miał pierwszy wielokrotność number po baseNumber. Problem polega na tym, że gdy number staje się zbyt duży, liczba iteracji staje się zbyt duża. Moje pytanie brzmi: czy istnieje szybszy sposób na zrobienie tego?

Answer 1

Jeśli wszystko jest gwarancją pozytywny, spróbuj

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

Że robi to w czasie stałym.

Najpierw dodajemy number - 1, aby upewnić się, że mamy numer co najmniej tak duży jak kolejny numer, ale mniejszy niż kolejny. Następnie odejmujemy resztę podziału przez number, aby upewnić się, że mamy pożądaną wielokrotność.

Jeśli baseNumber może być ujemna (ale number nadal dodatnia), możemy zmierzyć się z problemem, że multiple % number mogą być ujemne, jeśli multiple < 0, więc powyższe mógł pominąć wielokrotność number. Aby tego uniknąć, możemy użyć np.

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

Jeżeli rozgałęzienie jest zbyt kosztowne, możemy uniknąć if kosztem dwóch dywizji zamiast jednego,

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

Generalnie if wydaje korzystne, choć.

Jeśli wartość number może być ujemna, należy najpierw zastąpić ją wartością bezwzględną.

Uwaga: Powyższe zwraca, tak jak oryginalny kod, baseNumber, jeśli jest to już wielokrotność number. Jeśli nie jest to pożądane, usuń - 1 w pierwszym wierszu.

Answer 2

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

tak dla baseNumber = 3, liczba = 7, twoja wielokrotność to 3;

Jednak coś mi mówi, że bignums już się tu pojawią.

Answer 3

spróbować (Wymaga dzielenia całkowitego)

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

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

Trzeba to przypadku krawędź, gdzie jest już baseNumber wielokrotność number, którą będziesz musiał przetestować używając operacji modulus.

Answer 4

Dlaczego potrzebujesz pętli?

wielokrotność = (piętro (liczba/baseNumber) +1) * baseNumber