Base conversion for array of fractional places
-
02-07-2021 - |
Вопрос
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:
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
There is a suggested algorithm, which is worded as such:
for (i < precisionB):
- Keep a carry, initialize to 0.
- From RIGHT to LEFT
a. x = multiply the ith digit by baseB and add the carry
b. the new ith digit is x % baseA
c. carry = x / baseA- output[i] = carry
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 {1, 3, 6, 2, 5}
. An input of {0, 1}
in base 2 will properly return {2, 5}
in base 10.
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?
Here is my code:
public static int[] convertBase(int[] digits, int baseA,
int baseB, int precisionB) {
if (baseA < 2 | baseB < 2 | precisionB < 1) {
return null;
}
int[] input = digits.clone();
int[] output = new int[precisionB];
int carry = 0;
int j;
int x;
for (int i = 1; i <= precisionB; i++) {
j = precisionB - i;
if (input[j] >= baseA | input[j] < 0) {
return null;
}
x = (input[j] * baseB) + carry;
input[j] = x % baseA;
carry = x / baseA;
output[j] = carry;
}
return output;
}
This is from MIT's 6.005 course, problem set 1.
Решение
I eventually figured it out. The solution is that you must loop over all digits of the input array for each digit of the output. Here's the code in Java:
public static int[] convertBase(int[] digits, int baseA,
int baseB, int precisionB) {
if (baseA < 2 | baseB < 2 | precisionB < 1) {
return null;
}
int[] input = digits.clone();
int[] output = new int[precisionB];
int carry;
int j;
int x;
for (int i = 1; i <= precisionB; i++) {
carry = 0;
for (int k = 0; k < input.length; k++) {
j = input.length - 1 - k;
if (input[j] >= baseA | input[j] < 0) {
return null;
}
x = (input[j] * baseB) + carry;
input[j] = x % baseA;
carry = x / baseA;
}
output[i-1] = carry;
}
return output;
}