Tarea #6 [solución]

Rebase de operaciones aritméticas

      Para esta tarea programada usted debe enviarme estos archivos:

1. rebase.java
2. biblio.java
3. CARNET.docx
4. CARNET.html
5. CARNET.url

Es extraño cómo funcionan los valores infinitos porque el sentido común a veces no concuerda con la realidad. Por ejemplo, es posible demostrar que se puede contar los números racionales positivos al usar un recorrido como el que se muestra en este diagrama:

http://en.wikipedia.org/wiki/File:Diagonal_argument.svg
http://en.wikipedia.org/wiki/Rational_number

Al examinar este diagrama se puede concluir que la cantidad de números racionales es similar a la de números enteros, porque es posible contar cada uno de los números racionales positivos: a primera vista, esto es paradójico. Sin embargo, en la memoria de un computador no es posible almacenar todos estos valores porque cada número se presenta como una secuencia finita de bits, que en el caso del lenguaje Java es de 32 bits para el tipo (int) y de 64 bits para el tipo (long):
→ http://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html

El recorrido mostrado antes es engorroso de programar, porque primero sube y luego baja. Es más simple programar el recorrido por lo mismos números, pero comenzando por el primer renglón y bajando por la diagonal que cae de derecha a izquierda: [ 1/1 .. 1/2 2/1 .. 1/3 2/2 3/1 .. 1/4 2/3 3/2 4/1 .. 1/5 2/4 3/3 4/2 5/1 ... ]. Este orden es el que usted usará para recorrer los números racionales positivos que se pueden representar en variable Java de tipo (byte), que usan 8 bits y permiten almacenar los números enteros en el rango [-128 .. 127].

El mayor número entero que se puede almacenar en una variable entera de 32 bits es 2,147,483,647 que es el valor 2^31-1 (el exponente es no es 32 porque hay que usar uno de los bits para el signo del número). Esto quiere decir que si se suman 2 valores positivos y el resultado es un número negativo es porque la suma requiere más de 32 bits, como ocurre con estos ejemplos:

public void test_dosAla() { // dosAla(n) == 2^n
    assertTrue(  dosAla(0) == 1 && dosAla(3) == 8 ); // Ok
    assertTrue(  dosAla(30) ==   1073741824 );

    assertTrue(  dosAla(31) == 2*1073741824 ); // Ok
    assertTrue(  dosAla(31) ==  -2147483648 ); // ??????  [[1]]

    assertTrue( 2*dosAla(30) == -2147483648 );         // !!!!!!
    assertFalse( dosAla(30)+dosAla(30) > dosAla(30) ); // ??????  [[2]]
}

Al sumar el valor 1,073,741,824 consigo mismo, el resultado 2,147,483,648 sobrepasa en 1 el máximo valor que puede almacenarse en una variable entera: 2,147,483,647. Por eso, en lugar de obtener un resultado positivo, esta multiplicación queda como un número negativo.

Una forma de detectar si el resultado de una suma de 2 valores positivos ya no cabe en la variable entera es verificar si el resultado obtenido es un número negativo, como ocurre en el renglón marcado [[1]]. Otra es verificar si el resultado de la suma es menor que los valores originales, como ocurre en el renglón marcada [[2]].

En esta tarea programada usted debe hacer un programa que busque la primera pareja de números que tiene la propiedad de que, al sumarla, produce un resultado incorrecto porque se rebasa el límite de 32 bits para números enteros. Su programa debe probar todas las parejas de números que corresponden a un racional en el orden antes descrito para contar racionales (si lo desea, puede usar el orden de la figura que es un poco más complicado de programar).

Su programa rebase.java debe usar los métodos de la clase biblio para grabar en pantalla las primeras parejas de números cuyo suma, resta o multiplicación se sale de 8 bits, pues ese es el tamaño de una variable Java de tipo (byte). Use al técnica descrita en el Lab12.java para obtener la cantidad de valores que si programa debe reportar. Además, reporte primero las sumas, luego las restas y por últimos las multiplicaciones en renglones aparte que no sobrepasen 80 caracteres. Debido a que su programa usa el orden que permite contar números racionales, debe procesar las parejas de valores en ese mismo orden.

/** Contiene rutinas para verificar si las operaciones aritméticas
    producen o no rebase numérico. */
class biblio {
    /** Retorna true si la suma a+b si cabe en una variable entera. */
    public static boolean addIsSafe(byte a, byte b) {
        byte res=a; res += b;
        if (a != res-b) { return false; }
        return true;
    }
    // http://google.com/search?as_qdr=all&num=100&as_q=java+detect+integer+overflow

    /** Retorna true si la resta a-b si cabe en una variable entera. */
    public static boolean subIsSafe(byte a, byte b) {
        byte res=a; res -= b;
        if (a != res + b) { return false; }
        return true;
    }

    /** Retorna true si la multiplicación a*b si cabe en una variable entera. */
    public static boolean multIsSafe( byte a , byte b ) {
        byte res=a; res *= b;
        if (a!=0) if (res/a != b) { return false; }
        return true;
    }

    /** Retorna true si la división a/b si cabe en una variable entera. */
    public static boolean divIsSafe( byte a , byte b ) {
        return true;
    }
}

Consulta:

Profe: Podría detallar un poco mas como realizar la tarea programada :) Se lo agradezco.

Respuesta:

Los primero que tenés que lograr es que tu programa produzca todas las parejas de números. Los primeros sesenta son estos: (1/1) (1/2) (2/1) (1/3) (2/2) (3/1) (1/4) (2/3) (3/2) (4/1) (1/5) (2/4) (3/3) (4/2) (5/1) (1/6) (2/5) (3/4) (4/3) (5/2) (6/1) (1/7) (2/6) (3/5) (4/4) (5/3) (6/2) (7/1) (1/8) (2/7) (3/6) (4/5) (5/4) (6/3) (7/2) (8/1) (1/9) (2/8) (3/7) (4/6) (5/5) (6/4) (7/3) (8/2) (9/1) (1/10) (2/9) (3/8) (4/7) (5/6) (6/5) (7/4) (8/3) (9/2) (10/1) (1/11) (2/10) (3/9) (4/8) (5/7) (6/6) (7/5) (8/4) (9/3). Luego, le podés aplicar a cada una de esas parejas los métodos para determinar si las operaciones aritméticas con esos 2 operandos producen o no rebase numérico.

Consulta:

Profe: Me parece que cuando ya se llega al (1/127) y luego al (127/1) no se puede continuar con (128/1) porque ya 128 no cabe en un (byte). ¿Qué hacemos?

Respuesta:

Efectivamente, ya no pueden comenzar con (1/128) pero sí con (2/127). Luego seguirán con (3/126) hasta que, finalmente paren en (127/127).

PUNTOS EXTRA: Lo interesante de la tarea es que, para implementarla, no hay que usar multiplicaciones pues al recorrer las parejas de números usando el diagrama de diagonalización que está arriba, se puede generar el resultado de la multiplicación con base en los valores ya calculados.

Entrega de Tareas

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2012
Derechos de autor reservados © 2012