PROYECTO FIN DE CARRERA

Autor:

Director:

Escuela Técnica Superior deIngenieros Informáticos

Universidad Politécnica de Madrid

Ingeniería en Informática

MADRID, JULIO 2018

Biblioteca denúmeros grandes en C++

José Osvaldo Suárez Domingos

Fernando Pérez Costoya

Indice

1. Introduccion 21.1. Motivacion y origen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2. Estado de la cuestion 3

3. Implementacion 63.1. Lenguaje a usar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.2. Representacion de los numeros . . . . . . . . . . . . . . . . . . . . . . . . 63.3. Estructura en memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.4. Sumador basico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.5. Suma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.6. Resta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.7. Opuesto, incremento y decremento en 1 . . . . . . . . . . . . . . . . . . . 163.8. Multiplicador basico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.9. Multiplicacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.9.1. Multiplicacion clasica . . . . . . . . . . . . . . . . . . . . . . . . . 203.9.2. Multiplicacion de Karatsuba . . . . . . . . . . . . . . . . . . . . . 22

3.10. Division y modulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.10.1. Division larga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.10.2. Division larga en bloques . . . . . . . . . . . . . . . . . . . . . . . 25

3.11. Imprimir los numeros en decimal . . . . . . . . . . . . . . . . . . . . . . . 283.11.1. Algoritmo simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.11.2. Algoritmo “divide y venceras” . . . . . . . . . . . . . . . . . . . . 28

3.12. Otras operaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4. Pruebas y resultados 31

5. Conclusiones y lıneas futuras 35

1

1. Introduccion

La aritmetica de numeros grandes, tambien llamada aritmetica de precision arbitra-ria o multiple precision, es la realizacion de operaciones aritmeticas en un computador(tanto de numeros enteros como fraccionarios) con tamanos de operandos mayores que eltamano de palabra de este. Los datos manejados tıpicamente por computadores oscilanentre 8 y 64 bits de precision, y sus unidades aritmetico-logicas (por sus siglas en ingles,ALU) son, en general, capaces de operar con estos tamanos en un solo paso. Varios len-guajes de programacion (Lisp, Python, Perl, Haskell, Ruby) tienen soporte nativo paranumeros grandes que implementan mediante vectores de longitud variable [1].

Un uso muy comun de los numeros grandes es la criptografıa de clave asimetrica,cuyos algoritmos emplean numeros de cientos o miles de bits. Por ejemplo, 1024, 2048 o4096 bits son valores tıpicos en el tamano de clave del algoritmo criptografico RSA. Sibien estas longitudes de clave de miles de bits no son obligatorias (el algoritmo puedetrabajar con cualquier tamano), en la practica son necesarias para evitar ataques defuerza bruta. Otros usos comunes son los calculos financieros, el estudio numerico defunciones matematicas cuando los metodos analıticos no son viables (por ejemplo: lafuncion zeta de Riemann), o la simulacion y prediccion de sucesos fısicos (por ejemplo:el seguimiento de partıculas en el acelerador “LHC” [2]).

1.1. Motivacion y origen

Experimentando con un algoritmo para prediccion de resultados deportivos me en-contre con un sistema de ecuaciones mal condicionado y pense en usar numeros de comaflotante con precision mayor que doble o cuadruple bits (el compilador GCC implementamediante software un tipo de coma flotante de 128 bits float128). Aunque sabıa dealgunas bibliotecas de numeros grandes decidı que querıa hacer una para probar si podıasuperar a las existentes y que se adaptase a mi gusto [3].

1.2. Objetivos

Desarrollar una biblioteca para manejo de numeros grandes en C++ que cumplaestos requisitos:

- Facil de usar. Mediante la sobrecarga de operadores que permite el lenguaje lasustitucion de un tipo de enteros generico por esta implementacion deberıa ser lomas directa posible.

- Razonablemente rapido. La velocidad de ejecucion tiene dos vertientes, por unlado la complejidad computacional y por otro, dado un algoritmo, el optimo apro-vechamiento de los recursos. Desde el punto de vista academico es mas importantela primera, ası que no deberıan faltar algoritmos mas eficientes que las versionesclasicas alla donde sea posible.

- Que sirva como base para implementar coma fija y coma flotante. Ambos conceptosimplican que el numero de bits de cualquier numero es fijo.

2

2. Estado de la cuestion

Existen varias implementaciones de numeros grandes, cada una con sus particulari-dades [4]:

• Boost

- Lenguajes soportados: C++

- Licencia: Boost

- Tipos de numeros: enteros, racionales, coma flotante.

- Es un conjunto de mas de 80 bibliotecas para diversas tareas como, ademasde numeros de gran tamano, procesamiento de imagenes, manejo de sockets,expresiones regulares, multihilo, etc., por lo que llega a ser una dependenciapesada y, a menos que ya se este usando por sus otras opciones, podrıa serpreferible usar otra biblioteca para el manejo de numeros grandes. Usa pordebajo GMP/MPFR [5].

• TTMath

- Lenguajes soportados: C++

- Licencia: BSD

- Tipos de numeros: enteros, coma flotante.

- Biblioteca basada unicamente en plantillas de C++. El tamano de los numerosse establece en tiempo de compilacion, y es fijo en memoria, lo que hace quese manejen en la pila de ejecucion. Las operaciones basicas se realizan con losalgoritmos basicos bien conocidos. Soporta las arquitecturas x86 y x86-64 [6].

• GMP / MPFR

- Lenguajes soportados: C, C++, Ada, Perl, Python, ...

- Licencia: GPL2 / LGPL3

- Tipos de numeros: enteros, racionales, coma flotante.

- La biblioteca de precision multiple de GNU esta nativamente en lenguaje C ytiene interfaces para varios otros lenguajes. Para lograr una gran velocidad deejecucion toma ciertas decisiones de diseno: los numeros estan formados porpalabras del tamano maximo de la maquina, se usan distintos algoritmos parala misma operacion dependiendo del tamano de los numeros involucrados, y seusa codigo ensamblador para las zonas “calientes” del codigo [7]. Implementael algoritmo de multiplicacion Schonhage-Strassen [8], mas eficiente en ciertoscasos que el algoritmo clasico de la escuela o el de Karatsuba y un algoritmode division mediante la tecnica de “divide y venceras” [9].

3

• CLN

- Lenguajes soportados: C++

- Licencia: GPL2

- Tipos de numeros: enteros, racionales, coma flotante, complejos.

- Usa algunas optimizaciones como alojar enteros pequenos en la pila en vez deen la memoria dinamica. Tambien implementa el algoritmo de multiplicacionSchonhage-Strassen [10].

• ARPREC

- Lenguajes soportados: C++, Fortran 90

- Licencia: LBNL-BSD

- Tipos de numeros: enteros, coma flotante, complejos.

- Esta biblioteca toma una decision de diseno que limita su uso, al establecerla precision de los numeros mediante una variable global. Esto hace que no sepuedan mezclar operaciones de distinta precision. Los numeros se alojan enmemoria dinamica [11].

• MAPM

- Lenguajes soportados: C, C++

- Licencia: Dominio publico.

- Tipos de numeros: Enteros, coma flotante.

- La biblioteca tiene un uso de memoria poco eficiente; los numeros requierenuna estructura que ocupa 36 bytes en 64 bits, la cual se aloja en memoriadinamica. A esto se anade el propio numero que requiere otra reserva dememoria dinamica [12].

• MPIR

- Lenguajes soportados: C, C++, Ada, Perl, Python, ...

- Licencia: LGPL3

- Tipos de numeros: enteros, racionales, coma flotante.

- Es un trabajo derivado de la biblioteca de numeros grandes de GNU (GMP),por tanto comparte varias caracterısticas de diseno con GMP. Ademas demantener compatibilidad con este, su objetivo principal es desarrollar algo-ritmos paralelos que ejecuten en procesadores graficos y procesadores mul-tinucleo [13].

4

• libgcrypt

- Lenguajes soportados: C

- Licencia: LGPL. Algunos ficheros tienen otra licencia como BSD3, GPL, yvarias mas, aunque todas ellas parecen ser “Open Source”.

