title: Change of base for fractional numbers in O(N) time
body: <p>I apologize. This question is part of a programming assignment. We're asked to implement
  a method that changes a <em>fraction</em> f from base A to base B with P digits of precision. 
  The function has signature</p>
  
  <p><code>baseChanger(int[] f, int A, int B, int P)</code>.</p>
  
  <p>For example, the decimal 3.14159 has fraction 0.14159 and is represented as an array:</p>
  
  <pre><code>int[] frac = {1,4,1,5,9};
  </code></pre>
  
  <p>A fraction in base-16 -- 0.3BA07 -- would be written</p>
  
  <pre><code>int[] frac = {3,11,10,0,7};
  </code></pre>
  
  <p>The binary fraction 0.01 converted to a decimal fraction is 0.25, and a test of the conversion function would look like this:</p>
  
  <pre><code>int[] from = {0,1};
  int[] to = {2,5};
  
  @Test
      assertArrayEquals(to, baseChanger(from, 2, 10, 2));
  </code></pre>
  
  <p>This is the algorithm we were asked to implement: </p>
  
  <pre><code>/*      
   * for (i &lt; P) {
   *   1. Keep a carry, initialize to 0.
   *   2. From right to left:
   *      a. x = multiply the ith digit by B and add the carry
   *      b. the new ith digit is x % A
   *      c. carry = x / A
   *   3. output[i] = carry 
   * 
   * @param f The input array to translate. This array is not mutated.
   * @param A The base that the input array is expressed in.
   * @param B The base to translate into.
   * @param P The number of digits of precision the output should
   *                   have.
   * @return An array of size P expressing digits in B.
   */
  </code></pre>
  
  <p>So with "from" and "to" as above, this would mean doing the following:</p>
  
  <ol>
  <li><p>Create an array that can hold P digits:</p>
  
  <p>int[] output = new int[P]; // output = {0, 0}</p></li>
  <li><p>Take the rightmost digit of "from":</p>
  
  <p>{0, 1 &lt;== }</p></li>
  <li><p>Multiply that digit by B (10 here) and add the carry (zero, currently), and assign to x:</p>
  
  <p>x &lt;-- 1 x 10 + 0 = 10</p></li>
  <li><p><em>Replace</em> the rightmost digit (currently 1) with x mod A (2 here):</p>
  
  <p>{0, <strong>0</strong> &lt;== }</p></li>
  <li><p>Calculate the carry, which is x / A:</p>
  
  <p>carry &lt;-- 10 / 2 = 5</p></li>
  <li><p>Assign carry to the 0th slot in output:</p>
  
  <p>output[0] &lt;-- carry</p>
  
  <p>output: {<strong>5</strong> &lt;==, 0}</p></li>
  </ol>
  
  <p>This procedure is repeated once more, and output is now</p>
  
  <pre><code>output: {2,5}
  </code></pre>
  
  <p>But notice that the digits are in the wrong order and are output from <em>least significant</em> to <em>most significant</em>!</p>
  
  <p>Also, (more importantly), what would be done for a conversion from a decimal fraction like 0.3 to binary? Suppose you wanted, say, 12 digits of precision. There is no exact binary representation, of course, so what would you do here, especially since the least significant digits come out <em>first</em>? </p>
  
  <pre><code>from = {3}
  </code></pre>
  
  <p>I'm not sure where to start and would appreciate some advice. Remember that these numbers are fractions, not whole numbers and that the algorithm has to finish in <em>linear</em> time. </p>