(gmp.info.gz) Radix to Binary

Info Catalog

(gmp.info.gz) Binary to Radix

(gmp.info.gz) Radix Conversion Algorithms

 
 Radix to Binary
 ---------------
 
 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_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 ( References).  Some
 special case code is provided for decimal, giving the compiler a chance
 to optimize multiplications by 10.
 
    Above `SET_STR_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_THRESHOLD' usually ends up quite big, around 5000 digits, and
 on some processors much bigger still.
 
    `SET_STR_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_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 10, or more).
 

Info Catalog

(gmp.info.gz) Binary to Radix

(gmp.info.gz) Radix Conversion Algorithms