- Tipos de numeros: enteros.

- Es una biblioteca criptografica que implementa sus propios numeros grandes,con codigo ensamblador para gran variedad de procesadores: Alpha, AMD64,HP PA-RISC, i386, i586, M68K, MIPS 3, PowerPC, y SPARC [14].

• LibTomMath

- Lenguajes soportados: C

- Licencia: Dominio publico o WTFPL

- Tipos de numeros: enteros.

- Comenzo como un necesario reemplazo de la biblioteca MPI, parte de libgcrypt.Esta escrita de forma didactica.

• C++ BigInt Class

- Lenguajes soportados: C++

- Licencia: GPL2

- Tipos de numeros: enteros.

- El desarrollo de esta biblioteca comenzo en 1995. Representa los numeroscomo un vector de tamano variable. Opera con algoritmos sencillos.

Otras bibliotecas son: mbed TLS, JScience, JAS, JLinAlg, Apfloat, InfInt, bigz, ramp,float, fgmp, OpenSSL.

5

3. Implementacion

3.1. Lenguaje a usar

Al comenzar a implementar una biblioteca de numeros grandes surgen inevitable-mente cuestiones de diseno; la primera es elegir el lenguaje de programacion. He elegidoC++ porque lo uso habitualmente para mis proyectos personales. Sus caracterısticasgenerales son: es un lenguaje de proposito general, se basa en el paradigma imperativo,esta orientado a objetos, permite programacion generica (con plantillas) y permite elacceso a bajo nivel a la manipulacion de memoria [13]. Pero, mas concretamente, lascaracterısticas que me interesan son:

- Permite el manejo del computador a bajo nivel, pudiendo insertar codigo ensam-blador, que no solo puede ser util para exprimir un poco mas el rendimiento delprocesador, sino para salvar algunas limitaciones de C++. En concreto, el opera-dor de suma no dispone de ningun mecanismo para detectar un posible acarreo,de forma que habrıa que emular este comportamiento usando mas instrucciones delas que serıan necesarias en una arquitectura que implemente la suma con acarreo(¿hay alguna que no lo haga?). Asimismo, el operador de multiplicacion tambiencarece de acceso a la parte alta del resultado. Hay que recordar que una multi-plicacion de dos numeros de N bits da como resultado un numero de 2N bits.Estas limitaciones se pueden evitar insertando codigo ensamblador especıfico pa-ra cada arquitectura, conservando, eso sı, una implementacion en C++ puro masineficiente pero portable.

- Es un lenguaje muy usado, y esto hace que existan compiladores para muchasarquitecturas, lo que hace que C++ sea un lenguaje muy portable. Concretamente,el compilador que se usara principalmente en este proyecto, GNU GCC, admitedecenas de arquitecturas [15]. Estos compiladores son, en general, bastante buenosoptimizando.

- El uso de plantillas permite que algunos parametros del manejo de los numerossea conocido en tiempo de compilacion, lo que lleva a mejores posibilidades deoptimizacion.

- Permite la sobrecarga de operadores, haciendo que la interfaz de los numeros gran-des sea identica a la de los tipos predefinidos. Gracias a esto se podra reutilizar elcodigo existente con cambios mınimos.

3.2. Representacion de los numeros

Si bien existen implementaciones de numeros grandes usando cadenas de caracteres,su rendimiento es pobre y el uso de memoria ineficiente. Una implementacion solventepasa por usar la representacion nativa de los computadores modernos: binario. La di-ferencia en espacio es clara, un dıgito decimal ocupa 8 bits como caracter imprimible,

6

mientras que el mismo dıgito decimal ocupa en binario log2(10) ∼ 3,32 bits, y en veloci-dad de ejecucion mayor si cabe; un procesador de 64 bits puede sumar dos numeros deese tamano en 1 ciclo de reloj, que representado en decimal son log10(2) ·64 ∼ 19,3 cifras,llevando a esperar que tal operacion precisara de decenas de ciclos para completarse sisu representacion fuera en forma de cadena de caracteres decimales.

Usaremos, pues, vectores del maximo tamano de palabra que permita el computador,o mejor dicho, que permita C++. En principio los numeros que vamos a representar coneste formato son enteros sin signo, aunque posteriormente sea posible usar este mismoesquema con enteros con signo representando los numeros negativos en complementoa 2[complemento˙a˙dos.] Afortunadamente existen definiciones estandar de tipos dedatos numericos para 8, 16, 32 y 64 bits, con signo (int8 t, int16 t, int32 t, int64 t) ysin signo (uint8 t, uint16 t, uint32 t, uint64 t), de los que nos interesan los numerossin signo. En las arquitecturas con tamanos de palabra menores de 64 bits el compiladorgenerara el codigo que emule las operaciones con estos numeros mas grandes, que es,curiosamente, algo semejante a lo que queremos que haga la biblioteca.

Cuando los procesadores almacenan en la memoria principal los registros mayoresque un byte usan varias formas distintas respecto al orden de los bytes. Las mas usadasson: big endian 1 y little endian 2 (aunque otras aberraciones son tambien posibles [16]).

31 07815162324

Byte 3 Byte 2 Byte 1 Byte 0

Byte 3 Byte 2 Byte 1 Byte 0

0 N - 1

En registro

En memoria

Figura 1: Representacion de un dato de 32 bits que se transfiere de unregistro a la memoria principal usando una representacion big endian

31 07815162324

Byte 3 Byte 2 Byte 1 Byte 0

Byte 0 Byte 1 Byte 2 Byte 3

0 N - 1

En r er giso

En iemsatig

Figura 2: Representacion de un dato de 32 bits que se transfiere deun registro a la memoria principal usando una representacion little

endian

7

El orden mas usado actualmente es little endian, por ser usado en ordenadores per-sonales, con la arquitectura x86, y dispositivos portatiles con la arquitectura ARM. Losprocesadores ARM son capaces de usar ambos ordenamientos, a pesar de lo cual losdisenadores de computadores se adhieren masivamente al little endian. Aunque la formaen la que el computador almacena los palabras en memoria es de poca relevancia, laforma de almacenar las partes de un numero grande en un vector de palabras esta sujetoa las mismas consideraciones, ¿big endian o little endian?. Debemos tener en cuenta quelas operaciones de suma/resta y multiplicacion recorren los numeros desde los dıgitosmas bajos hasta los mas altos. Esto por si mismo no implicarıa una eleccion del orden,pero por otro lado los procesadores a menudo tienen mecanismos (stream buffers [17])para predecir los accesos en secuencia a la memoria principal y precargarla en buffers deacceso rapido con el fin de evitar paradas en la ejecucion. Los stream buffers, ademas,suelen detectar el patron secuencial solo hacia direcciones crecientes, y no hacia las de-crecientes. Si por ultimo anadimos que el codigo resultara mas sencillo si se recorren losbucles hacia adelante (de 0 a N − 1) que hacia atras (de N − 1 a 0), el ganador es littleendian.

H 1000

H 1004

H 1008

H 100C

H 1010

H 1014

H 1018

H 101C

H 1020

H 1024

Memoria principal Direcciones

Palabra 0

Palabra 1

Palabra 2

Palabra 3

Palabra 4

Palabra 5

Inicio

Figura 3: Representacion de un numero de 192 bits en la memoriaprincipal almacenado en little endian formado por 6 palabras de 32

bits

8

Hay otra razon menos importante para almacenar las palabras del vector en littleendian; si quisieramos optar por un vector de, por ejemplo, 32 bits, y lo almacenasemosen big endian, pero con el ordenamiento de los bytes (impuesto por la arquitectura) enlittle endian, su representacion en memoria serıa distinta a la que tendrıa si las palabrasfueran de, por ejemplo, 64 bits. Se tratarıa de dos variaciones posibles del concepto demiddle endian.

3.3. Estructura en memoria

Mas alla del ordenamiento de las palabras, las posibles estructuras de los numerosen memoria se pueden resumir en dos: tamano variable (o dinamico) y tamano fijo (oestatico). Cada uno tiene sus ventajas y desventajas.

