Numerical Accuracy with Java Log Probability Implementation

Question

Sometimes, when you perform calculations with very low probabilities, using common data types, such as doubles, numerical inaccuracies cascade across several calculations and lead to incorrect results. Because of this, it is recommended to use logarithmic probabilities , which improve numerical stability. I implemented log probabilities in Java, and my implementation works, but has digital stability worse than using raw paired. What is wrong with my implementation? What is an accurate and efficient way to do many sequential low probability calculations in Java?

I cannot provide a neatly inclusive demonstration of this problem because inaccuracies are cascaded by many calculations. However, it is proven that there is a problem: this comment on the CodeForces contest fails due to numerical accuracy. Running test No. 7 and adding debugging prints clearly show that from 1774 numerical errors begin to cascade until the sum of the probabilities drops to 0 (when it should be 1). After replacing my Prob class with a simple wrapper two times, the same solution passes the tests .

My implementation of multiplication probabilities:

a * b = Math.log(a) + Math.log(b)

My implementation of the add:

a + b = Math.log(a) + Math.log(1 + Math.exp(Math.log(b) - Math.log(a)))

The stability problem is most likely contained in these two lines, but here is my whole implementation:

class Prob {

        /** Math explained: https://en.wikipedia.org/wiki/Log_probability
         *  Quick start:
         *      - Instantiate probabilities, eg. Prob a = new Prob(0.75)
         *      - add(), multiply() return new objects, can perform on nulls & NaNs.
         *      - get() returns probability as a readable double */

        /** Logarithmized probability. Note: 0% represented by logP NaN. */
        private double logP;

        /** Construct instance with real probability. */
        public Prob(double real) {
            if (real > 0) this.logP = Math.log(real);
            else this.logP = Double.NaN;
        }

        /** Construct instance with already logarithmized value. */
        static boolean dontLogAgain = true;
        public Prob(double logP, boolean anyBooleanHereToChooseThisConstructor) {
            this.logP = logP;
        }

        /** Returns real probability as a double. */
        public double get() {
            return Math.exp(logP);
        }

        @Override
        public String toString() {
            return ""+get();
        }

        /***************** STATIC METHODS BELOW ********************/

        /** Note: returns NaN only when a && b are both NaN/null. */
        public static Prob add(Prob a, Prob b) {
            if (nullOrNaN(a) && nullOrNaN(b)) return new Prob(Double.NaN, dontLogAgain);
            if (nullOrNaN(a)) return copy(b);
            if (nullOrNaN(b)) return copy(a);

            double x = a.logP;
            double y = b.logP;
            double sum = x + Math.log(1 + Math.exp(y - x));
            return new Prob(sum, dontLogAgain);
        }

        /** Note: multiplying by null or NaN produces NaN (repping 0% real prob). */
        public static Prob multiply(Prob a, Prob b) {
            if (nullOrNaN(a) || nullOrNaN(b)) return new Prob(Double.NaN, dontLogAgain);
            return new Prob(a.logP + b.logP, dontLogAgain);
        }

        /** Returns true if p is null or NaN. */
        private static boolean nullOrNaN(Prob p) {
            return (p == null || Double.isNaN(p.logP));
        }

        /** Returns a new instance with the same value as original. */
        private static Prob copy(Prob original) {
            return new Prob(original.logP, dontLogAgain);
        }
    }

Answer 1

, Math.exp(z):

a + b = Math.log(a) + Math.log(1 + Math.exp(Math.log(b) - Math.log(a)))

z , double Math.exp(z). , , .

z >= 710, Math.exp(z) = Infinity

z <= -746, Math.exp(z) = 0

Math.exp y - x , x, . y x, , z , . , , (746, 710), , , 0, . , .

double x = Math.max(a.logP, b.logP);
double y = Math.min(a.logP, b.logP);
double sum = x + Math.log(1 + Math.exp(y - x));