[C con Clase] Ayuda con programa tengo error

[Steven Davidson]

Hola José Luis,

2011/9/27 jose luis <jcmdustin en gmail.com>:
>
> SD> >
> SD> El problema es que usas 'int', que seguramente ocupa 32 bits en tu
> SD> máquina. De estos 32 bits, el más significativo representa el signo: 1
> SD> es negativo y 0 es positivo. Esto significa que el intervalo de
> SD> valores representados por 'int' es el siguiente:
> SD> [-2147483648,+2147483647].
>
> gracias steven, tengo otra duda más, como se que signo se le asigna al numero?
> o como puedo determinarlo??
>

Eso se puede averiguar con matemáticas:

x > 0  =>  "x" es positivo => "x" tiene un signo positivo
x < 0  =>  "x" es negativo => "x" tiene un signo negativo

En el caso de la representación interna de un número entero que
expliqué antes, podemos usar operaciones a nivel de bit para averiguar
si ese bit del signo (negativo) está activado (1) o no (0). Para ello,
usamos la operación AND para consultar el valor guardado en ese 32º
bit. Usando un tipo 'int' de 32 bits, haríamos algo así,

int mascara = 1 << 31;
int numero;
...
if( numero & mascara )
  cout << numero << " es negativo" << endl;
else
  cout << numero << " es positivo (o cero)" << endl;

Claro que si usas 'unsigned int', no obtendrás un número negativo.

> SD> mano a otras bibliotecas que manejen números grandes. Claro que nadie
> SD> te detiene para que los crees tú mismo :)
>
> me podrias dar al guna idea para poder crear una biblioteca que maneje numeros grandes¿?
>

Como básicamente vas a crear un nuevo tipo de dato, la idea general es
la de definir un tipo de dato. Esto implica que deberás definir a) la
representación de los datos y b) las operaciones aritméticas válidas
para tratar este tipo de dato.

Para la representación interna, podrías usar un array de enteros para
representar la secuencia de dígitos decimales. Por ejmeplo,

struct gigante
{
  unsigned char numero[10240];  // 10 KB
  unsigned int nCantDigitos;
  bool bNegativo;  // Representa el signo negativo (true) o positivo (false)
};

Si quieres que este tipo sea dinámico y que se ajuste a cualquier
cantidad de dígitos, entonces te interesa usar memoria dinámicamente
adjudicada. Por ejemplo,

struct gigante
{
  unsigned char *pNumero;  // Array dinámico de dígitos (como 'unsigned char')
  unsigned int nCantDigitos;
  bool bNegativo;
};

Y luego, tendrías que hacer algo así,

gigante num;

num.nCantDigitos = 10240;
num.pNumero = new unsigned char[num.nCantDigitos];
num.bNegativo = false;

Claro está, al realizar las operaciones aritméticas, nos damos cuenta
que el procesador tardará lo mismo en sumar dos enteros de 1 dígito
que dos enteros de 4 dígitos. Así que vamos a usar arrays de 4 dígitos
agrupados en un 'int' en lugar de grupos de 1 dígito de tipo 'unsigned
char'. Esto es,

struct gigante
{
  int *pNumero;  // Array dinámico de 4 dígitos (como 'int')
  unsigned int nCantDigitos;
  bool bNegativo;  // Representa el signo negativo (true) o positivo (false)
};

El problema de usar arrays dinámicos es que vamos a tener problemas de
gestión de memoria si queremos agrandar o reducir la cantidad de
elementos (grupos de 4 dígitos) en el array dinámico. Además, si
usamos mucha memoria, va a resultar difícil encontrar bloques de
memoria contigua. Cuando veas las operaciones, te darás cuenta que a
veces te interesa agregar información en el medio del array, cosa que
no es tan fácil con los arrays requiriendo más gestión cuidadosa.