En general el tamano variable parece mas ventajoso cuanto mayores son los numerosmanejados porque aprovecha mejor la memoria al usar solo la mınima necesaria paracada numero. Esto es una verdad a medias: a los numeros se accede a traves de punteros,de forma que se consume la memoria del numero, la memoria de un puntero a este y lamemoria de un dato que indique el tamano del numero (esta ultima podrıa almacenarsejunto al propio numero). De esta forma, mientras que un numero de tamano fijo puededesperdiciar mucho espacio en forma de “ceros por la izquierda”, con tamano variableno sucede.

El diseno de tamano variable permite que cualquier numero crezca sin mas restric-ciones que la memoria del sistema, sin embargo el diseno de tamano fijo requiere queese tamano sea conocido en el momento de compilar, es decir, debera estar indicadoexplıcitamente en el codigo fuente. Ası, la coexistencia de muchos numeros de tamanofijo durante la ejecucion del programa implica que todos ellos usan el tamano maximoque se espera que alcance alguno de ellos.

Los numeros de tamano variable se almacenarıan una parte en la pila de ejecucion(el puntero y tal vez el tamano) y otra en el montıculo o heap. Las operaciones contamano variable dan lugar a resultados de tamanos diversos, requiriendo la continuareserva y desalojo de fragmentos de memoria, lo que podrıa producir fragmentacion; lasoperaciones con tamano fijo no sufren este problema y tienen una bonificacion anadidarespecto al uso de la memoria cache del procesador: ofrecen mejor localidad espacial alevitar una indireccion para acceder al vector.

Para implementar por software otros numeros como el estandar IEEE-754 [18] o lacoma fija puede resultar conveniente el tamano fijo.

9

Este serıa un ejemplo del tipo de datos para tamano variable (dinamico):

struct big_uint

{

// Puntero al vector de bloques.

uint64_t * vec;

// Numero de bloques actuales.

unsigned int length;

};

Y este serıa un ejemplo para tamano fijo (estatico):

template <unsigned int Length >

struct big_uint

{

// Vector de bloques.

uint64_t vec[Length ];

};

Es resenable que el tamano estatico usa un parametro de plantilla que permite ins-tanciar numeros de distintos tamanos.

10

Tras valorar estas cuestiones la estructura escogida ha sido el tamano fijo. Aquı semuestra el tipo de datos usado sin incluir los metodos de clase:

template <unsigned int Precision = 128,

typename Base_Type = uint64_t >

class big_uint

{

public:

static const unsigned int precision = Precision;

using base_type = Base_Type;

private:

static const base_type zero = 0;

static const base_type one = 1;

static const base_type all = ~zero;

static const unsigned int bits_per_block =

sizeof(base_type) * 8;

static const unsigned int blocks =

precision % bits_per_block == 0 ?

precision / bits_per_block :

precision / bits_per_block + 1;

static const unsigned int head_bits =

blocks * bits_per_block - precision;

static const base_type head_mask =

head_bits == 0 ?

~static_cast <base_type >(0) :

(one << (bits_per_block - head_bits )) - 1;

// Contenido del numero.

base_type data[blocks ];

};

En lugar de especificar el numero de enteros simples que forman el vector se indicael numero de bits de precision. Ademas es posible cambiar el tipo basico que forma elvector por enteros de otro tamano, no necesariamente 64 bits. A pesar de que operar conel tamano de palabra de la maquina es mas eficiente puede ser de utilidad disponer deotros tamanos para detectar fallos en el codigo debidos a desbordamientos en operacionescon palabras.

11

3.4. Sumador basico

En un procesador se logran sumas de varios digitos replicando varias veces un mismoelemento basico sumador de bits; recibe dos sumandos y un acarreo y produce un re-sultado y un nuevo acarreo. Este concepto se aplica igualmente con cualquier otra basemayor que 2, como en nuestro caso, donde se manejan las palabras del computador comosi fueran los dıgitos basicos. Por ejemplo, sumando dos palabras de 32 bits y un acarreode 1 bit se obtiene un resultado de 32 bits y otro acarreo de 1 bit.

Sumador

An Bn

Cn Cn-1

Rn

Sumador

An Bn

Cn Cn-1

Rn

32 32

32

Figura 4: Comparacion de un sumador de 1 bit y otro de 32 bits.

An y Bn son las cifras n-esimas de los numeros A y B que se van a sumar, Cn−1 yCn son los acarreos de entrada y de salida y Rn el resultado de la suma.

El siguiente pseudocodigo realiza la suma con acarreo de dos bloques a y b:

function suma basica(a, b, acarreo)r ← a+ boverflow ← (r < a) ∨ (r < b)if acarreo = 1 then

r ← r + 1

if acarreo = 1 ∧ r = 0 thenacarreo← 1

else if overflow thenacarreo← 1

elseacarreo← 0

return r, acarreo

El desbordamiento de los enteros sin signo no es un problema en C++; sigue lasreglas de la aritmetica modulo 2N . [19].

12

El codigo resultante serıa ası:

template <typename T>

T addc(T a,

T b,

T & carry)

{

T r = a + b;

overflow = r < a || r < b;

if (carry)

r++;

carry = overflow || (carry && r == 0)

return r;

}

Esta es la misma operacion con palabras de 32 bits mediante ensamblador x86 parael compilador GCC. El dialecto del codigo es intel.

template <>

inline

uint32_t add_carry(uint32_t a,

uint32_t b,

uint32_t & carry)

{

asm volatile(

"add�al ,�0xff��\n\t" //SR[C] <= RAX[0]

"adc� %[a],� %[b]\n\t" //a <= a + b + SR[C]

"mov�rax ,�0����\n\t" //RAX[0 .. 63] <= 0

"setc�al�������\n\t" //RAX[0] <= SR[C]

: [a]"+r"(a),

[carry]"+a"(carry) //RAX

: [b]"r"(b)

: "cc");

return a;

}

- "asm volatile" significa que el compilador no hara desaparecer el codigo en susintentos de optimizacion.

13

- Los dos puntos “:”separan las declaraciones de variables de salida, entrada y re-gistros modificados para que el compilador lo tenga en cuenta.

- (a) y (carry) seran, en principio, variables de salida, que si son nombradas dentrodel codigo recibiran los alias [a] y [carry].

- El modificador "+r" hace dos cosas; "r" indica que se espera que el valor de (a)

este cargado en un registro cuando se use por primera vez, y "+r" indica queademas (a) sera una variable de entrada y salida. El modificador "+a" de (carry)hace lo mismo, pero ademas requiere que el registro usado sea RAX. Por tantoambas variables son de entrada y salida.

- (b) es una variable de entrada que debera estar cargada en un registro (modificador"r") y sera nombrada usando el alias [b].

- "cc" indica que como resultado de la ejecucion del fragmento de codigo ensambla-dor el registro de estado sera modificado como efecto colateral.

Mediante la suma basica de dıgitos se construyen algunas de las operaciones elemen-tales como la suma, la resta y la multiplicacion.

Cabe plantearse el uso de instrucciones SIMD (single instruction, multiple data) paraaumentar el rendimiento de las operaciones, sin embargo la implementacion de estas enla arquitectura x86 no facilita el calculo de los acarreos ni su propagacion, de modo queno se obtiene mejora alguna: ni para sumar en paralelo los bloques de dos numeros, nipara sumar varios pares de numeros en paralelo.

3.5. Suma

La suma de numeros grandes se consigue repitiendo iterativamente la suma de cadapar de dıgitos (en este caso son palabras del tamano elegido) de la posicion n junto conel acarreo de la operacion n − 1, comenzando por el dıgito menos significativo, el 0. Elacarreo inicial es 0.

A0+B0+C0A1+B1+C1A2+B2+C2An-1+Bn-1+Cn-1

A0A1A2An-1

Bn-1 B2 B0B1

C0 = 0C1C2Cn-1 C3 ADCADCADCADC

Figura 5: Suma binaria mediante suma de bloques (palabras).

14

El pseudocodigo correspondiente al esquema:

