21 junio 2007

Factoriales

El factorial de N es el producto de todos los números enteros desde 1 hasta N. Se escribe con el símbolo !:

N! = 1x2x3x...x(N-1)xN

Esto lo sabe todo el mundo. Ahora un problemilla para pensar un poco:

Tenemos un procesador que puede trabajar con números binarios de X bits. En los ordenadores normales X es potencia de 2: 4, 8, 16, 32, 64... pero en este problema eso no influye.

¿Cuál es el factorial máximo que podemos representar en ese procesador? Recuerdo que con X bits se puede representar desde el 0 a 2^X -1.

Con 4 bits podemos representar hasta el 15, por tanto el máximo factorial representable es 3! (1*2*3 = 6).
Con 5 bits el máximo es 31 así que sólo nos cabe 4! (1*2*3*4 = 24)

¿Cuál es la mejor manera de calcula el factorial máximo que cabe en esos bits?