Is there a faster way to convert a hexadecimal fractional part to a decimal one?

Question

I wrote a program that generates digits of pi in hexadecimal. Every so often, at benchmark values, I would like to convert the hexadecimal value I have into a decimal one and save it to a file. Currently I am using BigDecimal to do that math with this code:

private static String toDecimal(String hex) {
    String rawHex = hex.replace(".", "");
    BigDecimal base = new BigDecimal(new BigInteger(rawHex, 16));
    BigDecimal factor = new BigDecimal(BigInteger.valueOf(16).pow(rawHex.length() - 1));
    BigDecimal value = base.divide(factor);
    return value.toPlainString().substring(0, hex.length());
}

Note that this method will only work for hexadecimal values with one digit in the integral part, pi included, do not copy and paste this for general use.

So this code works fine, but for the latest benchmark, 2.5m digits, the conversion took 11.3 hours to complete.

Is there any faster way to do this manually?

I tried dividing the first decimal place by 16, the second by 16^2, etc but this would quickly get out of hand. Maybe some way of bitshifting the digits back to keep the divisor low? But potentially the n+1, n+2, n+3, etc digits need to be processed to get the correct value for n.

Answer 1

First, I believe your function toDecimal is wrong as it doesn't correctly convert input ".1a" (it's off by a factor of 16), for example, and throws an exception for input ".800". The third line should be:

BigDecimal factor = new BigDecimal(BigInteger.valueOf(16).pow(rawHex.length()));

The exception arises from:

return value.toPlainString().substring(0, hex.length());

The converted value could be shorter than the input value and you get a java.lang.StringIndexOutOfBoundsException.

Moving on:

In truth I have not benchmarked this against your current method; I just offer this as "food for thought." Here I am doing the multiplications as a child is taught to do it in school and in your case we have a large loop just to produce one digit. But if you could somehow adapt this to use BigDecimal (it's not clear how you would) it might be quicker than your current approach (what's really needed is a BigHexadecimal class).

It can be observed that converting a fraction from one base to another can be done using multiplications. In this case we have the following hexadecimal fraction (we can ignore the integer portion, which is 3 when converting pi):

.h₁h₂h₃h₄ ... h_n

where h_n is the n^th hexadecimal "nibble".

We wish to convert the above to the following decimal fraction:

.d₁d₂d₃d₄ ... d_n

where d_n is the n^th decimal digit.

If we were to multiply both quantities by 10, we would get:

h^'₁.h^'₂h^'₃h^'₄ ... h^'_n
The primes (^`) denote that we have completely new hexadecimal nibble values following the multiplication.

and

d₁.d₂d₃d₄ ... d_n
The multiplication by 10 just shifts the decimal fraction one place to the left.

We must note that the quantities to the left of the decimal point must be equal, i.e. d₁ == h^'₁. Thus we repeatedly multiply our hexadecimal fraction by 10 and each time we do we take the integer portion as the next decimal digit for our conversion. We repeat this until either our new hexadecimal fraction becomes 0 or some arbitrary number of decimal digits have been produced:

See Java Demo

class Test {

    private static String toDecimal(String hex, int numberDigits) {
        /* converts a string such as "13.1a" in base 16 to "19.1015625" in base 10 */
        int index = hex.indexOf('.');
        assert index != -1;
        StringBuilder decimal = new StringBuilder((index == 0) ? "" : String.valueOf(Integer.parseInt(hex.substring(0, index), 16)));
        decimal.append('.');
        int l = hex.length() - index - 1;
        assert l >= 1;
        int firstIndex = index + 1;
        int hexDigits[] = new int[l];
        for (int i = 0; i < l; i++) {
            hexDigits[i] = Integer.parseInt(hex.substring(i + firstIndex, i + firstIndex + 1), 16);
        }
        while (numberDigits != 0 && l != 0) {
            int carry = 0;
            boolean allZeroes = true;
            for (int i = l - 1; i >= 0; i--) {
                int value = hexDigits[i] * 10 + carry;
                if (value == 0 && allZeroes) {
                    l = i;
                }
                else {
                    allZeroes = false;
                    carry = (int)(value / 16);
                    hexDigits[i] = value % 16;
                }
            }
            numberDigits--;
            if (carry != 0 || (numberDigits != 0 && l != 0))
                decimal.append("0123456789".charAt(carry));
        }
        return decimal.toString();
    }

    public static void main(String[] args) {
        System.out.println(toDecimal("13.1a", 15));
        System.out.println(toDecimal("13.8", 15));
        System.out.println(toDecimal("13.1234", 15));
    }

}

Prints:

19.1015625
19.5
19.07110595703125