function suma((a), (b), N)� (a) y (b) son vectores de bloques de bits (enteros sin signo)

� N es el numero de bloques de cada vectoracarreo← 0for i = 0, i < N do

s, c← suma basica(ai, bi, acarreo)ri ← sacarreo← c

return (r)

Hay que tener en cuenta que en C++ el desbordamiento de las operaciones aritmeti-cas se considera comportamiento indefinido, y significa que el estandar de C++ no obligaa un resultado concreto, lo que conlleva que la portabilidad del codigo no esta aseguraday hace necesario comprobar y, posiblemente, adaptar el codigo en cada arquitectura enla que se vaya a usar. Esto se relaciona tambien con el hecho de que el lenguaje no ofreceuna forma directa de obtener el acarreo de una suma. Para resolver estos problemas sepuede emular el calculo de los resultados, siendo mas costoso computacionalmente, ose puede insertar codigo ensamblador. Lo mejor es hacer las dos cosas; la primera convistas a la portabilidad, y la segunda al rendimiento, siempre que sea posible.

3.6. Resta

Para la resta binaria he usado el metodo del complemento a dos, pues permite efectuarla resta reutilizando la operacion de suma. El complemento a dos de un numero binariopuede considerarse como el opuesto de ese numero, y ası se efectua la resta sumando elminuendo con el opuesto del sustraendo.

El calculo del complemento a dos del sustraendo consiste en invertir todos sus bitsy posteriormente sumar 1 al resultado. Muy convenientemente podemos conseguir estosdos pasos con el operador de negacion binaria de C++ (~) e iniciando la cadena desumas con el acarreo igual a 1.

15

A0+B0+C0A1+B1+C1A2+B2+C2An-1+Bn-1+Cn-1

A0A1A2An-1

Bn-1 B2 B0B1

C0 = 1C1C2Cn-1 C3 ADCADCADCADC

NOT NOTNOTNOT

Figura 6: Resta binaria mediante suma de bloques (palabras). Noteseel acarreo inicial 1 para hacer el complemento a dos del sustraendo.

El pseudocodigo correspondiente al esquema:

function resta((a), (b), N)� (a) y (b) son vectores de bloques de bits (enteros sin signo)

� N es el numero de bloques de cada vectoracarreo← 1 � El acarreo inicial es 1for i = 0, i < N do

not b← not(bi)s, c← suma basica(ai, not b, acarreo)ri ← sacarreo← c

return (r)

3.7. Opuesto, incremento y decremento en 1

A partir de la resta se implementa el opuesto P de un numero N como P = 0−N .Para evitar accesos innecesarios a la memoria el numero 0 sera simplemente un soloregistro para cada bloque de la operacion.

16

A0+B0CBA0+12n0C12n

+12n +B +A+n

CA- -nCnCBC12n C= +3 D+3 D+3 D+3 D

NOT NOTNOTNOT

A

A0+n0Cn A0+A0CA

Figura 7: Calculo del opuesto mediante la resta a 0.

function opuesto((a), N)� (a) es un vector de bloques de bits (enteros sin signo)

� N es el numero de bloques de (a)acarreo← 1 � El acarreo inicial es 1for i = 0, i < N do

not a← not(ai)s, c← suma basica(0, not a, acarreo)ri ← sacarreo← c

return (r)

El incremento I de un numero N sera I = N + 0 + C0, siendo C0 = 1 el acarreoinicial. Y por otro lado el decremento D sera D = N + 0 + C0, con C0 = 0, es decir, laresta de N − 0 pero sin el ajuste +1 del complemento a dos al negar el numero 0.

A0+0+B0AC+0+BCA1+0+B1A2nC+0+B2nC

A0ACA1A2nC

B0- -CBCB1B2nC B= A3 DA3 DA3 DA3 D

0

Figura 8: Calculo del incremento mediante la suma.

17

Cuando la operacion de incremento o decremento se realize in situ no sera necesariorecorrer todo el numero en el caso de que dejen de propagarse acarreos; en el autoin-cremento un acarreo Ci = 0 significa que las cifras superiores no van a cambiar, y en elautodecremento se da el mismo caso para el acarreo Ci = 1, pues 0 + 1 = 0.

function incremento((a), N)� (a) es un vector de bloques de bits (enteros sin signo)

� N es el numero de bloques de (a)acarreo← 1 � El acarreo inicial es 1for i = 0, i < N do

s, c← suma basica(ai, 0, acarreo)ri ← sacarreo← c

return (r)

3.8. Multiplicador basico

Al igual que en la suma, la multiplicacion de dos numeros requiere repetir una mismaoperacion basica sobre pares de cifras (en este caso seran palabras), y esta operacion dacomo resultado (potencialmente) dos cifras: parte alta y parte baja. Esto se debe a quela multiplicacion de dos numeros de M y N cifras da lugar a un numero de al menosM+N−1 cifras, y a lo sumoM+N . Dado que los computadores trabajan con palabras detamano fijo deben usar dos palabras para almacenar el resultado de una multiplicacion.Nuevamente, como en la suma, el lenguaje C++ no permite acceder a parte de esteresultado (la parte alta), teniendo que, o bien emular la operacion, o bien usar codigoensamblador para recuperar este dato.

Multiplicador

An Bn

Hn

Rn

Multiplicador

An Bn

Hn

Rn

32 32

32

32

Figura 9: Comparacion de un multiplicador de 1 bit y otro de 32 bits.El valor H es la parte alta del resultado.

Al igual que en el sumador basico la multiplicacion puede recibir un equivalente alacarreo de una operacion anterior, ası que cabe preguntarse ¿por que no aparece en elesquema?. En la arquitectura x86 las instrucciones de multiplicacion de enteros solo usan

18

los dos factores, y solo recientemente se han anadido al juego de instrucciones operacionesde multiplicacion y suma fusionadas (fused multiply-add, FMA), que ademas no operancon numeros enteros. Puesto que esta operacion con enteros no es tan comun y no estadisponible, la operacion que he implementado de multiplicacion basica es simplementeuna interfaz para acceder a la instruccion que de otra forma no esta disponible en C++.

Para solventar el problema de no tener acceso a la parte alta del resultado puedeusarse codigo ensamblador, tipos de datos de mayor tamano o emular el calculo de laparte alta. El siguiente pseudocodigo calcula las partes alta y baja del resultado sinrecurrir a tipos de datos de mayor tamano:

function multiplicacion basica(a, b)N ← tamano en bits(a)mascarabaja ← despl izq(1, N2 )− 1mascaraalta ← not(mascarabaja)a0 ← and(a,mascarabaja) � Parte baja de atemp← and(a,mascaraalta)a1 ← despl der(temp, N2 ) � Parte alta de ab0 ← and(b,mascarabaja) � Parte baja de btemp← and(b,mascaraalta)b1 ← despl der(temp, N2 ) � Parte alta de br0 ← 0 � Parte baja del resultador1 ← 0 � Parte alta del resultados, c← suma basica(r0, a0 · b0, 0)r0 ← sr1 ← r1 + ctemp← despl izq(a1 · b0, N2 ) � Se pierden N

2 bits de la parte altas, c← suma basica(r0, temp, 0)r0 ← sr1 ← r1 + ctemp← despl izq(a0 · b1, N2 ) � Se pierden N

2 bits de la parte altas, c← suma basica(r0, temp, 0)r0 ← sr1 ← r1 + cr1 ← r1 + despl der(a1 · b0, N2 )

� Al desplazar el producto a1 · b0 se pierden N2 bits de la parte baja

r1 ← r1 + despl der(a0 · b1, N2 )� Al desplazar el producto a0 · b1 se pierden N

2 bits de la parte bajar1 ← r1 + a1 · b1return r0, r1 � Se devuelve una parte baja r0 y una parte alta r1, ambas de N

bits

Al igual que en el sumador basico la diferencia entre la emulacion de la instruccion yla instruccion de ensamblador en sı es enorme, lo que no evita la necesidad de la primera.

19

Una version que use codigo ensamblador para x86 podrıa ser ası:

template <>

inline

