What base would be more appropriate for my BigInte

Question

I have developed my own BigInteger library in C++, for didactic purpose, initially I have used base 10 and it works fine for add, subtract and multiply, but for some algorithms such as exponentiation, modular exponentiation and division it appears to be more appropriate use base 2.

I am thinking restart my project from scratch and I would know what base do you think is more adequate and why?. Thanks in advance!

Answer 1

A base the same as the word size on your target machine, where you have word x word = doubleword as a primitive. The primitive operations work out neatly in terms of machine instructions.

Answer 2

A base 10 representation makes sense for a BigDecimal type, where you need to need to represent decimal fractions exactly (for financial calculations and the like).

I can't see much benefit to using a base 10 representation for a BigInteger. It makes string conversion really easy, but at the expense of making mathematical operations much more complicated. This doesn't seem like a good tradeoff in most cases.

Answer 3

If you look at most BigNum type libraries you will see that they are built on top of the existing "SmallNum" data types. These "SmallNum" data types (short, int, long, float, double, ...) are in binary for too many reasons to count. Rather than a vector of base 10 digits, your code will be much faster (much, much, much faster!) if work with a vector of (for example) unsigned ints.

This is one of those places where performance does count. Suppose you use a BigNum package to solve a problem that could be solved without resorting to BigNums. Even the best BigNum library will be much slower (much, much slower) than will a simplistic, non-BigNum approach. If you try to solve a problem that is beyond the bounds of the standard representations that performance penalty will make things even worse.

The best way to overcome this inherent penalty is to take as much advantage of the builtin types as you possibly can.