Programando números grandes
¡Hola! bienvenidos a la cuarta entrega de la serie de Matemáticas para Data Science. En las entregas pasadas se habló de métodos de conteo y conjuntos y observamos que los factoriales y potencias son de vital importancia para aprender a contar. ¿Qué pasa si las queremos programar? una opción valida es importar una librería y usar las funciones correspondientes, pero… ¿y si nosotros las queremos programar sin necesidad de librerías? sólo porque queremos sentir la emoción de programar.
En esta entrega se hablará del tiempo que le toma a la computadora realizar las operaciones de factorial y de potenciación para ver la diferencia, veremos una forma distinta de aplicar las operaciones y poder así calcular estas más rápidamente
¡Comencemos!
Tiempo de cómputo
De una forma intuitiva se puede decir que
Es el tiempo que le toma a la computadora realizar una operación
Cada instrucción que le damos a la computadora toma un determinado tiempo realizarlo, tiempo lineal, tiempo exponencial, logarítmico, etc.
Lo ideal es conseguir realizar un cierto número de operaciones en el menor tiempo posible. A lo largo de esta entrega veremos cuales son las formas más convenientes de reescribir las operaciones para que se ejecuten en el menor tiempo posible, aunque algunas de estas pierdan precisión, analizaremos cuan certeras son.
Factorial
Teorema 1. (Representación del factorial) El factorial se puede reescribir de la siguiente manera
Observamos que el factorial es una función recursiva, veamos cuánto tiempo le tomaría a la computadora realizar la operación factorial
La complejidad del factorial está dado por O(n)
Esto significa que crece de una forma lineal, o sea, como la sencilla fórmula que sabemos para líneas rectas f(x)=mx+b la siguiente pregunta que surge es
¿Se podrá hacer en un tiempo menor?
La respuesta es SÍ sin embargo, al momento de hacer esto se pierde un poco de precisión, es decir, sólo se puede aproximar el resultado. ¡Veamos su aproximación y cuán exacto es este!
Aproximación de Stirling
Teorema 2. (Aproximación de Stirling) La aproximación del factorial se puede ver como
Nota: Los picos generados es por procesos internos del sistema, sin embargo, se observan los comportamientos de los factoriales correctamente, como se quería
La complejidad de la aproximación de Stirling es O(log(n))
Comparemos ahora qué tan exacta es la aproximación de Stirling con el valor del factorial
Observamos que la diferencia es mínima, más aún veamos cuál es la taza de cambio
Podemos observar que va teniendo una asíntota con el valor y=0 implicando que la aproximación de Stirling crece más rapidamente que el factorial, sin embargo observamos que llegando al valor n=100 este cociente está rozando al valor y=1 lo que nos hace pensar que el desface será significativo para valores más grandes
Suma de potencias
La suma de potencias es una operación típica en matemáticas, veremos cómo se puede obtener el resultado general de estas para solamente evaluarlo sin necesidad de sumar todos los términos individualmente. La primera pregunta que surge es
¿Podemos asegurar que la suma de potencias siempre será finito?
La respuesta a esa pregunta es Sí, la suma de potencias, hablando bajo el contexto de programación será finita, debemos tener en cuenta que las bases serán números naturales, ya que hablando en el contexto de programación, es imposible llegar a tener una infinidad de términos, pues si esto fuera cierto se necesitaría una infinidad de tiempo y una infinidad de procesamiento. Así, aclarando esa parte tenemos el siguiente
Teorema 3. (Suma de potencias) Sea p un número natural, la expresión general para la suma de potencias está dada por
Observamos lo que se aclaraba anteriormente, n en la suma no puede ser infinito, veamos que la suma es acotada
Veamos el tiempo computacional de estas operaciones, comparando la suma como tal y después usando la fórmula general dada en el Teorema 3
En el gráfico anterior, observamos que hacer la suma sumando cada término tenemos un mayor tiempo de cómputo inicial y por un mayor tiempo, por otro lado, al ser la sustitución una forma donde solamente tenemos que evaluar, toma menos tiempo hacerlo y dura menos,
Esta entrega fue un análisis computacional de los métodos de conteo y de cómo optimizar su tiempo computacional, de nuevo recalcando que aunque se pueden usar librerías, el lector puede optar por hacerlas él mismo.
La combinación, la permutación, el factorial y las tuplas son métodos de conteo que usan los artificios aquí analizados.
Esperamos que el análisis hecho le sirva al lector, que, aunque si se computan números pequeños la diferencia será imperceptible, sin embargo, si se requieren hacer varias de estas operaciones se llevará más tiempo.
¡Gracias y saludos!
Chucho Montesinos
