PDF de programación - calculos con números enteros grandes en ordenadores

Cálculos con números enteros grandes en ordenadores.

Aladár Péter Sántha


Haciendo cálculos con lápiz y papel, el tamaño de los operandos está limitado
solamente por el tamaño del papel y por el tiempo disponible. Cuando los cálculos se
hacen con un ordenador, además de la cantidad de memoria y el factor tiempo, hay que
tener en cuenta que las variables de precisión doble pueden almacenar 2p cifras.
. Un número con más de 2p cifras se presentará en
Normalmente, tenemos
punto flotante. Esto significa que conoceremos solamente las primeras
cifras del
resultado puesto que la cifra que ocupa el lugar 2p ya está afectada por el redondeo. Por
otra parte, las dificultades empiezan ya al introducir los operandos en el ordenador. Al
intentar introducir un operando de más de 2p cifras en una variable numérica de
precisión doble, el resultado será almacenado en punto flotante, perdiendo las últimas
cifras. Así pues, haciendo operaciones con números grandes, los operandos deberán ser
introducidos en variables alfanuméricas (de tipo string), que pueden recibir números
largos. El número de las cifras de un número que se puede introducir en una variable de
tipo alfanumérico está limitado únicamente por la memoria disponible en el ordenador.
Haciendo cálculos con números grandes, los operandos deberán ser divididos en
bloques. El tamaño de los bloques depende de las operaciones a efectuar. El resultado
de la operación entre los números situados en dos bloques se almacenará en una
variable de doble precisión y así, para sumas, restas y divisiones euclideas, el número de
. En el caso de las
las cifras por bloque no tiene que ser mayor a
multiplicaciones, el número de las cifras por bloque no debe superar las

cifras.
Cuando se efectúan todo tipo de operaciones, es conveniente que el número de cifras
por bloque sea siempre el mismo, menor o igual a
Ejemplo 1: Para sumar los números

, los números se dividirán en bloques de 8 cifras. La formación de los bloques se hará
desde la extremidad derecha de cada número, hacia la izquierda. Dado que las
calculadoras de bolsillo exponen 10 cifras, los cálculos de este ejemplo se pueden seguir
con éstas calculadoras.

y

.

,



Sumando los bloques que ocupan el mismo lugar, se obtienen los números

, donde el último número no es un bloque de 8 cifras. Separando la cifra 1 del número
184874454 se obtiene el arrastre 1 que se sumará al bloque siguiente
. Así,
se obtienen los bloques:



, y uniendo los bloques, resulta que:



Ejemplo 2: Para calcular la diferencia de los números
y

, los números A y B se dividirán en bloques de 8 cifras:



