Modo rapido per trovare il prossimo multiplo di un numero

Question

Ho bisogno di trovare il primo multiplo per un numero a partire da un numero base. Per esempio: il primo multiplo di 3 da 7 è 9. Il mio primo tentativo è stato quello di fare questo:

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

Alla fine, "multipla" avrà il primo multiplo di number dopo baseNumber. Il problema è che quando number diventa troppo grande, il numero di iterazioni diventa eccessivo. Quindi la mia domanda è: c'è un modo più veloce per farlo?

Answer 1

Se tutto è garantito per essere positivo, provare

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

che lo fa in tempo costante.

Prima di tutto, aggiungiamo number - 1 per assicurarci di avere un numero almeno grande come il prossimo multiplo ma più piccolo di quello successivo. Quindi sottraiamo il resto della divisione per number per assicurarci di avere il multiplo desiderato.

Se baseNumber può essere negativo (ma number ancora positiva), si affronta il problema che multiple % number può essere negativo se multiple < 0, la suddetta potrebbe saltare un multiplo di number. Per evitare ciò, possiamo usare per es.

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

Se ramificazione è troppo costoso, siamo in grado di evitare la if al costo di due divisioni invece di uno,

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

In generale, il if sembra preferibile, però.

Se number può essere negativo, sostituirlo prima con il suo valore assoluto.

Nota: quanto sopra riportato, come fa il codice originale, baseNumber se questo è già un multiplo di number. Se ciò non è desiderato, rimuovere - 1 nella prima riga.

Answer 2

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

quindi per baseNumero = 3, numero = 7, il tuo multiplo è 3;

però, qualcosa mi dice che i bignum stanno per apparire qui.

Answer 3

provare questo (Richiede divisione intera):

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

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

Hai un caso limite in cui la baseNumber è già multiplo di number, che sarà necessario testare utilizzando l'operazione modulo.

Answer 4

Perché è necessario un ciclo?

multipla = (piano (numero/baseNumber) +1) * baseNumber