Change of base for fractional numbers in O(N) time

Question

I apologize. This question is part of a programming assignment. We're asked to implement a method that changes a fraction f from base A to base B with P digits of precision. The function has signature

baseChanger(int[] f, int A, int B, int P).

For example, the decimal 3.14159 has fraction 0.14159 and is represented as an array:

int[] frac = {1,4,1,5,9};

A fraction in base-16 -- 0.3BA07 -- would be written

int[] frac = {3,11,10,0,7};

The binary fraction 0.01 converted to a decimal fraction is 0.25, and a test of the conversion function would look like this:

int[] from = {0,1};
int[] to = {2,5};

@Test
    assertArrayEquals(to, baseChanger(from, 2, 10, 2));

This is the algorithm we were asked to implement:

/*      
 * for (i < 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.
 */

So with "from" and "to" as above, this would mean doing the following:

1. Create an array that can hold P digits:

   int[] output = new int[P]; // output = {0, 0}

2. Take the rightmost digit of "from":

   {0, 1 <== }

3. Multiply that digit by B (10 here) and add the carry (zero, currently), and assign to x:

   x <-- 1 x 10 + 0 = 10

4. Replace the rightmost digit (currently 1) with x mod A (2 here):

   {0, 0 <== }

5. Calculate the carry, which is x / A:

   carry <-- 10 / 2 = 5

6. Assign carry to the 0th slot in output:

   output[0] <-- carry

   output: {5 <==, 0}

This procedure is repeated once more, and output is now

output: {2,5}

But notice that the digits are in the wrong order and are output from least significant to most significant!

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 first?

from = {3}

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 linear time.

Answer 1

Disclaimer: I think it finishes in O(N) time. I've added to the versatility of the algorithm. Moreover, Negative radixes are IMPRACTICAL

The following method converts a number in the decimal base to that mentioned in radix:

/**
 * This method returns an array with <code>precs</code> elements conating the
 * required fractional part in the base <code>radix</code>
 *
 * @param frac A <code>float</code> that contains the fractional part 
 * (and fractional part only!!) in decimal number system.
 * @param radix The base to which it has to be converted (must be (+) ve).
 * @param precs The number of digits required i.e. precision.
 * 
 * @return A <code>int[]</code> that contains the digits(eqivalent).
 */
public static int[] toRadix(float frac, int radix, int precs)
{
    if(radix < 2) return null;
    //Only fractional part is accepted here.
    frac = frac - (long)frac;  //Precautionary measure :-)
    int i, j;
    int[] res = new int[precs]; //For storing result.
    for(i = 0; i < precs && frac != 0; i++)
    {
        frac *= radix;
        res[i] = (int)frac;
        if((long)frac >= 1)
            frac = frac - (long)frac;
    }
    if(flag)
        return copy(res, i);
    return res;
}

The method that converts a number in base radix to decimal -- returns a float.

/**
 * This method returns a <code>float</code> that contains the equivalent of the
 * fraction in the other base in the parameter array, in decimal.
 * 
 * @param frac An <code>int[]</code> conatining only the fractional part.
 * @param radix The base of the fraction entered (must be (+) ve).
 * 
 * @return The equivalent decimal fraction as a <code>float</code>.
 */
public static float toDecimal(int[] frac, int radix)
{
    if(radix < 2) return null;
    float res = 0, fac = 1.0f/radix;
    int i, p = frac.length;
    for(i = 0; i < p; i++)
    {
        res += frac[i] * fac;        //or (float)Math.pow(radix, -i);
        fac/=radix;                  //would be fine as well.
    }
    return res;
}

Finally! The `baseChanger()` method

public static int[] baseChanger(int[] f, int A, int B, int P)
{
    if(A < 2) return null;
    if(B < 2) return null;
    return toRadix(toDecimal(f, A), B, P);
}

And the copy method:

private static int[] copy(int[] a, int index)
{
    index = index < a.length ? index : a.length;
    int b[] = new int[index];
    for(int i = 0; i < index; i++)
        b[i] = a[i];
    return b;
}

---

I have obtained the required level of generalization. The results:

1. The actual (correct) output:

   

2. The output of the above written code:

   

So, I guess that settles it! By the way, here are some tips:

1. Working with arrays instead of String can lead to several complications. For starters, the integral part of the float entered is difficult to deal with. This method is okay for the fractional part because we know where the loop is supposed to stop.

2. Using a String rules out the need for copying.

3. But your method has an upperhand : the upper limit for the radix is
   Integer.MAX_VALUE whereas that of the String approach is only 36 (0 to 9 and a to z) (though this is not quite a serious advantage as it has no practical application).

4. The most practical approach to changing the base of numbers is to first convert to decimal and then, converting that to the other base.

5. Using double would be better than using float as it improves accuracy.