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

abi, c++, c++11, integer, portability

Solution

The real key implementing bignums efficiently is that you need to have a widening multiply that gives you 2x as many bits as your basic word size. So you can only use uint64_t as your basic word size if your platform supports a 128 bit multiply result. The size of pointers on your machine is largely irrelevant.

If you really want the most efficient implementation that is as portable as possible, you should make the word size selectable at compile time. Then have an autoconfig script that (attempts to) build the code with various different word sizes and tests the results of those 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`

Problem

Typically bignums are implemented by using multiple words, but I'd like to pick the word size as portably as possible. This is more tricky than it might seem -- `std::uint64_t` is available in many 32-bit compilers, but `std::uint32_t` would probably be a better choice on a 32-bit machine. So the temptation then would be to use std::size_t, but there's no guarantee for a given architecture that `std::size_t` is the most efficient type for arithmetic, for example on the new x32 Linux ABI `std::size_t` would be 32-bits but `std::uint64_t` would still be the best choice. C++11 has fast/least types of various sizes defined, but it doesn't give any way of querying the relative performance of them. I realize there may be no best portable answer, my best guess now is to default to `std::size_t` and detect exceptional architectures at configure time. But maybe there's a better way?

Original source