Ermittlung der effizientesten Wortgröße für die Implementierung von Bignums in C++ 11?

Question

Normalerweise werden Bignums mit mehreren Wörtern implementiert, aber ich möchte die Wortgröße so portabel wie möglich auswählen. Dies ist komplizierter als es scheint - std::uint64_t ist in vielen 32-Bit-Compilern verfügbar, aber std::uint32_t wäre wahrscheinlich eine bessere Wahl auf einem 32-Bit-Rechner. Also wäre die Versuchung dann, std :: size_t zu verwenden, aber es gibt keine Garantie für eine gegebene Architektur, dass std::size_t der effizienteste Typ für Arithmetik ist, zum Beispiel wäre std::size_t 32-Bits, aber std::uint64_t wäre immer noch die beste Wahl.

C++ 11 hat schnell/am wenigsten Typen verschiedener Größen definiert, aber es gibt keine Möglichkeit, die relative Leistung von ihnen abzufragen. Mir ist klar, dass es möglicherweise keine beste portable Antwort gibt, meine beste Schätzung ist jetzt, auf std::size_t voreinzustellen und außergewöhnliche Architekturen zur Konfigurationszeit zu entdecken. Aber vielleicht gibt es einen besseren Weg?

Answer 1

Der wirkliche Schlüssel, der bignums effizient implementiert, ist, dass Sie eine sich erweiternde Multiplikation benötigen, die Ihnen 2x so viele Bits wie Ihre grundlegende Wortgröße gibt. Daher können Sie uint64_t nur als Basiswortgröße verwenden, wenn Ihre Plattform ein 128-Bit-Multiplikationsergebnis unterstützt. Die Größe der Zeiger auf Ihrer Maschine ist weitgehend irrelevant.

Wenn Sie wirklich die effizienteste Implementierung wünschen, die so portabel wie möglich ist, sollten Sie die Wortgröße zur Kompilierzeit auswählbar machen. Dann haben Sie ein Autoconfig-Skript, das (versucht) den Code mit verschiedenen Wortgrößen erstellt und die Ergebnisse dieser Builds auf Korrektheit und Geschwindigkeit testet.

#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 

Verwendung WORD(WORD_SIZE) und WORD(X2(WORD_SIZE)) in Ihrem Code und kompilieren mit
-DWORD_SIZE=8 oder 16 oder 32 oder 64