Esistono implementazioni di interi interi solidi in C?

Question

Sto lavorando a un progetto in cui ho bisogno di scricchiolare interi grandi (come 3^361) con assoluta precisione e con la massima velocità possibile. C è il linguaggio più veloce con cui ho familiarità, quindi sto cercando di codificare la mia soluzione in quella lingua.

Il problema è che non sono stato in grado di trovare una buona implementazione di qualsiasi tipo di dati per rappresentare numeri interi senza limiti in C diversi dal codice sorgente di Python. Mi sta prendendo tempo per passare attraverso il codice e determinare ciò di cui ho bisogno.

Preferisco usare il codice testato di qualcun altro con un set completo di funzionalità (addizione, sottrazione, moltiplicazione, divisione, modulazione, elevazione a potenza, controllo di uguaglianza ... anche un'operazione bit-a-bit sarebbe dolce) rispetto a spendere le settimane che sarebbe portami anche a cominciare a ottenere la mia versione alla pari. Mentre sarebbe una grande esperienza di apprendimento, non è al centro del mio problema, e preferirei arrivare alla parte che mi interessa :)

Answer 1

Gnu MP fornisce una libreria bignum.

Answer 2

Un paio di persone hanno già menzionato GMP. Vorrei solo aggiungere che, almeno l'ultima volta che ho guardato, era abbastanza limitato a lavorare con gcc.

Se si desidera utilizzare altri compilatori, la coppia che si potrebbe considerare è NTL e MIRACL. Ho provato un po 'MIRACL e sembra funzionare abbastanza bene. Ho usato NTL un bel po 'di più, e mentre i grandi numeri interi sono più di una linea laterale per questo, li fa ancora abbastanza bene. Non pretende di essere veloce come GMP (e, in effetti, può usare GMP per fare operazioni di base), ma quando ho fatto qualche benchmarking minimo tra i due non ho trovato molte differenze significative (sebbene è passato abbastanza tempo da dubitare che sia più valido).

Answer 3

La libreria OpenSSL fornisce anche un'implementazione solida BigNum (<openssl/bn.h>).

Answer 4

Io uso MAPM che è una libreria di precisione (integer e floating point) arbitraria portatile.

Answer 5

Se si desidera standard ANSI C, ottenere il codice in Dave Hanson C Interfaces and Implementations. Molto chiaro e ben progettato.

Se le estensioni gcc e gcc sono OK, allora come altri hanno sottolineato la Gnu Multiprecision Library (GMP) è ben pensata e ampiamente utilizzata.

Answer 6

libtommath, da libtomcrypt, è probabilmente il più piccolo, il più semplice e il più veloce. (Divertente come quei 3 superlativi si incontrano quasi sempre ...) Se non riesci a trovare un upstream puoi ottenere il sorgente dall'albero sorgente ssh dropbear.