uint32_t mul_carry <uint32_t >( uint32_t a,

uint32_t b,

uint32_t & carry)

{

asm volatile("mul� %[b]\n\t"

: [carry]"=d"(carry), //edx

[a]"+a"(a) //eax

: [b]"r"(b)

: "cc");

return a;

}

3.9. Multiplicacion

3.9.1. Multiplicacion clasica

Una implementacion del algoritmo de multiplicacion clasica de la escuela es obligato-ria, tanto para testear la correccion de otros algoritmos como su velocidad de ejecucion.El concepto es identico tanto en decimal como en la implementacion binaria en hardwarey como al operar con bloques: el producto Ai ·Bj da lugar a una parte baja Li+j y unaalta Hi+j+1; se suman los bloques de igual subındice, se propagan los acarreos de lasuma y obtenemos ası el resultado.

20

Ai+1 Ai

Bj+1 Bj

Ai·Bj

Ri+jRi+j+1Ri+j+2

Ai·Bj+1

Ai+1·Bj

Ai+1·Bj+1

Ri+j+3

X

Figura 10: Fragmento de la multiplicacion clasica. Los cuadros en grisson la parte alta del producto de las multiplicaciones parciales de

cada par de bloques de los factores A y B.

function multiplicacion((a), (b), N)� (a) y (b) son vectores de bloques de bits (enteros sin signo)

� N es el numero de bloques de (a)for i = 0, i < 2N do

ri ← 0 � Inicializamos el resultado de tamano 2N con ceros

for i = 0, i < N dofor j = 0, j < N do

baja, alta← multiplicacion basica(ai, bj)ri+j , acarreo← suma basica(ri+j , baja, 0)ri+j+1, acarreo← suma basica(ri+j+1, alta, acarreo)k ← 2while acarreo = 1 do

ri+j+k, acarreo← suma basica(ri+j+k, 0, acarreo)k ← k + 1

return r

21

Ya que la multiplicacion es parte de otras operaciones como la division o la potenciaes ventajoso contar con una implementacion tipo FMA, o sea, multiplicacion y sumafusionadas.

3.9.2. Multiplicacion de Karatsuba

El algoritmo de Karatsuba fue descubierto en 1960 por Anatoli Alekseevich Karatsu-ba[20], tras asistir a un seminario de Andrei Kolmogorov, en el que este ultimo conjetura-ba que el algoritmo de multiplicacion clasico, de complejidad O(n2), era asintoticamenteoptimo. Esto supuso un incentivo para Karatsuba que, siendo un estudiante de 23 anos,desarrollo el algoritmo en una semana. La complejidad del mismo es de O(nlog23), apro-ximadamente O(n1,585).

La base del algoritmo es reescribir los factores a multiplicar a y b para que tenganuna parte alta y una parte baja:

a = a1 · 2n/2 + a0

b = b1 · 2n/2 + b0,

donde los factores a y b tienen n bits.El producto ab se puede escribir entonces como:

ab = (a1 · 2n/2 + a0)(b1 · 2n/2 + b0)

ab = c2 · 2n + c1 · 2n/2 + c0,

con

c2 = a1b1

c1 = a1b0 + a0b1

c0 = a0b0.

Esta formula requiere cuatro multiplicaciones, pero Karatsuba se dio cuenta de quepodıa calcular c1 como:

c1 = (a1 + a0)(b1 + b0)− c2 − c0

evitando una de las multiplicaciones.Hay que notar que el calculo de (a1+a0)(b1+ b0) podrıa llevar a un desbordamiento,

lo que puede evitarse reescribiendo c1 como:

c1 = (a0 − a1)(b0 − b1) + c2 + c0

22

que produce resultados en el intervalo (−2n2 , 2

n2 ). El producto (a0 − a1)(b0 − b1) puede

dar lugar, no obstante, valores negativos, algo que debe ser tenido en cuenta al realizarlos calculos, pues esto requiere un bit adicional.

La disminucion de la complejidad del algoritmo se debe a que esta reduccion de lasmultiplicaciones (de cuatro a tres) se hace recursivamente mientras sea posible, hastamanejar numeros suficientemente pequenos. El concepto de “pequeno” depende de cues-tiones practicas pues, aunque en teorıa el mınimo de tamano para aplicar la recursionson 4 bits, en la practica un computador de 64 bits calculara a igual velocidad productosde 4 bits que de 64, haciendo que la division recursiva del problema por debajo de esetamano sea mucho mas ineficiente. Mas aun, el algoritmo clasico resulta mas rapido contamanos menores de 20000 bits, tal vez por el menor uso de memoria.

23

function karatsuba((a), (b), N)P ← N

2 � Bits de la parte bajaQ← N − P � Bits de la parte altaif N < umbral then

mascara← despl izq(1, P )− 1a0 ← and(a,mascara) � Parte baja de aa1 ← despl der(a, P ) � Parte alta de ab0 ← and(b,mascara) � Parte baja de bb1 ← despl der(b, P ) � Parte alta de bu0, u1 ← karatsuba(a0, b0, P ) � Llamada recursiva con tamano Pw0, w1 ← karatsuba(a1, b1, Q) � Llamada recursiva con tamano Qif a0 < a1 then

signoa ← 1difa ← a1 − a0

elsesignoa ← 0difa ← a0 − a1

if b1 < b0 thensignob ← 1difb ← b0 − b1

elsesignob ← 0difb ← b1 − b0

d0, d1 ← karatsuba(difa, difb, Q) � Llamada recursiva con tamano Quw0, acarreo← suma acarreo(u0, w0, 0) � Suma de tamano Puw1, uwacarreo ← suma acarreo(u1, w1, acarreo) � Suma de tamano Qsigno← xor(signoa, signob)if signo = 1 then

d0 ← not(d0) � Negacion para restar en complemento a 2d1 ← not(d1)uwacarreo ← xor(uwacarreo, 1)

v0, acarreo← suma acarreo(d0, uw0, signo)v1, acarreo← suma acarreo(d1, uw1, acarreo)vacarreo ← xor(acarreo, uwacarreo) � Este bit es parte de v

� Con u, v y w ya se puede componer el resultado finaltemp, acarreo0 ← suma acarreo(u1, v0, 0) � Suma de tamano Qbaja← u0 + despl izq(temp, P )temp1, acarreo1 ← suma acarreo(v1, w0, acarreo0) � Suma de tamano Qtemp2 ← w1 + acarreo1 + vacarreoalta← temp1 + despl izq(temp2, P )if P < Q then � Si son distintos su diferencia es 1

alta← despl izq(alta, 1) + leer bit(baja, P − 1)escribir bit(baja, P − 1, 0)

return baja, alta � baja y alta tienen tamano N24

3.10. Division y modulo

3.10.1. Division larga

La division larga permite dividir dos numeros obteniendo un dıgito del cociente encada paso[21]. Su fama se debe a que es un algoritmo suficientemente sencillo como parahacerlo a mano. Ademas se obtiene el resto de la division.

Este es algoritmo de la division larga sobre enteros binarios obtenida de la Wikipe-dia[22]:

function division(dividendo, divisor)if divisor = 0 then

errorcociente← 0resto← 0for i = precision, i > 0 do

resto← despl izq(resto, 1)b← leer bit(dividendo, i− 1)escribir bit(resto, 0, b)if resto ≥ divisor then

resto← resto− divisorescribir bit(cociente, i− 1, 1)

return cociente, resto

3.10.2. Division larga en bloques

El problema de la version anterior es su completo desaprovechamiento del paralelismodel computador. No es que el algoritmo sea paralelizable, pero en el caso de que existauna instruccion de division de enteros, esta se puede usar para resolver mas dıgitos encada paso (en vez de ir de uno en uno). Para encontrar la forma vamos a observar elfuncionamiento de la division larga:

Queremos calcular1239931/97,

o escrito de otra forma, queremos determinar Q,R ∈ N tal que

1239931 = Q · 97 +R.

Comprobamos que el cociente Q debe ser menor que 100000, pues

1239931 < 97 · 100000.La cifra correspondiente a las centenas de millar del cociente es un 0.

