Determinare la dimensione della parola più efficiente per l'implementazione di bignum in C++ 11?

Question

In genere i bignum vengono implementati utilizzando più parole, ma mi piacerebbe scegliere la dimensione della parola il più portabile possibile. Questo è più difficile di quanto possa sembrare - std::uint64_t è disponibile in molti compilatori a 32 bit, ma std::uint32_t potrebbe essere una scelta migliore su un computer a 32 bit. Quindi la tentazione sarebbe quella di usare std :: size_t, ma non c'è garanzia per una data architettura che std::size_t sia il tipo più efficiente per l'aritmetica, ad esempio su the new x32 Linux ABIstd::size_t sarebbe a 32 bit ma std::uint64_t sarebbe comunque la scelta migliore.

C++ 11 ha definito i tipi veloci/minimi di varie dimensioni, ma non fornisce alcun modo per interrogare le relative prestazioni. Mi rendo conto che potrebbe non esserci la migliore risposta portatile, la mia migliore ipotesi ora è di default su std::size_t e rilevare architetture eccezionali al momento della configurazione. Ma forse c'è un modo migliore?

Answer 1

La vera chiave per implementare bignum in modo efficiente è che è necessario avere un moltiplicatore di ampliamento che fornisca un numero di bit pari a 2x della parola base. Quindi puoi usare uint64_t come dimensione della parola base solo se la tua piattaforma supporta un risultato di moltiplicazione a 128 bit. La dimensione dei puntatori sulla tua macchina è in gran parte irrilevante.

Se si desidera veramente l'implementazione più efficiente che sia il più portabile possibile, è necessario rendere selezionabile la dimensione della parola in fase di compilazione. Quindi avere uno script di autoconfig che (tenta di) creare il codice con varie dimensioni di parole diverse e verifica i risultati di tali build per correttezza e velocità.

#define WORD_(SIZE) std::uint ## SIZE ## _t 
#define WORD(SIZE)  WORD_(SIZE) 
#define X2_(SIZE)  X2_ ## SIZE 
#define X2(SIZE)  X2_(SIZE) 
#define X2_8   16 
#define X2_16   32 
#define X2_32   64 
#define X2_64   128 

uso WORD(WORD_SIZE) e WORD(X2(WORD_SIZE)) nel codice e compilare con
-DWORD_SIZE=8 o 16 o 32 o 64