Algoritmos más eficientes aplicando matemáticas

Continuando con mi visión de que las matemáticas son de mucha ayuda en la creación de software, en este post daré un ejemplo de cómo con una ecuación de segundo grado se puede construir una versión de un programa más eficiente que usando exclusivamente la lógica de programación.

Primero pido excusas a los puristas de las matemáticas ya que por ser tan amplias y tan exactas no domino la jerga a totalidad y probablemente diga una cosa cuando signifique otra, pero sé que me entenderán.

Supongamos que nos piden hacer un programa de esos que los profesores asignan en introducción a la programación para despertar la lógica. El programa debe pedir un número y calcular la sumatoria desde 0 hasta el número dado:
$$ \sum_{k=0}^n{k} $$
como si fuera el factorial, pero en vez de multiplicar, sumar. Por ejemplo, si el número introducido fue el 6
, lo que hará el programa es sumar 6+5+4+3+2+1 y dar el resultado = 21:
$$ \sum_{k=0}^6{k} = 0+1+2+3+4+5+6 = 21 $$
Lo que se haría normalmente sin utilizar ningún recurso matemático es hacer un bucle que itere el número de veces que el mismo número introducido y en cada iteración vaya sumando el número de esa vuelta con el pasado y guardando un acumulado, hasta llegar al final. El código se explica mejor que yo:

for(int i=0; i<=num; i++){
    acu += i;
}  

Donde num es el número dado hasta el cual se debe hacer la sumatoria.
De igual forma se podría expresar así:

for(int i=num; i!=0; i--){
    acu += i;
}

Aunque en programas pequeños no hay una diferencia notable de rendimiento, esta es una versión menos eficiente que la que a continuación vamos a desarrollar usando una ecuación de segundo grado.

Si nos fijamos bien, lo que queremos conseguir realmente es una función que reciba un valor y nos devuelva otro. En cierta forma estos valores son fijos, es decir que a cada valor que introduzcamos le pertenecerá otro valor único. El valor único es el que obtendremos al "procesar" el número dado con la función.

Así podemos hacer una relación (tabla) de valores de entrada y valores de salida. En la columna Entrada están los números originales, en la columna Salida el resultado de hacer la sumatoria con el número de la columna entrada de la misma fila. Empecemos desde el 3:

Entrada	Salida
3	6
4	10
5	15
6	21
7	28
8	36
9	45
10	55
11	66
12	78
13	91
. . .	. . .

Como vemos lo que tenemos es una tabla de valores donde muy bien las columnas entrada y salida podría ser $x$ y $y$ respectivamente. Si graficamos esos puntos en Calc tendremos una parábola, la cual no se extiende hacía los enteros negativos porque no hemos incluido números negativos en lo que hemos venido haciendo.

Gráfica de los puntos de la tabla anterior

Sabemos que una ecuación de segundo grado siempre que se grafica da como resultado una parábola, entonces ya solo nos queda saber cuál es la ecuación de segundo grado que define esa parábola, cuando lo logremos tendremos la función que recibe un número y devuelve su sumatoria desde 0 hasta el mismo número (porque eso es lo que representan esos puntos que graficamos), o sea, tendremos el algoritmo principal del programa.

Encontrando la ecuación/función

La parte que sigue es puramente matemática, si sabes como encontrar una ecuación de segundo grado a partir de tres puntos dados puedes saltártelo.

Para hallar la función/ecuación usamos los puntos que tenemos, pueden ser cuales quiera tres puntos. Yo usaré los del cero hasta el 3, por ser más sencillo de operar con ellos. Aunque no los incluí en la tabla, estos son: $(0,0),(1,1),(2,3)$.

Cualquier ecuación de segundo grado tiene la forma $y = ax^2 + bx + c$. De esa expresión sabemos quien es $x$ y quien es $y$ por los puntos que escogimos, así que sustituimos y formamos tres ecuaciones distintas que pertenecen a un mismo sistema:

$$\begin{aligned}
\textrm{A:} \;\;\;\; 0 = c \\
\textrm{B:}  \;\;\;\; 1 = a + b \\
\textrm{C:} \;\;\;\; 3 = 4a + 2b
\end{aligned}$$
Resolvemos el sistema de ecuaciones:
$$ \begin{aligned} \textrm{B:} \;\;\;\; b = 1 - a \\
\textrm{Sustituyendo B en C:} \\ 3 = 4a + 2(1 - a) \\
3 = 4a + 2 - 2a \\
a = 1/2
\end{aligned}$$
Por lo que $b$ es:
$$b = 1/2$$
Sustituyendo $a, b, c$ en la forma general de una ecuación de segundo grado nos queda:
$$\begin{aligned}y = ax^2 + bx + c \\
y = 1/2x^2 + 1/2b\\
\textrm{Simplificando:}\\
y = \frac{x(x+1)}{2}
\end{aligned}$$
Una expresión que probablemente te resulte familiar...

No sustituimos $x$ y $y$ porque lo que queremos es dejarla expresada en función de esas variables. Dependiendo del valor que le demos a $x$, obtendremos un $y$ como hicimos antes con la tabla de valores, solo que ahora esta expresión que hemos encontrado es general y nos sirve para cualquier número. Con lo que ya tenemos hecho, pero no terminado el programa.

Terminando el programa

Ya que hemos encontrado la función solo nos queda hacer que el programa reciba un número y se lo pase como parámetro a la misma. Finalmente agregándole unas validaciones para controlar la entrada de datos y operando con el método System.currentTimeMillis() para hacer una comparación del tiempo de ejecución de esta versión con la que usa los ciclos, el programa en java quedaría así:

import java.util.Scanner;

 
public class nnmu{
 public static void main(String[] args){
  Scanner sc = new Scanner(System.in);
  String str = "";
  boolean error = false;
  long num = 0;
  long acu = 0;
  long tiempoInicioMili = 0;
  long tiempoFinalMili = 0;
  long tiempoTotalMili = 0;
  
  while(num != -1){
   do{
    try{
     error = false;
     System.out.println("Entre un número. -1 para terminar: ");
     str = (String) sc.nextLine();
     num = Integer.parseInt(str);
    }catch(NumberFormatException nfex){
     error = true;
     System.err.println("Error con la entrada de datos."+ 
     " Inténtelo otra vez.");
    }
   }
   while(error == true);
  
   System.out.println("Número escogido: "+ num);
   
   tiempoInicioMili = System.currentTimeMillis();
   acu = num*(num+1)/2;
   tiempoFinalMili = System.currentTimeMillis();
   
   tiempoTotalMili = tiempoFinalMili - tiempoInicioMili;
   
   System.out.println("SUMATORIA: " +acu);
   System.out.println("Tiempo ejecución (milisegundos): "
    +tiempoTotalMili + "\n\n\n\n\n");
  }
  
  
 }
 
}

Con el algoritmo que hemos desarrollando matemáticamente tendremos el resultado de una manera muchísimo más eficiente. Supongamos que el número de entrada sea muy grande, claro está que al procesador le toma mucho más trabajo hacer un millón de sumas (que es como lo hicimos la primera vez, con un bucle) que hacer una multiplicación, una suma y una división. Aquí está la prueba:

1,315 milisegundos. Tiempo de ejecución usando la versión ineficiente (con ciclos)

0 milisegundos. Tiempo de ejecución de la versión eficiente (con la función)

Como vemos el tiempo de ejecución con la versión que desarrollamos es menor a un milisegundo por lo que pone cero, o sea que es mucho más rápido el programa.