Biblioteca de números grandes en C++

Suárez Domingos, José Osvaldo (2018). Biblioteca de números grandes en C++. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Description

Title: Biblioteca de números grandes en C++
Author/s:
  • Suárez Domingos, José Osvaldo
Contributor/s:
  • Pérez Costoya, Fernando
Item Type: Final Project
Date: July 2018
Subjects:
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Arquitectura y Tecnología de Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (282kB) | Preview

Abstract

La aritmética de precisión arbitraria o múltiple precisión, es la realización de operaciones aritméticas en un computador (tanto de números enteros como fraccionarios) con tamaños de operandos mayores que el tamaño de palabra de este. Los datos manejados típicamente por computadores oscilan entre 8 y 64 bits de precisión, y sus unidades aritmético-lógicas (por sus siglas en inglés, ALU) son, en general, capaces de operar con estos tamaños en un solo paso. Varios lenguajes de programación (Lisp, Python, Perl, Haskell, Ruby) tienen soporte nativo para números grandes que implementan mediante vectores de longitud variable [1]. Un uso muy común de los números grandes es la criptografía de clave asimétrica, cuyos algoritmos emplean números de cientos o miles de bits. Por ejemplo, 1024, 2048 o 4096 bits son valores típicos en el tamaño de clave del algoritmo criptográfico RSA. Si bien estas longitudes de clave de miles de bits no son obligatorias (el algoritmo puede trabajar con cualquier tamaño), en la práctica son necesarias para evitar ataques de fuerza bruta. Otros usos comunes son los cálculos financieros, el estudio numérico de funciones matemáticas cuando los métodos analíticos no son viables (por ejemplo: la función zeta de Riemann), o la simulación y predicción de sucesos físicos (por ejemplo: el seguimiento de partículas en el acelerador \LHC" [2]). Experimentando con un algoritmo para predicción de resultados deportivos me encontré con un sistema de ecuaciones mal condicionado y pensé en usar números de coma flotante con precisión mayor que doble o cuádruple bits (el compilador GCC implementa mediante software un tipo de coma otante de 128 bits float128). Aunque sabía de algunas bibliotecas de números grandes decidí que quería hacer una para probar si podía superar a las existentes y que se adaptase a mi gusto [3]. El objetivo de este proyecto es desarrollar una biblioteca para manejo de números grandes en C++ que cumpla estos requisitos: - Fácil de usar. Mediante la sobrecarga de operadores que permite el lenguaje la sustitución de un tipo de enteros genérico por esta implementación debería ser lo más directa posible. - Razonablemente rápido. La velocidad de ejecución tiene dos vertientes, por un lado la complejidad computacional y por otro, dado un algoritmo, el óptimo aprovechamiento de los recursos. Desde el punto de vista académico es más importante la primera, así que no deberían faltar algoritmos más eficientes que las versiones clásicas allá donde sea posible. - Que sirva como base para implementar coma fija y coma flotante. Ambos conceptos implican que el número de bits de cualquier número es fijo.

More information

Item ID: 52392
DC Identifier: http://oa.upm.es/52392/
OAI Identifier: oai:oa.upm.es:52392
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 26 Sep 2018 11:18
Last Modified: 26 Sep 2018 11:19
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM