<html lang="en">
<head>
<title>Radix to Binary - GNU MP 6.1.0</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="description" content="How to install and use the GNU multiple precision arithmetic library, version 6.1.0.">
<meta name="generator" content="makeinfo 4.13">
<link title="Top" rel="start" href="index.html#Top">
<link rel="up" href="Radix-Conversion-Algorithms.html#Radix-Conversion-Algorithms" title="Radix Conversion Algorithms">
<link rel="prev" href="Binary-to-Radix.html#Binary-to-Radix" title="Binary to Radix">
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
<!--
This manual describes how to install and use the GNU multiple precision
arithmetic library, version 6.1.0.

Copyright 1991, 1993-2015 Free Software Foundation, Inc.

Permission is granted to copy, distribute and/or modify this document under
the terms of the GNU Free Documentation License, Version 1.3 or any later
version published by the Free Software Foundation; with no Invariant Sections,
with the Front-Cover Texts being ``A GNU Manual'', and with the Back-Cover
Texts being ``You have freedom to copy and modify this GNU Manual, like GNU
software''.  A copy of the license is included in
*note GNU Free Documentation License::.-->
<meta http-equiv="Content-Style-Type" content="text/css">
<style type="text/css"><!--
  pre.display { font-family:inherit }
  pre.format  { font-family:inherit }
  pre.smalldisplay { font-family:inherit; font-size:smaller }
  pre.smallformat  { font-family:inherit; font-size:smaller }
  pre.smallexample { font-size:smaller }
  pre.smalllisp    { font-size:smaller }
  span.sc    { font-variant:small-caps }
  span.roman { font-family:serif; font-weight:normal; } 
  span.sansserif { font-family:sans-serif; font-weight:normal; } 
--></style>
</head>
<body>
<div class="node">
<a name="Radix-to-Binary"></a>
<p>
Previous:&nbsp;<a rel="previous" accesskey="p" href="Binary-to-Radix.html#Binary-to-Radix">Binary to Radix</a>,
Up:&nbsp;<a rel="up" accesskey="u" href="Radix-Conversion-Algorithms.html#Radix-Conversion-Algorithms">Radix Conversion Algorithms</a>
<hr>
</div>

<h4 class="subsection">15.6.2 Radix to Binary</h4>

<p><strong>This section needs to be rewritten, it currently describes the
algorithms used before GMP 4.3.</strong>

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

   <p>Conversions from other radices use one of two algorithms.  Sizes below
<code>SET_STR_PRECOMPUTE_THRESHOLD</code> 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 <a href="References.html#References">References</a>).  Some special case code is provided for decimal, giving
the compiler a chance to optimize multiplications by 10.

   <p>Above <code>SET_STR_PRECOMPUTE_THRESHOLD</code> 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.

   <p>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. 
<code>SET_STR_PRECOMPUTE_THRESHOLD</code> usually ends up quite big, around 5000 digits, and on
some processors much bigger still.

   <p><code>SET_STR_PRECOMPUTE_THRESHOLD</code> 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.

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

   </body></html>

