Evitar el desbordamiento en la multiplicación de enteros seguido por la división

Tengo dos variables integrales a y b y una constante s resp. d. Necesito calcular el valor de (a*b)>>s resp. a*b/d. El problema es que la multiplicación puede desbordarse y el resultado final no será correcto, aunque a*b/d podría caber en el tipo integral dado.Evitar el desbordamiento en la multiplicación de enteros seguido por la división

¿Cómo podría resolverse de manera eficiente? La solución directa es expandir la variable a o b a un tipo integral más grande, pero puede no haber un tipo integral más grande. ¿Hay alguna forma mejor de resolver el problema?

Fuente

2011-04-04 Juraj Blaho

Debo inferir que 'd' siempre es' 1 << s'. ¿Es eso cierto? –

Sí, es cierto. –

Su mejor opción es expandirse a un tipo integral más grande. –

Si no hay un tipo más grande, necesitará encontrar una biblioteca de estilo big-int, o tratar con ella manualmente, utilizando una larga multiplicación.

Por ejemplo, suponga que a y b son de 16 bits. Luego puede reescribirlos como a = (1<<8)*aH + aL y b = (1<<8)*bH + bL (donde todos los componentes individuales son números de 8 bits). Entonces usted sabe que el resultado global será:

(a*b) = (1<<16)*aH*bH 
     + (1<<8)*aH*bL 
     + (1<<8)*aL*bH 
     + aL*bL

Cada uno de estos 4 componentes se ajuste a un registro de 16 bits. Ahora puede realizar, p. cambios a la derecha en cada uno de los componentes individuales, teniendo cuidado de tratar con los acarreos de manera apropiada.

Fuente

2011-04-04 17:34:03

Creo que el problema que se plantea es que a * b podría no caber en 16 bits, aunque se garantiza a * b/d caber. Por lo tanto, su solución no ayuda. –

@Mark Ransom: Sí. Con mi método, no necesita valores de 32 bits. –

Sí, esto funcionaría, pero parece que hay algunos cálculos desperdiciados en esta solución. Me pregunto si no podría fusionarse de alguna manera con la división (cambio a la derecha) para obtener un código más eficiente. –

No he probado exhaustivamente esto, pero ¿podría hacer la división primero, y luego cuenta para el resto, a expensas de operaciones adicionales? Como d es una potencia de dos, todas las divisiones se pueden reducir a operaciones bit a bit.

Por ejemplo, suponga siempre a > b (primero debe dividir el número más grande). Luego a * b/d = ((a/d) * b) + (((a % d) * b)/d)

Fuente

2011-04-04 17:40:39

Creo que '(a% d) * b' aún podría desbordarse (el mayor valor posible es' (d-1) * b'). –

puede usar la misma técnica que Mark B explicó para la parte ((a% d) * b)/d, viendo un% d como b y b como a. – steabert

@steabart: Sí, es cierto. Debe recurrir tantas veces como sea necesario para estar seguro. –

Si el tipo más grande tiene solo 64 bits, la solución directa probablemente resulte en un código eficiente. En las CPU x86, cualquier multiplicación de dos números de 32 bits dará el desbordamiento en otro registro. Entonces, si su compilador comprende eso, puede generar código eficiente para Int64 result=(Int64)a*(Int64)b.

Tuve el mismo problema en C#, y el compilador generó un código bastante bueno. Y los compiladores de C++ suelen crear mejores códigos que el .NET JIT.

Recomiendo escribir el código con los moldes para los tipos más grandes y luego inspeccionar el código ensamblado generado para verificar si es bueno.

Fuente

2011-04-04 17:42:29 CodesInChaos

He examinado el desmontaje y 'int32_t result = (int64_t (a) * int64_t (b)) >> 2' genera un código agradable (solo' imul' para la multiplicación). Pero cuando b es constante, el compilador genera 'call _allmul'. Eso parece un poco extraño. Tendré que mirar más adentro. –

En ciertos casos (históricamente generadores de números aleatorios LCG con constantes seleccionadas), es posible hacer lo que desee, para algunos valores de ay d.

Esto se llama el método de Schrage, véase, por ejemplo. there.

Fuente

2011-04-05 10:53:07

Evitar el desbordamiento en la multiplicación de enteros seguido por la división

Respuesta

Cuestiones relacionadas