La primera posicion no nula del cociente resulta ser las decenas de millar, pues

1239931 ≥ 97 · 10000.

25

Ademas esta cifra es un 1, ya que

1239931 < 97 · 20000.

Ahora sabemos que el cociente

Q ≥ 10000,

y podemos calcularlo comoQ = Q1 + 10000,

donde1239931− 10000 · 97 = Q1 · 97 +R.

Ası que ahora queremos calcular269931/97.

Dado que el cociente Q1 < 10000 probamos primero con los millares, entre 1000 y9000. La cifra resulta ser un 2, pues

269931 ≥ 97 · 2000

y269931 < 97 · 3000.

Nuevamente, sabemos que el cociente

Q ≥ 12000,

y podemos calcularlo comoQ = Q2 + 12000,

donde1239931− 12000 · 97 = Q2 · 97 +R.

Ası que ahora queremos calcular75931/97.

Aplicando estos pasos de forma sucesiva llegamos a que

Q = 12782

R = 77

En el caso de dividir en base binaria el tanteo de cada cifra del cociente se reduce aprobar con el 0 y el 1. Si hiciesemos lo mismo con bases mayores, por ejemplo, base 10,podrıamos intentar recorrer todo el rango desde 0 hasta 9, pero serıa muy ineficiente. Lamejor forma serıa, pues, una busqueda binaria en el intervalo, reduciendo el tamano del

26

mismo a la mitad en cada tanteo. Y esto nos lleva de nuevo a la base binaria. ¿Podemosevitarlo?

La idea de usar cifras del tamano de palabra de la maquina no es para evitar obtenerdıgitos del cociente a una velocidad mınima de un bit por iteracion, sino delegar estatarea a la instruccion de division de la maquina, obteniendo tantos bits como nos permitatal instruccion de una sola vez.

Sin embargo esto plantea un problema: ni el dividendo ni el divisor caben en losregistros (pues son numeros grandes). Ası que nos vemos obligados a usar solo partede ellos, los bits mas significativos. ¿Cuantos? Primero hay que tener en cuenta que sitenemos un dividendo de M bits y un divisor de N bits el cociente sera de M−N . Ahora,queremos que la aproximacion del cociente tenga toda la precision posible, el maximonumero de bits posible, pero si usamos un divisor con pocos bits sera poco representativodel divisor completo y la aproximacion del cociente sera mala.

Como ejemplo: si usaramos N bits del dividendo y N bits del divisor el resultadotendrıa 1 bit de precision. Si usaramos N bits del dividendo y 1 bit del divisor, el bit deldivisor siempre serıa 1, haciendo la operacion inutil. Aumentamos, entonces, el numerode bits del divisor hasta N

2 y ası la aproximacion del cociente tendra tambien N2 bits.

function division(dividendo, divisor,N)cociente← 0if divisor = 0 then return errordBMS ← bms(divisor) � Bit mas significativo del divisord0 ← despl der(divisor, dBMS − N

2 ) + 1 � Copiamos los primeros N2 bits del

divisor y ajustamos al alzawhile dividendo ≥ divisor do

EBMS ← bms(dividendo) � Bit mas significativo del dividendo actualE0 ← despl der(dividendo,EBMS −N) � Copiamos los primeros N bits del

dividendoc← E0

d0� Cociente parcial

desplazamiento← EBMS − dBMS − N2

if desplazamiento ≤ 0 thenc← despl der(c,−desplazamiento)if c = 0 then � Esto puede suceder por ajustar d0 al alza

c← 1p← c · divisorif desplazamiento > 0 then

c← despl izq(c, desplazamiento)p← despl izq(p, desplazamiento)

cociente← cociente+ cdividendo← dividendo− p

resto← dividendoreturn cociente, resto

27

La complejidad computacional de este algoritmo es la misma que en la version massencilla: O(n2), mas concretamente O(m · n), siendo m la diferencia entre el tamanoen bits del dividendo y el divisor y n el tamano de los operandos de las operacionesnecesarias; restas, desplazamientos, productos. Sin embargo este ultimo algoritmo esmas rapido, pues en vez de calcular 1 bit del cociente en cada paso calcula R

2 bits, dondeR es el tamano del registro del procesador. Es necesario, eso sı, disponer de una operacionde division entera en el procesador y que esta sea razonablemente veloz.

3.11. Imprimir los numeros en decimal

3.11.1. Algoritmo simple

Mostrar en la pantalla numeros binarios en formato binario no tiene secreto alguno;usar bases que sean potencias de 2 es bastante sencillo, tambien. El problema surgecuando una cifra en otra base requiere un numero de cifras binarias no entero, porejemplo en base 10, pues cada cifra usa log2(10) ∼ 3,32 bits. En este caso se hacenecesario usar la division entera para obtener los dıgitos.

Este es el metodo clasico:

function conversion decimal(n)if n = 0 then

r ← ‘0’

elser ← cadena vacıawhile n > 0 do

cociente, resto← division(n, 10)caracter ← numero a texto(resto)r ← anexar(r, caracter)n← cociente

invertir cadena(r)

return r

Si se tratase de imprimir un numero en decimal de unas 500 cifras el bucle se repetiria500 veces, disminuyendo el tamano del dividendo de 1 en 1. Es decir, en la primeraiteracion el dividendo tendria 500 cifras, en la segunda 499, en la tercera 498, ... Comose realizan n divisiones de tamano promedio n

2 y la complejidad de la division es O(n2)podemos estimar que la complejidad del algoritmo es O(n3).

3.11.2. Algoritmo “divide y venceras”

Esto se puede mejorar con una aproximacion tipo “divide y venceras”. El numerototal de divisiones seguira siendo el mismo, pero estas se haran sobre numeros maspequenos. El metodo consiste en dividir el trabajo de calcular los dıgitos de un numerode tamano N en dos partes iguales (tambien puede probarse con tres o mas), lo que

28

requiere primero calcular el divisor 10N2 y repetir la operacion con cada una de las partes,

cociente y resto, sucesivamente hasta que los numeros sean lo suficiente pequenos comopara dividirlos con las instrucciones del procesador en vez de las operaciones de manejode numeros grandes.

function conversion decimal(n)r ← cadena vacıa � Guardara el resultado finalcifras← bms(n)·10

32 + 1 � Numero de cifras inicialmente estimadocon dec aux(r, n, cifras)invertir cadena(r)borrar ceros izq(r)if es vacıa(r) then

r ← ‘0’

return r

procedure conversion decimal aux(cadena, n, cifras)if cifras > umbral then

cifras0 ← cifras2

cifras1 ← cifras− cifras0� Dividiremos el numero en dos partes

potencia← 10cifras1 � Este numero puede precalcularseparte1, parte0 ← division(n, potencia)for i = 0, i < 2 do

ci ← cadena vacıaconversion decimal aux(ci, partei, cifrasi)

� El numero partei tiene la mitad de bits que nanexar(cadena, ci)

elsefor i = 0, i < cifras do

cociente← n10 � Esta division no es de numeros grandes.

resto← n− cociente · 10caracter ← numero a texto(resto)anexar(cadena, caracter)n← cociente

Pasar de un tamano N a 2N implica duplicar el trabajo de N y anadir una divisionde tamano 2N . Por ejemplo, para el tamano N llamaremos P al numero de pasos nece-sarios para hacer la division de mayor tamano y Q a los pasos que requiere el resto deoperaciones recursivas. De esta forma el tamano N implica realizar P +Q pasos. Comola complejidad de la division es cuadratica, duplicar el tamano del problema requiereque la mayor division necesite 4P pasos (ignorando las constantes), mientras que el restodel problema requiere 2(P +Q) pasos; en total, el tamano 2N requiere 4P + 2P + 2Q.

29

Si seguimos duplicando el tamano se observa esta evolucion en el numero de pasos:

N → P +Q

2N → 4P + 2P + 2Q

4N → 16P + 8P + 4P + 4Q

8N → 64P + 32P + 16P + 8P + 8Q

16N → 256P + 128P + 64P + 32P + 16P + 16Q

32N → 1024P + 512P + 256P + 128P + 64P + 32P + 32Q