Lo ideal es que usemos una lista dinámicamente enlazada o incluso
mejor, una lista doblemente enlazada. Así vamos creando la memoria que
necesitemos sin forzar a que sea contigua. Podemos eliminar partes de
la lista independientemente del resto de la lista. Además, podemos
agregar nuevos elementos donde queramos, sin mucha preocupación. Algo
así,

struct gigante_nodo
{
  int digitos;
  gigante_nodo *pSig, *pAnt;
};

struct gigante_lista
{
  gigante_nodo *pCabeza, *pUltimo;  // Este último puntero es una
optimización: para ir rápidamente al último nodo
  unsigned int nCantNodos;
};

struct gigante
{
  gigante_lista lista;  // La lista doblemente enlazada
  bool bNegativo;  // Representa el signo negativo (true) o positivo (false)
};

El problema es que al representar grupos de 4 dígitos, es posible que
algunos nodos contengan enteros de menos de 4 dígitos. Por ejemplo,

[102] [49] [0] [13]

Esto representaría el siguiente número entero:

102004900000013

Hay que tener en cuenta esos 0's de más, aunque internamente sólo se
guarde un entero de menos de 4 dígitos, como por ejemplo un 0 (cero).


Se implementarán las 5 operaciones aritméticas básicas: suma, resta,
multiplicación, división, y exponenciación (el exponente será un
'unsigned int'). Los algoritmos de las 4 primeras operaciones se basan
en los algoritmos que nos enseñaron a todos en la escuela. La
diferencia es que no sumamos los dígitos, sino grupos de 4 dígitos; es
decir, de 0 á 9999. Por ejemplo,

      [102]   [49]       [0]      [8]
+  [9955]     [0] [1130]  [999]
-------------------------------------
[1]    [57]   [49] [1131]      [7]

Como puedes ver, hay que tener en cuenta el acarreo al sumar (y al
restar). También puedes observar que tuvimos que agregar un nuevo nodo
al principio de la lista resultante. Por último, hay que tener en
cuenta el signo de cada operando en las operaciones aritméticas.

La multiplicación es una suma de productos de un nodo de un
multiplicando por cada nodo del otro multiplicando.

Podríamos definir la división de la inversa de la multiplicación: una
serie de restas. Pero es más rápido si aplicamos la misma estrategia
que nos enseñaron en el colegio: adivinar el cociente e ir probando y
refinando nuestra respuesta. Esto es un poco más complicado, pero en
general, da buenos resultados.

Para la exponenciación, no uses el algoritmo trivial de ir
multiplicando la base por sí misma y acumulando el resultado. Existe
un mejor algoritmo que se basa en ir cuadrando la base, según la
secuencia binaria del exponente. Te doy un ejemplo,
    20
10

Miramos el exponente en binario:

20 = 10100

Ahora vamos cuadrando la base (10, en este ejemplo) y acumulándolo en
cada iteración. Sin embargo, sólo acumulamos la respuesta en el
resultado si el bit del exponente de esta iteración es un 1. Por
ejemplo,

#     Bit    Cuadrados                      Respuesta
---------------------------------------------------------------------------------
0     ----  1                                       1
1      0    10                                     1
2      0    100                                   1
3      1    10000                               10000
4      0    100000000                       10000
5      1    10000000000000000       100000000000000000000

La respuesta final es:  100000000000000000000 = 10^20

Como puedes ver, en 5 iteraciones obtenemos el resultado usando este
algoritmo, mientras que con el algoritmo trivial de ir multiplicando
tantas veces como indique el exponente, acabaríamos realizando 20
iteraciones. Esto es una gran mejora :)

Por cierto, tuve que hacer todo esto como proyecto en una clase de
algoritmia en mi universidad; pero de eso hace muchos años :D  y me
temo que perdí el código fuente.


Para el tema de las listas doblemente enlazadas, consulta el capítulo
5 de nuestro curso de EDD en nuestra página yendo a:
http://c.conclase.net/edd/index.php?cap=005#inicio


Espero que todo esto te oriente.

Steven