162p12p12pn2/)22(pn2/)22(pn 76561237874386679245045 A05974356892945629973 B87438765045612376679245 A 97435689629973052945 B184874454675585426682190 675585428487445467558543668219045458543848746682190675 BA88795761523745898763334A6783618765896875869B



Restando de los bloques de A los bloques de B que ocupan el mismo lugar, se obtienen
los números:



Para hallar los bloques de A - B hay que sumar 108 a -25986989 y restar 1 del número
-35262935, luego, hay que repetir lo mismo para los primeros dos números. Así, A-B se
obtiene por el camino siguiente:



Para hallar B-A, los cálculos se harían de la misma manera, cambiando previamente el
primer operando con el segundo, luego el resultado tendrá el signo menos.
En el caso de la suma algebraica de dos enteros, es conveniente separar los signos de los
números desde el principio y operar con los valores absolutos, de acuerdo con las reglas
siguientes:
Si los dos números tienen el mismo signo, se suman los valores absolutos y a esta suma
se le asigna el signo común de los operandos.
Si los dos números son de signos distintos, pero no son opuestos, del número de mayor
valor absoluto se resta el otro y el resultado tendrá el signo del número de mayor valor
absoluto.
Si los números son opuestos, el resultado es cero.
Teniendo en cuenta que en un programa de ordenador los valores absolutos de los
números aparecerán en campos alfanuméricos, la comparación de los valores absolutos
se hará según las reglas siguientes: Si A$ y B$ son los campos alfanuméricos que
contienen los números A y B, respectivamente, y la longitud del campo A$ es mayor
que la del campo B$, entonces A>B. Si los campos A$ y B$ tienen la misma longitud,
A>B si y solamente si A$>B$. Recordamos que la comparación de A$ y B$ se hace
comparando sucesivamente las cifras que ocupan la misma posición en las dos
variables, de izquierda a la derecha. Al encontrar las primeras dos cifras distintas, el
campo mayor será aquello que contiene el mayor de estas dos cifras. Evidentemente, si
todas las cifras, que ocupan posiciones idénticas, coinciden, los dos campos son iguales.
, se dividen estos números en
Para multiplicar los números
bloques de dos cifras:
.

y

y

Entonces,
, y multiplicando todos los sumandos de A con los sumandos de B, sucesivamente,
resulta que

y



+



…



(1)

5237488733495761 5898763 A7836187668758696589B25986989- 35262935- 589817474013011352629365898174740130113526293558981747401301164737065589817301137065740135898173647B-A52317A15341245B17235A45123415B42105102317A64210151034101245B246241020410276106076510103510225BA681046810255103451075105781078210170642642102601027610410210102510735651046108641037510245105510110770105821078642105558226021078276102510473565BA10810375110245770


Por otra parte, multiplicando los bloques del número B, empezando con el bloque 45,
con cada bloque del número A, se obtienen bloques de 4 cifras que, divididos en
bloques de dos cifras, se colocarán en la tabla 1 Por ejemplo, al multiplicar el bloque 45
con el bloque 17 se obtiene el bloque de 4 cifras 0765 que se divide luego en los
bloques de dos cifras 07 y 65. El bloque 65 se coloca en la esquina superior derecha de
un cuadradito, mientras que el bloque 07 será situado en la esquina inferior izquierda
del mismo cuadradito. Los bloques que se obtienen al multiplicar el bloque 45 con los
bloques 17, 23, 05 se colocarán en la primera fila de la tabla, de derecha a la izquierda.
Luego, repitiendo lo mismo con los otros bloques de B, se obtienen las otras filas de la
tabla.
Mirando la tabla 1, se puede ver que los coeficientes de las potencias 100, 102, 104, 106,
108,1010 y 1012 en la expresión (1) del producto
son exactamente las sumas de
aquellos números de la tabla 1 que se encuentran sobre las rectas

se ponen las sumas de los números
y
que se encuentran en estas líneas.
Finalmente, por debajo de estos números aparecen los bloques del producto


. Al pie de la tabla y en las líneas

.

,

,

,

,

,



Así,
Haciendo los cálculos con un ordenador, hay que tener en cuenta que un elemento de
una tabla no puede contener dos números.
Por esta razón, en un programa de ordenador se definirá una tabla tridimensional A de
las dimensiones
. El piso bajo de esta tabla está formado por aquellos números
que se encuentran en las esquinas superiores de los elementos de la tabla (1), mientras
qué el piso superior está formado por los números que se sitúan en las esquinas
inferiores.



BA'aa'bb'cc'ee'kk'gg'aa,'bbBA658026079146BA2,3,42576020210356560070200027082780107057545550003021247920619146656546910726801Tablaabcdek'a'b'c'k'e'd


25

35

65

60

70

75

76

04

82

78

45

55



02

10

07

00

02

02

01

07

05

00

03

02



Piso bajo Piso superior



Así los elementos del piso bajo y del piso superior de A son
respectivamente, donde
tabla 1, que se encuentran sobre las líneas


y

,
. Por tanto, las sumas de los números de la

y

son:



.



Obviamente, el mismo producto se podría calcular formando bloques con más cifras.
Por ejemplo, si se forman bloques de 3 cifras, los cálculos son los siguientes:

;



, como en el caso anterior.

, y así

Ejemplo 3: Si A = 547888431678967 y B = 99345687652349, los números sean
divididos en bloques de longitud 5


;



1,,jiA2,,jiA41i31j'',',',',','ggyffeeddccbbaa1,3,1A2,3,11,3,21,2,1AAA2,3,22,2,11,3,31,2,21,1,1AAAAA2,3,32,2,22,1,11,3,41,2,31,1,2AAAAAA2,3,42,2,32,1,21,4,21,3,1AAAAA2,4,22,3,11,4,1AAA2,4,1A31752A24534115B658026079146BA789678431654788A52349568769934B2Tabla74066512777320971710878075546656659149141607607801802



.

, y así
La división euclidea de dos números naturales se reduce a una sucesión de restas, de
fácil programación. No obstante, la duración de una división euclidea es bastante
superior al tiempo necesario para efectuar a una suma o a una multiplicación.
El método expuesto para efectuar las operaciones con números naturales grandes,
dividiéndoles en bloques, se conoce ya desde hace mucho tiempo pero el autor de este
escrito no pudo averiguar de quien fue la idea. A continuación se exponen las funciones
necesarias en el lenguaje VISUAL-BASIC, para efectuar operaciones con números
enteros grandes. Par