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.

3 comentarios:

Laureano Remedi dijo...

Muy bueno!!, recuerdo la anecdota de un profe de la facu, en una de sus demostraciones de analisis que nos comentaba sobre un matematico en sus etapas de niño, del que te debo del nombre. Donde supuestamente la maestra les dio para sumar a raiz de un mal comportamiento grupal y que queria tomarse unos mates sin que la molesten, como ejercicio de clase que sumen los numeros del 1 al 100. Esta alumnito empezo a sumar de forma distinta a lo que haria el resto. Sumo:
1+100 = 101
2+99 = 101
y ahi se dio cuenta de la formulita propuesta por vos para evitar los bucles...
(n+1)*n/2

Groso Maxlo, muy bueno el post...

Matthias Gallé dijo...

Como dijo maxlo en un de esos sitio de redes sociales redundantes, era Gauss. Un lindo artículo sobre la veracidad de esa historia se encuentra aca

Cristian Perfumo dijo...

Me encantan estas historias geek!!! Quiero más.

Yo también iba a una academia de computación. Nos enseñaban a usar DOS.

Uno de los profesores se llamaba Xavier y de un día para el otro desapareció del pueblo. Muchos afirman haberlo visto travestido en un programa de televisión (esto es posta, que afirman).

ABRAZOTE!