Determining the most efficient word size for implementing bignums in C ++ 11?

Question

Usually bignums are implemented using a few words, but I would like to choose the word size as portable as possible. This is more complicated than it might seem - std::uint64_t is available in many 32-bit compilers, but std::uint32_t is probably the best choice on a 32-bit machine. Therefore, it would be tempting to use std :: size_t, but there is no guarantee for this architecture that std::size_t is the most efficient type for arithmetic, for example, on the new x32 Linux ABI, std::size_t will be 32-bit, but std::uint64_t would still be a better choice.

C ++ 11 has the fastest / smallest types of certain sizes, but it does not provide any way to query relative performance. I understand that there cannot be a better portable answer, now I prefer std::size_t by default and detect exceptional architectures during setup. But maybe there is a better way?

Answer 1

The real key to implementing bignums effectively is that you need to increase the multiplication, which gives you 2x as many times as your main word size. Thus, you can use uint64_t as the main word size if your platform supports a 128-bit multiplication result. The size of the pointers on your machine is largely irrelevant.

If you really want the most efficient implementation to be as portable as possible, you must make the word size selected at compile time. Then use an autoconfig script that (tries) to build code with different word sizes and checks the results of these builds for correctness and speed.

 #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 

use WORD(WORD_SIZE) and WORD(X2(WORD_SIZE)) in your code and compile with
-DWORD_SIZE=8 or 16 or 32 or 64