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

user_7427882 0
Viewed 572

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.

base hex algorithm java
2 Answers

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):

.h1h2h3h4 ... hn

where hn is the nth hexadecimal "nibble".

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

.d1d2d3d4 ... dn

where dn is the nth decimal digit.

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

h'1.h'2h'3h'4 ... h'n
The primes (`) denote that we have completely new hexadecimal nibble values following the multiplication.

and

d1.d2d3d4 ... dn
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. d1 == h'1. 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
user_28237190

Thank you to @Booboo for the solution to this problem. I improved on his code a little so it should work in every case. I wanted to post it here for future visitors.

/**
 * Converts a hex number string to a decimal number string.
 *
 * @param hex      The hex number string.
 * @param accuracy The number of decimal places to return in the decimal number string.
 * @return The decimal number string.
 */
public static String hexToDecimal(String hex, int accuracy) {
    if (!hex.matches("[0-9A-Fa-f.\\-]+") || (accuracy < 0)) {
        return "";
    }
    
    boolean negative = hex.startsWith("-");
    hex = hex.replaceAll("^-", "");
    String integral = hex.contains(".") ? hex.substring(0, hex.indexOf(".")) : hex;
    String fraction = hex.contains(".") ? hex.substring(hex.indexOf(".") + 1) : "";
    if (integral.contains("-") || fraction.contains(".") || fraction.contains("-")) {
        return "";
    }
    
    StringBuilder decimal = new StringBuilder();
    decimal.append(negative ? "-" : "");
    decimal.append(integral.isEmpty() ? "0" : new BigDecimal(new BigInteger(integral, 16)).toPlainString());
    if (fraction.isEmpty() || (accuracy == 0)) {
        return decimal.toString();
    }
    decimal.append(".");
    
    int numberDigits = accuracy;
    int length = Math.min(fraction.length(), numberDigits);
    int[] hexDigits = new int[numberDigits];
    Arrays.fill(hexDigits, 0);
    IntStream.range(0, length).boxed().parallel().forEach(i -> hexDigits[i] = Integer.parseInt(String.valueOf(fraction.charAt(i)), 16));
    
    while ((numberDigits != 0)) {
        int carry = 0;
        for (int i = length - 1; i >= 0; i--) {
            int value = hexDigits[i] * 10 + carry;
            carry = value / 16;
            hexDigits[i] = value % 16;
        }
        decimal.append(carry);
        numberDigits--;
    }
    return decimal.toString();
}

/**
 * Converts a hex number string to a decimal number string.
 *
 * @param hex The hex number string.
 * @return The decimal number string.
 * @see #hexToDecimal(String, int)
 */
public static String hexToDecimal(String hex) {
    String fraction = hex.contains(".") ? hex.substring(hex.indexOf(".") + 1) : "";
    return hexToDecimal(hex, fraction.length());
}

public static void main(String[] args) {
    //integer
    Assert.assertEquals("0", hexToDecimal("0"));
    Assert.assertEquals("1", hexToDecimal("1"));
    Assert.assertEquals("9", hexToDecimal("9"));
    Assert.assertEquals("15", hexToDecimal("F"));
    Assert.assertEquals("242", hexToDecimal("F2"));
    Assert.assertEquals("33190", hexToDecimal("81A6"));
    Assert.assertEquals("256", hexToDecimal("100"));
    Assert.assertEquals("1048576", hexToDecimal("100000"));
    Assert.assertEquals("5191557193152165532727847676938654", hexToDecimal("FFF6AA0322BC458D5D11A632099E"));
    Assert.assertEquals("282886881332428154466487121231991859970997056152877088222", hexToDecimal("B897A12C89896321C454A7DD9E150233CBB87A9F0233DDE"));
    Assert.assertEquals("-256", hexToDecimal("-100"));
    Assert.assertEquals("-144147542", hexToDecimal("-8978456"));
    Assert.assertEquals("-332651442596728389665499138728075237402", hexToDecimal("-FA42566214321CC67445D58EE874981A"));
    Assert.assertEquals("33190", hexToDecimal("81a6"));

    //decimal
    Assert.assertEquals("0.10", hexToDecimal("0.1a"));
    Assert.assertEquals("0.5", hexToDecimal("0.8"));
    Assert.assertEquals("0.0711", hexToDecimal("0.1234"));
    Assert.assertEquals("0.528966901", hexToDecimal("0.876A5FF4A"));
    Assert.assertEquals("-0.528966901", hexToDecimal("-0.876A5FF4A"));
    Assert.assertEquals("-0.00000000", hexToDecimal("-0.00000001"));
    Assert.assertEquals("-0.62067648792835838863907521427468", hexToDecimal("-0.9EE4A7810C666FF7453D06A44621030E"));
    Assert.assertEquals("0.528966901", hexToDecimal("0.876a5ff4a"));
    Assert.assertEquals("0.528966901", hexToDecimal(".876a5ff4a"));
    Assert.assertEquals("-0.528966901", hexToDecimal("-.876a5ff4a"));

    //combined
    Assert.assertEquals("15.33693", hexToDecimal("F.56412"));
    Assert.assertEquals("17220744.33934412", hexToDecimal("106C488.56DF41A2"));
    Assert.assertEquals("282886881332428154466487121231991859970997056152877088222.62067648792835838863907521427468", hexToDecimal("B897A12C89896321C454A7DD9E150233CBB87A9F0233DDE.9EE4A7810C666FF7453D06A44621030E"));
    Assert.assertEquals("-17220744.33934412", hexToDecimal("-106C488.56DF41A2"));
    Assert.assertEquals("-282886881332428154466487121231991859970997056152877088222.62067648792835838863907521427468", hexToDecimal("-B897A12C89896321C454A7DD9E150233CBB87A9F0233DDE.9EE4A7810C666FF7453D06A44621030E"));
    Assert.assertEquals("-17220744.33934412", hexToDecimal("-106c488.56df41a2"));
    Assert.assertEquals("3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808", hexToDecimal("3.243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89452821E638D01377BE5466CF34E90C6CC0AC29B7C97"));

    //accuracy
    Assert.assertEquals("-0.00000", hexToDecimal("-0.00000001", 5));
    Assert.assertEquals("-0.000000000232830", hexToDecimal("-0.00000001", 15));
    Assert.assertEquals("-0", hexToDecimal("-0.00000001", 0));
    Assert.assertEquals("282886881332428154466487121231991859970997056152877088222.5", hexToDecimal("B897A12C89896321C454A7DD9E150233CBB87A9F0233DDE.9EE4A7810C666FF7453D06A44621030E", 1));
    Assert.assertEquals("3.14", hexToDecimal("3.243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89452821E638D01377BE5466CF34E90C6CC0AC29B7C97", 2));
    Assert.assertEquals("3.1415926535", hexToDecimal("3.243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89452821E638D01377BE5466CF34E90C6CC0AC29B7C97", 10));
    Assert.assertEquals("3.1415926535897932384626433", hexToDecimal("3.243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89452821E638D01377BE5466CF34E90C6CC0AC29B7C97", 25));

    //invalid
    Assert.assertEquals("", hexToDecimal("0.00000.001"));
    Assert.assertEquals("", hexToDecimal("0.00000-001"));
    Assert.assertEquals("", hexToDecimal("156-081.00000001"));
    Assert.assertEquals("", hexToDecimal("hello"));
    Assert.assertEquals("", hexToDecimal("9g"));
    Assert.assertEquals("", hexToDecimal("9G"));
    Assert.assertEquals("", hexToDecimal("546.FDA", -1));
    Assert.assertEquals("", hexToDecimal("546.FDA", -999));
}
user_74278820
Related