Multiplicar por X el tamano del problema hace que algoritmo requiera (2X2 −X) ·P + X · Q pasos, de lo que se deduce que la complejidad del algoritmo es cuadratica(O(n2)), lo que me sorprende, pues esperaba que fuera O(n2 · log n).

3.12. Otras operaciones

Otras operaciones desarrolladas son:

• Desplazamiento aritmetico. Varios algoritmos de los presentados hacen uso deldesplazamiento aritmetico y es tambien una operacion muy utilizada por mejorarla velocidad de ejecucion de multiplicaciones y divisiones cuando se hacen conpotencias de 2. Las rotaciones no estan implementadas.

• Operadores de bits y mascaras. En una implementacion completa de los operadoresde enteros de C++ no pueden faltar las operaciones logicas “o”, “y”, “o exclusivo”y “negacion” aplicadas sobre bits. Para facilitar la creacion de mascaras y, sobretodo, su uso eficiente se han anadido tres operaciones para consultar/establecerel contenido de un bit indicando su posicion y para establecer el contenido de unintervalo de bits (get bit, set bit y set range).

• Exponenciacion. El algoritmo rapido de conversion a decimal requiere el calculo depotencias de 10. Como no podıa ser de otra manera, he usado la exponenciacionbinaria[23]. Tambien existe un metodo para exponenciacion en modulo.

• Conversion de tipos. Es de tres tipos: de entero basico a numero grande y viceversa,y de numero grande de un tamano a numero grande de otro. Cuando se asigna unnumero negativo a un numero grande se hace extension de signo para facilitar unafutura implementacion de numeros grandes con signo. Ademas es posible designarel valor de un numero grande mediante una cadena de texto en las bases 2, 8, 10y 16.

Asımismo las operaciones aritmeticas que puedan recibir como segundo argumentoun numero grande tambien son capaces de manejar un entero basico sin hacersu conversion, ahorrando uso de memoria y con ello mejorando la velocidad deejecucion.

30

4. Pruebas y resultados

He hecho pruebas para verificar la correccion de los resultados comparando con labiblioteca GMP. Aparte de eso he hecho comparaciones de velocidad de ejecucion conlas bibliotecas GMP y TTMath.

La ejecucion se ha hecho en un procesador de la arquitectura x86-64, modelo AMD64Phenom II X6 1050T de 6 nucleos, aunque todas las pruebas funcionaron en un solo hilo.Cada nucleo tiene 64 KB de cache de instrucciones y 64 KB de datos en el nivel 1 y 512KB en el nivel 2. Hay una cache de 6 MB compartida por todos los nucleos. La velocidadde reloj era de 2200 MHz.

En las siguientes tablas se muestran los resultados. En la columna izquierda estanlos tamanos de los operandos usados; en las restantes aparece el numero de operacionespor segundo alcanzadas.

Sumas por segundoTamano gueb::big uint GMP TTMath

100 225432958 53330023 214277952150 199155263 54792458 198740652200 156554969 55824660 168572022500 84318126 45609549 68353433

1000 33714132 34773819 292222592000 19397550 25188555 167915005000 8673320 12136349 796329210000 4506755 7750147 439264620000 2281162 3388096 222963450000 929014 1607045 916195

100000 466228 772899 362699200000 229000 172851 171036500000 85847 61485 575551000000 24858 9369 204092000000 10398 3833 8392

31

Desplazamientos aritmeticos por segundo(31 bits a la izquierda)

Tamano gueb::big uint GMP TTMath

100 387631019 54596580 102139294150 166483149 57057018 81172871200 142551414 46757756 64764644500 72155200 41345836 32232417

1000 33634088 30180593 57518762000 14245156 20887754 32708585000 6438706 9398081 119321110000 3360638 5183557 60358220000 1721137 2771050 30337750000 695328 1100436 137516

100000 325404 552342 71014200000 167993 161930 35701500000 66639 64067 137351000000 25171 8572 65372000000 13658 4211 2958

Multiplicaciones por segundoTamano gueb::big uint GMP TTMath

100 149375869 42877781 55063486150 72441238 42933961 42855983200 33191837 20742200 24826570500 9660468 8871847 21928901000 2292563 2931087 6388472000 524808 936794 1847535000 93875 201664 27112

10000 30939 65988 889420000 10043 23241 295650000 2040 6425 745

100000 675 2409 246200000 219 905 81500000 51 271 241000000 17 111 82000000 5 53 2

32

Divisiones por segundo(el divisor tiene la mitad de bits)

Tamano gueb::big uint GMP TTMath

100: 2373963 12651306 223478978150: 2148652 12641366 22649528200: 1903429 9721190 2787253500: 507155 4699269 11122221000: 187525 2624545 3499892000: 63687 1362301 1420155000: 13646 370517 34393

10000: 4015 115700 809820000: 1120 36117 267350000: 187 7941 406100000: 48 2646 101200000: 10 932 22500000: ∼1 269 ∼2

1000000: <1 108 <12000000: <1 46 <1

Se puede ver como en las operaciones sencillas como la suma y el desplazamientoaritmetico es factible alcanzar la rapidez de una biblioteca de alto nivel como GMP. Entamanos pequenos el uso de tamano fijo permite al compilador convertir datos variablesen constantes y, con ello, desenrollar bucles, intercalar el codigo de los procedimientosen vez de llamarlos y mantener los datos de trabajo en registros sin necesidad de accedera la memoria. Todo esto repercute en un mayor rendimiento. Tambien se ve como apartir del tamano ∼1000 esta ventaja desaparece, y GMP es superior. Probablemente sedeba a que la biblioteca GMP dispone de codigo con bucles desenrollados mientras queel compilador no realiza esta tarea automaticamente con tamanos grandes. Finalmente,cuando el tamano pasa a ser mayor de ∼100000 bits el rendimiento de GMP vuelve adecaer, lo que puede ser achacable al desbordamiento de la memoria cache de nivel 1. Elcodigo de prueba que usan TTMath y gueb::big uint es tal que ası:

for (uint64_t i = 0; i < iteraciones; i++)

c = a + b;

33

Mientras que para GMP es ası:

for (uint64_t i = 0; i < iteraciones; i++)

mpz_add(c, a, b);

La variable de destino en el primer caso es siempre la misma, y su memoria asignada,por tanto, tambien. Para GMP la variable de destino se crea en memoria dinamica y lamemoria de esta variable podrıa ser distinta en dos llamadas consecutivas, sobre todo sise libera la memoria del contenido anterior antes de asignar el nuevo. Esto provocarıaque GMP estuviera usando la memoria correspondiente a 4 o mas variables, mientrasque las versiones de memoria estatica usan 3. El lımite para contener 3 variables en 64KB de cache serıan 65536/3 ∗ 8 ∼ 174762 bits, pero para 4 serıan 65536/4 ∗ 8 = 131072.De esta forma GMP comenzarıa a tener fallos de cache al llegar a ese lımite, y convariables de 200000 bits tendrıa muchos mas fallos que las otras dos bibliotecas.

En el caso de las multiplicaciones sucede lo mismo para tamanos pequenos, sin em-bargo al aumentar la disparidad es bastante grande. La biblioteca GMP usa metodosdistintos para multiplicar segun las dimensiones de los operandos, como los algoritmosde Karatsuba[20], Toom-Cook[24] o Schonhage-Strassen [8], mientras que TTMath ygueb::big uint solo usan Karatsuba.

Por ultimo, la division de gueb::big uint esta a mucha distancia de tener un rendi-miento aceptable.

34

5. Conclusiones y lıneas futuras

¿En que medida se han logrado los objetivos?

- Facilidad de uso. Gracias a la conversion automatica desde y hacia tipos basicos yla sobrecarga de operadores la interfaz es casi identica a la de los tipos basicos. Alestar compuesta la biblioteca unicamente de ficheros de cabeceras se puede integraren otros proyectos con sencillez, tan solo copiando los ficheros.

- Rapidez. Conocer de antemano el tamano de los numeros permite al compiladorlograr mayor velocidad con numeros de hasta algo menos de 1000 bits, a partir delo cual el tamano dinamico comienza a ganar ventaja.

