Forma rápida de encontrar el siguiente múltiplo de un número

Necesito encontrar el primer múltiplo de un número comenzando desde un número base. Por ejemplo: El primer múltiplo de 3 a 7 es 9. Mi primer intento fue hacer esto:Forma rápida de encontrar el siguiente múltiplo de un número

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

Al final, "múltiple" tendrá el primer múltiplo de number después baseNumber. El problema es que cuando number se vuelve demasiado grande, el número de iteraciones llega a ser demasiado. Entonces mi pregunta es: ¿hay una manera más rápida de hacer esto?

Fuente

2012-07-27 LuisEspinoza

Usted puede ser mejor pedir esto en la pila Cambio de Matemáticas. También es posible que desee proporcionar una definición más clara o más rigurosa de lo que quiere decir con múltiples de un número. – Jim

Si todo está garantizado para ser positivo, tratar

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

que lo hace en un tiempo constante.

Primero, agregamos number - 1 para asegurarnos de tener un número al menos tan grande como el siguiente pero más pequeño que el siguiente. Luego restamos el resto de la división al number para asegurarnos de tener el múltiplo deseado.

Si baseNumber puede ser negativo (pero number siendo positiva), nos enfrentamos al problema de que multiple % number puede ser negativo si multiple < 0, por lo que lo anterior podría saltar un múltiplo de number. Para evitar eso, podemos usar, p.

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

Si ramificación es demasiado caro, podemos evitar la if a costa de dos divisiones en lugar de uno,

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

general, el if parece preferible, sin embargo.

Si number puede ser negativo, sustitúyalo primero con su valor absoluto.

Nota: Lo anterior devuelve, como lo hace el código original, baseNumber si eso ya es un múltiplo de number. Si no se desea, elimine el - 1 en la primera línea.

Fuente

2012-07-27 17:43:26

No creo que esto sea correcto, suponiendo que se requiere el siguiente múltiplo mayor que 'baseNumber'. Considere 'baseNumber = 6, number = 3'; obtendrás 6. En términos más generales, creo que esto fallará siempre que 'number' divida' baseNumber'. – DSM

Fui por código de OP que también devuelve 'baseNumber' si eso ya es un múltiplo. Pero agregaré una nota sobre esto, gracias. –

@DSM Si ese es el caso, entonces todo lo que tiene que hacer es eliminar el "-1", y debería estar bien. –

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

por lo que para baseNumber = 3, número = 7, su múltiplo es 3;

sin embargo, algo me dice que los bignums están a punto de aparecer aquí.

Fuente

2012-07-27 17:44:37 Shark

Siento que esto tiene el mismo problema que el OP. Supongamos que 'number' es algo así como 2 y baseNumber es 1 billón. No desea tener que verificar todos los múltiplos de 2 hasta 1 mil millones. –

en ese caso, esto es más cuestión matemática, entonces ... sé que hay una fórmula para eso. tengo que buscar mis viejas notas criptográficas, supongo ... – Shark

probar esto (Requiere división entera):

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

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

tiene un caso borde donde la baseNumber es ya una múltiplo de number, que deberá probar utilizando la operación de módulo.

Fuente

2012-07-27 17:45:14

Doh. Casi repitió tu respuesta. ¿Pero no necesitas una función de piso después de la base/número? – bigbenbt

División entera: D –

Ah. Entonces hay una RAZÓN de poner palabras en negrita. – bigbenbt

¿Por qué necesita un bucle?

múltiple = (piso (número/baseNumber) 1) * baseNumber

Fuente

2012-07-27 18:09:21 bigbenbt

Forma rápida de encontrar el siguiente múltiplo de un número

Respuesta

Cuestiones relacionadas