8 de octubre de 2010

ene por ene más uno sobre 2

Este post cuenta otra de esas anécdotas relacionadas con computación y, en este caso además, matemáticas.

Corría el año... debe haber sido 1999. Yo era un feliz y entusiasta estudiante de matemáticas, y me sentía atraído por las computadoras; aunque hasta ese entonces no había tenido un fuerte contacto con ellas. En segundo año de la carrera, tenemos una materia que se llama Análisis Numérico, y utilizábamos la computadora para resolver ciertos problemas matemáticos, como encontrar raíces de ecuaciones. Aprendíamos a programar un poquito... y ahí fue cuando me empezó a picar el bichito de la programación. Tanto me gustó que al cuatrimestre siguiente me apunté a un curso de programación. Y luego tanto me gustó que me cambié de carrera a Ciencias de Computación, la terminé, estoy contento y currando (verbo elegido totalmente adrede) con esto.
El curso de programación era en el lenguaje Pascal, un lenguaje bastante decente sobre todo para aprender. Se dictaba en una academia de modestas pretenciones, el profesor era un compunauta al que llamaremos "jeisi" (JC). Jeisi era muy piola (majo) y bastante didáctico... aunque por ahí le hubiera faltado saber un poco más en cuanto a lo técnico. Pero, repito, para un curso de introducción a la programación estaba muy bien. Tengo buenos recuerdos de él.
El caso es que estábamos aprendido los bucles y nos había dado el siguiente ejercicio:

El usuario ingresa un número n. Nuestro programa tiene que calcular
la suma de 1 hasta n e imprimir el resultado en pantalla.

La idea era utilizar un bucle para ir acumulando la suma parcial en una variable, y luego simplemente imprimir el valor de la misma.
Ahora bien, los que sepan matemáticas (y los que sepan computación también deberían!!) ya se han dado cuenta que no es necesario hacer dicha suma número por número. Hay una forma directa, que además debe ser lo primero que uno demuestra cuando aprende inducción, que nos dice lo siguiente:

1 + 2 + 3 + ... + n = n*(n+1)/2

Es decir, no necesitamos calcular toda la suma número a número. Imagínense si n es muy grande, es un pérdida de tiempo: es suficiente hacer una multiplicación y luego una división. El resultado será exactamente el mismo.

Mi programa, entonces, no utilizaba bucles. Básicamente tenía 2 líneas:

1: obtener n 
2: imprimir n*(n+1)/2

Cuando Jeisi vió mi programa puso la mejor cara de WTF que ví jamás, mucho mejor que la mía en esta ocasión.Lamento ahora que todavía no tengamos cámaras de fotos integradas en los ojos, porque hubieria sido legendario.

No me creyó. Me dijo que no daría el resultado correcto. Con la tranquilidad de quien se sabe con la razón de su lado, le dije que estaba «matemáticamente demostrado» y lo invité a que probara haciendo algunas cuentas. Esto no cuenta como demostración, pero sirve para convencerse. Hay algunas demotraciones gráficas que no sabía y no se me ocurrieron, pero hubieran servido en aquel momento.

Tiempo después me dí cuenta que usar el método de n*(n+1)/2 está propenso a overflows y hay que tener cuidado con esto. Estrictamente hablando, la implementación con el bucle es más «correcta» que la implementación con la fórmula sin cuidado de overflow.


Desde ese día Jeisi me elevó a la categoría de semigenio y yo aprendí que cualquier programador más o menos serio necesita tener un buen background en matemáticas.