En general, las operaciones son considerablemente rapidas, pero la implementacionde la division es varios ordenes de magnitud mas lenta que la implementacion queuso de referencia (la biblioteca GMP), y requiere mas trabajo para mejorar.

- Se puede implementar un tipo de datos de numeros en coma fija o coma flotantecon bastante facilidad basandose en esta biblioteca. La estructura compacta enmemoria posibilita, por ejemplo, implementar numeros en coma flotante que siganel estandar IEEE-754.

La biblioteca se puede mejorar o ampliar por las siguientes vıas:

• Division por “divide y venceras”. La division larga en bloques se basa en el usode una instruccion de division entera mediante hardware, pues es de suponer queesta sea bastante rapida. ¿Que ocurre si no hay tal instruccion? ¿Es mas rapido elmetodo clasico o una emulacion de la division entera usando registros como ope-randos puede ser de ayuda en la division larga en bloques? Llevando este conceptoal extremo, ¿podemos basar la division de numeros de N bits en la suposicion deque ya disponemos de una division de numeros de N

2 bits y usarla con la divisionlarga mejorada? ¿Podemos implementar la division de numeros de N

2 bits median-te una division de numeros de N

4 bits? De aquı surge otro metodo de division denumeros grandes, aplicando el famoso paradigma de diseno “divide y venceras”.

• Cuadrado mas eficiente. Si representasemos los productos parciales de las cifras deuna multiplicacion en una tabla comprobarıamos que cuando los dos factores de lamultiplicacion son iguales la tabla tiene el aspecto de una matriz simetrica. Comocasi la mitad de estos calculos estan repetidos pueden ahorrarse y aumentar lavelocidad del calculo del cuadrado de un numero, lo que beneficiara a la operacionde exponenciacion que se basa en el mismo.

• Multiplicaciones de Toom-Cook y Schonhage-Strassen. La multiplicacion de Toom-Cook[24] es una generalizacion del algoritmo de Karatsuba que funciona partiendolos factores en fragmentos de igual tamano, tipicamente 3 o mas, que son opera-dos recursivamente de forma que se evitan varias multiplicaciones originalmentenecesarias. Debido a su sobrecoste en otras operaciones, no resulta practico con

35

numeros relativamente pequenos, para los que la multiplicacion clasica o la de Ka-ratsuba son mas rapidas. Cuando se llega a un cierto lımite, aumentar el numerode fragmentos resulta contraproducente y comienza a ser viable otro algoritmo:Schonhage-Strassen[8].

El algoritmo de Schonhage-Strassen concibe la multiplicacion clasica de enteroscomo un producto de convolucion[25] y, como tal, se puede calcular transformandoel dominio del problema mediante una transformada de Fourier[26], que posibilitacalcular la convolucion con menos operaciones. Posteriormente hay que hacer latransformacion inversa.

• Enteros con signo. Las operaciones de resta y opuesto de un numero operan encomplemento a 2, lo que facilita el paso a manejar enteros con signo. Las operacio-nes de multiplicacion y division requerirıan una implementacion distinta, aunquesi tenemos en cuenta su, comparativamente, lenta velocidad de ejecucion, un parde cambios de signo antes de operar no tendrıa un impacto demasiado apreciableen el rendimiento total, haciendo evitable reimplementar estas operaciones.

• Tamano variable. Para tamanos relativamente pequenos (128-1024 bits...) el cono-cimiento a priori del tamano del numero resulta muy ventajoso para el compilador,pues puede propagar los valores conocidos de estos datos y preparar versiones masrapidas del codigo para esos tamanos, al ahorrar calculos durante la ejecucion.Cuando el tamano crece mas se hacen patentes otros problemas como el desper-dicio de memoria y de tiempo de procesador en numeros de mucho tamano quepueden contener temporalmente valores pequenos. La parte alta de estos numeroscontiene ceros que hay que almacenar y actualizar en cada operacion aritmetica.Aparte de las ventajas y desventajas explicadas antes, los procesadores operan conpalabras de tamano fijo por una razon: simplicidad. Pero una vez que necesitamossuperar esos tamanos, y no teniendo instrucciones nativas para operar con tamanosmayores y fijos, ¿seguimos necesitando que sean fijos?

36

Referencias

[1] Arbitrary-precision arithmetic: Applications. url: https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Applications (visitado 27-08-2017).

[2] Jonathan M. Borwein David H. Bailey. High-Precision Arithmetic in MathematicalPhysics. url: http : / / www . mdpi . com / 2227 - 7390 / 3 / 2 / 337 / pdf (visitado27-08-2017).

[3] Not invented here. url: https://en.wikipedia.org/wiki/Not_invented_here(visitado 12-06-2018).

[4] List of arbitrary-precision arithmetic software. url: https://en.wikipedia.org/wiki/List_of_arbitrary- precision_arithmetic_software (visitado20-08-2017).

[5] Boost (C++ libraries). url: https://en.wikipedia.org/wiki/Boost_(C%2B%2B_libraries) (visitado 20-08-2017).

[6] Christian Kaiser Tomasz Sowa. Frequency asked questions about TTMath. url:http://www.ttmath.org/faq (visitado 20-08-2017).

[7] GNU Multiple Precision Arithmetic Library. url: https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library (visitado 20-08-2017).

[8] Schonhage–Strassen algorithm. url: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm (visitado 20-08-2017).

[9] Divide and Conquer Division. url: https://gmplib.org/manual/Divide-and-Conquer-Division.html (visitado 20-08-2017).

[10] Class Library for Numbers. url: https://en.wikipedia.org/wiki/Class_Library_for_Numbers (visitado 20-08-2017).

[11] David H. Bailey y col. High-Precision Software Directory. url: http://crd.lbl.gov/~dhbailey/mpdist/arprec-2.2.19.tar.gz (visitado 13-08-2017).

[12] Michael C. Ring. url: https://github.com/LuaDist/mapm/raw/master/m_apm.h (visitado 20-08-2017).

[13] MPIR (mathematics software). url: https://en.wikipedia.org/wiki/MPIR_(mathematics_software) (visitado 20-08-2017).

[14] Libgcrypt. url: https://en.wikipedia.org/wiki/Libgcrypt (visitado 12-05-2018).

[15] Status of Supported Architectures from Maintainers’ Point of View. url: https://gcc.gnu.org/backends.html (visitado 24-08-2017).

[16] Middle-endian. url: https://en.wikipedia.org/wiki/Endianness#Middle-endian (visitado 25-08-2017).

[17] Stream buffers. url: https://en.wikipedia.org/wiki/Cache_prefetching#Stream_buffers (visitado 26-08-2017).

[18] IEEE 754. url: https://en.wikipedia.org/wiki/IEEE_754 (visitado 11-09-2017).

37

[19] c++11 - Is signed integer overflow still undefined behaviour in C++? url: https://stackoverflow.com/questions/16188263/is-signed-integer-overflow-

still-undefined-behavior-in-c (visitado 04-07-2018).

[20] Karatsuba algorithm. url: https : / / en . wikipedia . org / wiki / Karatsuba _

algorithm (visitado 29-05-2018).

[21] Division larga. url: https://es.wikipedia.org/wiki/Divisi%C3%B3n_larga(visitado 29-05-2018).

[22] Integer division with remainder. url: https : / / en . wikipedia . org / wiki /

Division_algorithm#Integer_division_(unsigned)_with_remainder (vi-sitado 29-05-2018).

[23] Exponenciacion binaria. url: https://es.wikipedia.org/wiki/Exponenciaci%C3%B3n_binaria (visitado 03-07-2018).

[24] Toom-Cook multiplication. url: https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication (visitado 06-07-2018).

[25] Convolucion. url: https://es.wikipedia.org/wiki/Convoluci%C3%B3n (visi-tado 06-07-2018).

[26] Transformada rapida de Fourier. url: https : / / es . wikipedia . org / wiki /

Transformada_r%C3%A1pida_de_Fourier (visitado 06-07-2018).

38