Biblioteca de enteros de 128 bits más rápida

Question

Estoy trabajando en una aplicación de computación numérica pesada de CPU. Sin entrar en muchos detalles, se trata de un proyecto de investigación de matemática computacional que implica calcular una cierta función f (x) para un entero grande x.

Ahora todo está implementado en C++ en modo x64, usando ints nativos de 64 bits. Eso me limita a x < 2^64 ~ 1.8 * 10^19. Quiero ir más allá, para hacer eso, necesito una biblioteca que haga aritmética de 128 bits. Y tiene que ser muy rápido. En particular, las divisiones enteras deben ser rápidas. De lo contrario, estaré sentado aquí esperando los resultados hasta el Día de Acción de Gracias. Y prefiero no reinventar la rueda.

Encontré una lista de ~ 20 grandes bibliotecas enteras en Wikipedia, pero la mayoría de ellas parecen dirigidas a números de precisión arbitraria, lo cual es excesivo para mi tarea, y no necesito costos adicionales asociados con eso.

¿Alguien sabe qué biblioteca puede operar en los enteros de 128 bits más rápido?

Answer 1

No mencionó los requisitos de plataforma/portabilidad. Si está dispuesto a usar gcc o clang, en plataformas de 64 bits tienen un tipo incorporado de 128 bits que viene gratis, __uint128_t y __int128_t. Quizás otras plataformas tengan extensiones de tipo similar.

En cualquier caso, debería ser posible encontrar el código genérico correspondiente en los gcc fuentes que reúne dos números enteros de anchura N para sintetizar un número entero de anchura 2N. Este probablemente sea un buen punto de partida para hacer una biblioteca independiente para ese propósito.

Answer 2

Esto puede que no sea para todo el mundo, pero lo que yo haría es elegir la biblioteca de números enteros arbitrarios de mayor rendimiento con código fuente y adecuado para el trabajo, y hackearlo para tamaños enteros fijos. Cambia algunas variables "nbits" a 128 codificadas. Probablemente asigna memoria en tiempo de ejecución, sin saber el número de bytes hasta entonces. Cámbielo para usar struct con datos in situ, guardando un puntero de eliminación de referencias cada vez que se leen datos. Desenrolle ciertos lazos críticos a mano. Codifique cualquier otra cosa que pueda ser crítica. Entonces el compilador probablemente tendrá un tiempo más fácil para optimizar las cosas. Por supuesto, gran parte de esto será ensamblado, usando SIMD elegante con lo que sea que la tecnología esté en uso esta semana.

¡Sería divertido! Pero luego, como programador comencé con código de máquina y cosas de muy bajo nivel.

Pero para aquellos que no están tan locos como yo, tal vez una de las bibliotecas disponibles usa plantillas o tiene alguna forma de generar código personalizado para algún tamaño. Y, algunos compiladores tienen un tipo entero largo "largo" que podría ser adecuado.

Answer 3

La biblioteca ttmath hace lo que quiere.