viernes, 1 de marzo de 2013

¿Cuántas cifras tiene un número? Por ejemplo, el factorial de 1.000.000

El sistema de numeración que utilizamos es posicional y decimal, es decir que utilizando 10 dígitos (0, 1, 2, 3, 4, 5, 6, 7, 8 y 9) podemos escribir cualquier número entero.

¿Cuántas cifras tiene el número 92.368.556? Una pregunta bastante sencilla. Contamos y listo. 8 cifras.

¿Cuántas cifras tiene el factorial de 1.001? Pues ahora la cosa no es tan sencilla. Calcular el factorial de 1.001 y contar sus cifras es una posibilidad, pero en vista de que el número es bastante elevado vamos a intentar encontrar una alternativa que nos evite calcular el factorial.

Si volvemos al hecho de que usamos un sistema decimal, podemos concluir fácilmente que se añade una cifra más cada vez que damos un salto a la siguiente potencia de 10.
En 10¹ = 10 comienzan los números de 2 cifras.
En 10² = 100 comienzan los números de 3 cifras.
En 10³ = 1.000 comienzan los números de 4 cifras
... si generalizamos esta propiedad, podemos formularla como ...
En 10^n comienzan los números de n+1 cifras.

Si el cambio de cifras se produce en las potencias de 10, para conocer cuántas cifras tiene un número podemos utilizar la operación inversa a la exponenciación de base 10: los logaritmos decimales.


Por ejemplo, si tenemos en cuenta que log(10)=1 y log(100)=2, al calcular el logaritmo decimal de cualquier número entre 10 y 100 obtenemos, dado que el logaritmo es una función estrictamente creciente, un resultado decimal entre 1 y 2.

Entonces, la cantidad de cifras de un número cualquiera se obtiene sumando 1 a la parte entera de su logaritmo decimal.

Ejemplo: ¿Cuántas cifras tiene el número 92.368.556?
log(92368556) = 7,96552415434
La parte entera, a partir de ahora denotada por [], es [7,96552415434]=7.
Por tanto, el número 92.368.556 tiene 8 (7+1) cifras.

Si aplicamos esto mismo a la pregunta de cuántas cifras tiene 1001!, tendríamos:
cantidad de cifras de 1001! = [log(1001!)]+1

1001! es un número elevado para las calculadoras, pero wxMaxima puede calcular la expresión [log(1001!)]+1 directamente con el siguiente comando, sin que se produzca ningún desbordamiento:
entier(log(1001!)/log(10))+1;
Téngase en cuenta que en wxMaxima la función log corresponde al logaritmo neperiano y no al decimal, por eso aparece en la expresión la división entre log(10). El resultado que devuelve wxMaxima es:
2571
Bien, ya sabemos cuántas cifras tiene el factorial de 1001, pero además de que hemos hecho la gran trampa de que wxMaxima sí ha calculado el factorial de 1001, ¿qué pasa si el número es mayor? Pongamos por ejemplo que queremos saber cuántas cifras tiene 1.000.000!
Aquí wxMaxima ya no arroja resultados. Podríamos recurrir a la programación para definir una función que calcule el factorial multiplicando tipos enteros, pero la mayoría de lenguajes de programación tiene un rango limitado para sus tipos de variables. Por ejemplo, un tipo unsigned long long en el lenguaje de programación C tiene un rango de 0 a 18.446.744.073.709.551.615. Cualquier operación cuyo resultado sea mayor provoca un desbordamiento. Otros lenguajes de programación, como python, ya llevan implementadas en sus librerías funciones que efectúan las operaciones de este tipo sin provocar desbordamiento.
 
En cualquier caso, lo que estamos pensando es si puedo evitar el cálculo del factorial porque lo único que me interesa es saber cuántas cifras tiene. Así que volvemos a utilizar la expresión general:
cifras de n! = [log(n!)]+1

Nuestro problema era que no queremos/podemos calcular el factorial y si observamos la propiedad anterior resulta que ahora no sólo tengo que calcular un factorial sino que además tengo que calcular un logaritmo. Menudo invento. Bueno, tranquilidad. El factorial son productos y sabemos que los logaritmos tienen la propiedad de "transformar las multiplicaciones en sumas": log(a·b)=log(a)+log(b).
Así pues,
log(1000000!) = log(1000000·999999·...·2·1)=log(1000000)+log(999999)+...+log(2)+log(1).

¿Qué ganamos con esto? Pues reducir considerablemente el orden de los números con los que se trabaja. Los números decimales que aparecen en los sumandos de log(1000000)+...+log(2)+log(1) están comprendidos entre 0 y 6 (incluidos). La precisión de los tipos decimales de cualquier lenguaje de programación es más que suficiente para el cálculo anterior, especialmente si tenemos en cuenta que lo que nos interesa ahora es la parte entera del resultado del sumatorio.


Por ejemplo, en C++ podemos escribir el siguiente programa:



#include < stdlib.h >
#include < iostream >
#include < math.h >
main()
{
    double r=0;
    unsigned long int numero=1000000;
    for(unsigned long int n=1; n<=numero; n++)
    {
        r+=log10(n);
    } //for n
    unsigned long int cifras_factorial= (unsigned long int) r;
    cifras_factorial++;
    std::cout < < "El factorial de " < < numero < < " tiene " < < cifras_factorial < < " cifras." < < std::endl;
    return 0;
}


La ejecución del programa anterior devuelve la siguiente sentencia:
El factorial de 1000000 tiene 5565709 cifras.

Como curiosidad final, hice un programa en python que calcula todas las cifras del factorial de 1000000.


Entrada relacionada:
- El factorial de las mil y una noches.

1 comentario:

Félix dijo...

He de decir que la idea de esta entrada surgió a raíz de leer una entrada interesante en el blog Un informático en el lado del mal.

http://www.elladodelmal.com/2013/02/resolver-el-factorial-de-100-no-es.html