Java Arithmetic Coding - Finding Character Ranges

Question

I am trying to recreate a Java implementation of arithmetic coding as described in this link, under the section 'Arithmetic Coding: how it works': link

I am at the point where the individual symbols need to be assigned a range along a probability line. However, I am having some issues in creating the correct ranges. In my code shown below, this is carried out by setRanges(). The expected result should be this:

Character Ranges -

            0.0 - 0.09999999999999999
A           0.1 - 0.19999999999999999
B           0.2 - 0.29999999999999999
E           0.3 - 0.39999999999999999
G           0.4 - 0.49999999999999999
I           0.5 - 0.59999999999999999
L           0.6 - 0.79999999999999999
S           0.8 - 0.89999999999999999
T           0.9 - 0.99999999999999999

My current output is this:

Character Ranges -

            0.0 - 0.09999999999999999
A           0.1 - 0.2
B           0.2 - 0.30000000000000004
E           0.30000000000000004 - 0.4
G           0.4 - 0.5
I           0.5 - 0.6
L           0.6 - 0.8
S           0.8 - 0.9
T           0.9 - 1.0

I am not sure is there is a better way to code my method setRanges(), or whether this is simply the result of rounding errors.

Here is the class Range which simply contains a low and high float value:

public class Range {

    private double low, high;

    public Range(double low, double high) {
        this.low = low;
        this.high = high;
    }

    public String toString() {
        return low + " - " + high;
    }

}

The method:

import java.util.TreeMap;

    public static TreeMap<Character, Range> setRanges(TreeMap<Character, Double> treeMap) {
        TreeMap<Character, Range> rangeMap = new TreeMap<>();
        double currentValue;
        double previousValue = 0;
        double runningTotal = 0;

        for(Character key : treeMap.keySet()) {
            currentValue = treeMap.get(key) + runningTotal;
            rangeMap.put(key, new Range(previousValue, currentValue - 0.00000000000000001));
            previousValue = currentValue;
            runningTotal += treeMap.get(key);
        }
        return rangeMap;
    }

}

Answer 1

I think you need to use BigDecimal for that precision. With either 128 or no roudning option. See below:

double first = 1d;
double second = 0.00000000000000001d;

System.out.println("Db --> " + (first - second));

BigDecimal firstBd = new BigDecimal(first);
BigDecimal secondBd = new BigDecimal(second);
BigDecimal resultBd = firstBd.subtract(secondBd);

System.out.println("32 --> " + resultBd.round(MathContext.DECIMAL32));
System.out.println("64 --> " + resultBd.round(MathContext.DECIMAL64));
System.out.println("128--> " + resultBd.round(MathContext.DECIMAL128));
System.out.println("Unl--> " + resultBd);

Output is:

Db --> 1.0
32 --> 1.000000
64 --> 1.000000000000000
128--> 0.9999999999999999899999999999999993
Unl--> 0.9999999999999999899999999999999992845757594537807549147194381507675227382936355979836662299931049346923828125