Anticipar el desbordamiento factorial

Me pregunto cómo podría anticipar si la próxima iteración generará un desbordamiento de enteros al calcular el factorial F o no?Anticipar el desbordamiento factorial

Digamos que en cada iteración tengo un int I y el valor máximo es MAX_INT.

Parece una tarea, lo sé. No es. Es solo que me hago preguntas "estúpidas".

Addendum

I aunque sobre, dado un número de bits (la anchura un número entero puede tomar, en bits), podría redondear el número I a la siguiente potencia de dos, y detectar si un cambio hacia izquierda excedería BITS. ¿Pero cómo se vería eso, algorítmicamente?

Fuente

2010-06-06 Flavius

Esto no es necesariamente una respuesta a su pregunta, así que no lo estoy publicando así, pero puede ser más eficiente codificar estos valores en su programa. No es como si el valor de los factoriales cambiara, y sería bueno tener una configuración de búsqueda como esta en la que se pudiera ver en tiempo constante si el factorial se desbordara o no. – avpx

@avpx: en C++, incluso podría usar plantillas para generar las tablas y el código de búsqueda apropiados para los tamaños de ese compilador para enteros en tiempo de compilación de una manera portátil. – Omnifarious

pista alternativa:

a * b ≤ MAX_INT

es equivalente a

a ≤ MAX_INT/b

si b> 0.

Fuente

2010-06-06 21:55:23 kennytm

¡Duh!¡No me puedo imaginar por qué no se me ocurrió este enfoque! – swestrup

Los factoriales son una serie de multiplicaciones, y la cantidad de bits necesarios para mantener el resultado de una multiplicación es la suma de los bits de los dos multiplicandos. Por lo tanto, mantenga un total acumulado de cuántos bits se usan en su resultado y la cantidad actual de bits necesarios para mantener el valor en el que se está multiplicando. Cuando eso es mayor que la cantidad de bits restantes, está a punto de desbordarse.

Fuente

2010-06-06 21:53:48 swestrup

Voy a masticar, pero aceptaré la respuesta de KennyTM, ya que es más intuitiva, matemáticamente. @ Usuarios de SO: por favor, vote esta, ¡es una buena respuesta! – Flavius

... pero esto es solo muy aproximado: ejemplo: 2 * 2 * 2 * 2 = 16 multiplicación de 4 valores, 2 bits cada uno, da como resultado un valor de 4 bits, pero 3 * 3 * 3 * 3 = 81, también una multiplicación de 4 valores, 2 bits cada uno, da como resultado un valor de 6 bits. La solución de Moron es más precisa. – Curd

Implementar esto ingenuamente tenderá a hacer que subestimes cuando vas a desbordarte. Factorial va de muy bien a desbordamiento en gran paso al final de la multiplicación, por lo que esto realmente solo te meterá en problemas cuando el último factorial antes del desbordamiento esté cerca de MAX_INT, pero puede hacerlo. 4 toma 3 bits para representar y 3 toma 2, pero 12 solo toma 4 bits para representar, no 5. – Omnifarious

Si ha conseguido hasta ahora m = (n-1)! y que está a punto de multiplicar por n , puede protegerse contra el desbordamiento comprobando que

m <= MAX_INT/n

Fuente

2010-06-06 21:57:27

Puede utilizar probablemente Stirling's Approximation formula que dice que

ln (n!) = N * ln (n) - n + ln (2 * pi * n)/2 + O (1/n)

y será bastante preciso.

No necesita tratar de multiplicar, etc. Por supuesto, esto no responde directamente a lo que ha preguntado, pero dado que solo tiene curiosidad, espero que esto ayude.

Fuente

2010-06-06 22:02:52

+1 Eso es lo que quería responder. Y: el registro de un valor es proporcional al número de bits necesarios para representar el valor. Así que esto es todo lo que Flavius necesita. – Curd

Este fue mi primer pensamiento también, pero no recuerdo el nombre de la fórmula de aproximación. Estúpidamente suficiente, es lo mismo que mi nombre. : - / – swestrup

Anticipar el desbordamiento factorial

Respuesta

Cuestiones relacionadas