15.6.2 Radix to Binary

This section needs to be rewritten, it currently describes the algorithms used before GMP 4.3.

Conversions from a power-of-2 radix into binary use a simple and fast O(N) bitwise concatenation algorithm.

Conversions from other radices use one of two algorithms. Sizes below SET_STR_PRECOMPUTE_THRESHOLD use a basic O(N^2) method. Groups of n digits are converted to limbs, where n is the biggest power of the base b which will fit in a limb, then those groups are accumulated into the result by multiplying by b^n and adding. This saves multi-precision operations, as per Knuth section 4.4 part E (see section References). Some special case code is provided for decimal, giving the compiler a chance to optimize multiplications by 10.

Above SET_STR_PRECOMPUTE_THRESHOLD a sub-quadratic algorithm is used. First groups of n digits are converted into limbs. Then adjacent limbs are combined into limb pairs with x*b^n+y, where x and y are the limbs. Adjacent limb pairs are combined into quads similarly with x*b^(2n)+y. This continues until a single block remains, that being the result.

The advantage of this method is that the multiplications for each x are big blocks, allowing Karatsuba and higher algorithms to be used. But the cost of calculating the powers b^(n*2^i) must be overcome. SET_STR_PRECOMPUTE_THRESHOLD usually ends up quite big, around 5000 digits, and on some processors much bigger still.

SET_STR_PRECOMPUTE_THRESHOLD is based on the input digits (and tuned for decimal), though it might be better based on a limb count, so as to be independent of the base. But that sort of count isn’t used by the base case and so would need some sort of initial calculation or estimate.

The main reason SET_STR_PRECOMPUTE_THRESHOLD is so much bigger than the corresponding GET_STR_PRECOMPUTE_THRESHOLD is that mpn_mul_1 is much faster than mpn_divrem_1 (often by a factor of 5, or more).

This document was generated on March 31, 2014 using texi2html 5.0.