title: Base conversion for array of fractional places
body: <p>I am trying to implement an algorithm to convert an array of integers, which represent the digits of the fractional part of a number, from one base to another.  In other words:</p>
  
  <pre><code>int[] input = {0, 0, 1, 0, 1}; // 0.00101 in base 2
  int[] output = convertBase(input, 2, 10, 5); // convertBase(input, fromBase, toBase, precision)
  output == {1, 5, 6, 2, 5}; // .15625 in base 10
  </code></pre>
  
  <p>There is a suggested algorithm, which is worded as such:</p>
  
  <blockquote>
    <p>for (i &lt; precisionB):</p>
    
    <blockquote>
      <p><ol>
      <li>Keep a carry, initialize to 0.</li>
      <li>From RIGHT to LEFT</p>
      
      <blockquote>
        <p>a. x = multiply the ith digit by baseB and add the carry
        <br/>b. the new ith digit is x % baseA
        <br/>c. carry = x / baseA</li>
        <li>output[i] = carry</li>
        </ol></p>
      </blockquote>
    </blockquote>
  </blockquote>
  
  <p>But when I implement this, the second digit is always off by a bit for arrays that are longer than 3 digits.  For the above example, it'll return <code>{1, 3, 6, 2, 5}</code>.  An input of <code>{0, 1}</code> in base 2 will properly return <code>{2, 5}</code> in base 10.  </p>
  
  <p>I don't think I am properly understanding 2b.  It seems like you are already done with the ith digit in the input array, replacing it shouldn't matter?</p>
  
  <p>Here is my code:</p>
  
  <pre><code>public static int[] convertBase(int[] digits, int baseA,
                                  int baseB, int precisionB) {
      if (baseA &lt; 2 | baseB &lt; 2 | precisionB &lt; 1) {
          return null;
      }
      int[] input = digits.clone();
      int[] output = new int[precisionB];
      int carry = 0;
      int j;
      int x;
  
      for (int i = 1; i &lt;= precisionB; i++) {
          j = precisionB - i;
          if (input[j] &gt;= baseA | input[j] &lt; 0) {
              return null;
          }
          x = (input[j] * baseB) + carry;
          input[j] = x % baseA;
          carry = x / baseA;
          output[j] = carry;
      }
  
      return output;
  }
  </code></pre>
  
  <p>This is from <a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-005-elements-of-software-construction-fall-2011/" rel="nofollow">MIT's 6.005</a> course, problem set 1.</p>