domingo, 10 de febrero de 2013

Cálculo con numeros relativamente grandes.

En algunas ocasiones el sentido común puede ser una guía mas bien engañosa. Sobre todo cuando tratamos problemas simples en los cuales se ven envueltos, a veces sin que estemos completamente conscientes de ello, números grandes.

Por ejemplo veamos un problema clásico:

No todos los juegos, son deportes. Aun más son pocos los deportes que tienen asociado a su nacimiento una leyenda que contiene un problema matemático. Me estoy refiriendo a la leyenda que cuenta el origen del juego de ajedrez. A grandes rasgos la leyenda cuenta que en el momento en que el sultán conoció el juego, este le gustó tanto que quiso premiar a su creador. Teniéndose sí mismo por un gran hombre, le pidió que el expresara un deseo y lo vería hecho realidad. La respuesta fue insólita. El creador del juego pidió un grano de trigo por la primera casilla del tablero, dos por la segunda, cuatro por la tercera, ocho por la siguiente y así sucesivamente. El sultán se sintió menospreciado por este hombre y le ordenó que esperase fuera; que inmediatamente le sería entregado dentro de un saco lo que pidió.

Nuestro sultán terminó sin saberlo con dos regalos, un juego trascendental y una lección de humildad. A veces lo grandes hombres reciben más regalos de los que pueden apreciar. 

Volviendo a C#, si nos correspondiese a nosotros desempeñar el rol de matemático de la corte, nuestra respuesta debería ser la misma que recibió el sultán de la leyenda: ni sembrando toda la superficie de a tierra durante varios años y entregando hasta el último grano cosechado podrían satisfacer la petición formulada por su creador. La única diferencia es que nosotros podemos llegar más rápido a esa conclusión. Escribir unas pocas líneas de código C# dentro del cuerpo de una función es todo lo que tenemos que hacer. Estas líneas podrían tener el siguiente aspecto:

static long CantidadSemillas(int alto = 8, int ancho = 8)
{
long resultado = 0;
int celdas = alto * ancho;

for (int i = 0; i < celdas; i++)
resultado += (long)Math.Pow(2, i);

return resultado;
}

Utilizando esta función para un tablero de 4x4 casillas, obtendríamos rápidamente la respuesta: 65535 granos de trigo. Sin embargo para un tablero normal de 8x8 casillas obtenemos -1. No hay errores en tiempo de ejecución y sin embargo la respuesta es incorrecta. Esta es la parte donde el “gran hombre” nos mandaría a decapitar. Aún sin cabeza deberíamos preguntarnos ¿qué fue lo que ocurrió y por qué recibimos una respuesta disparatada en lugar de un mensaje de error? 

Modifiquemos el código anterior para usar enteros largos sin signo. Quedaría así.

static ulong CantidadSemillas(int alto = 8, int ancho = 8)
{
ulong resultado = 0;
int celdas = alto * ancho;

for (int i = 0; i < celdas; i++)
resultado += (ulong)Math.Pow(2, i);

return resultado;
        }

Al ejecutar este código recibimos la respuesta correcta: 18446744073709551615

De aquí podemos deducir que anteriormente hubo un error de desborde, tanto la respuesta como algunos de los cálculos intermedios para determinar la respuesta era representable usando variables de tipo entero largo. Las variables de tipo entero largo utilizan 8 bytes y pueden tomar valores enteros entre -9223372036854775808 y 9223372036854775807.

Pero aún tenemos la curiosidad, ¿por qué no nos fue notificado que había ocurrido un error? Volvamos a modificar el código para que utilice checked y quede así:

       static ulong CantidadSemillas(int alto = 8, int ancho = 8)
       {
            ulong resultado = 0;

            int celdas = alto * ancho;
           
            checked
            {
                for (int i = 0; i < celdas; i++)
                    resultado += (ulong)Math.Pow(2, i);
            }

            return resultado;
       }

Ahora calculamos la cantidad de semillas de trigo a entregar si usásemos un ajedrez modificado al estilo Sheldon Cooper y las dimensiones del tablero fueran de 16X16 casillas.

Ahora sí recibimos nuestra querida Overflow Exception que nos notifica que algo fue mal evitándonos respuestas incorrectas. Si comentamos la línea de código que contiene checked y volvemos a correr el programa pues obtenemos una respuesta incorrecta que tomaríamos como correcta con todas las consecuencias que podría traer esto. Las computadoras no se equivocan pero este comportamiento es lo más parecido.

La palabra clave checked se utiliza para habilitar precisamente el chequeo de errores de desbordamiento para expresiones no constantes en tiempo de ejecución. Es necesario prever la aparición de números grandes en cálculos intermedios para habilitar esta opción o no. Esta trivialidad ha causado comportamientos anómalos en más de una ocasión que pueden hacernos sentir que "perdemos la cabeza".

 




















No hay comentarios:

Publicar un comentario