Adaptive precision in Newton’s Method

This describes a way to improve the performance of a BigDecimal based implementation of Newton’s Method
by adapting the precision for every iteration to the maximum precision that is actually possible at this step.

As showcase I have picked the implementation of Newton’s Method to calculate the natural logarithm of a BigDecimal value with a determined precision.

The source code is available on github: big-math.

Here the mathematical formulation of the algorithm:

\(\require{AMSmath}\)
\(\displaystyle y_0 = \operatorname{Math.log}(x),\)
\(\displaystyle y_{i+1} = y_i + 2 \frac{x – e^{y_i} }{ x + e^{y_i}},\)
\(\displaystyle \ln{x} = \lim_{i \to \infty} y_i\)

Here a straightforward implementation:

private static final BigDecimal TWO = valueOf(2);

public static BigDecimal logUsingNewtonFixPrecision(BigDecimal x, MathContext mathContext) {
	if (x.signum() <= 0) {
		throw new ArithmeticException("Illegal log(x) for x <= 0: x = " + x);
	}

	MathContext mc = new MathContext(mathContext.getPrecision() + 4, mathContext.getRoundingMode());
	BigDecimal acceptableError = BigDecimal.ONE.movePointLeft(mathContext.getPrecision() + 1);
	
	BigDecimal result = BigDecimal.valueOf(Math.log(x.doubleValue()));
	BigDecimal step;
	
	do {
		BigDecimal expY = BigDecimalMath.exp(result, mc); // available on https://github.com/eobermuhlner/big-math
		step = TWO.multiply(x.subtract(expY, mc), mc).divide(x.add(expY, mc), mc);
		result = result.add(step);
	} while (step.abs().compareTo(acceptableError) > 0);

	return result.round(mathContext);
}

The MathContext mc is created with a precision of 4 digits more than the output is expected to have.
All calculations are done with this MathContext and therefore with the full precision.

The result is correct but we can improve the performance significantly be adapting the precision for every iteration.

The initial approximation uses Math.log(x.doubleValue()) which has a precision of about 17 significant digits.

We can expect that the precision triples with every iteration so it does not make sense to calculate with a higher precision than necessary.

Here the same implementation with a temporary MathContext that is recreated with a different precision every iteration.

public static BigDecimal logUsingNewtonAdaptivePrecision(BigDecimal x, MathContext mathContext) {
	if (x.signum() <= 0) {
		throw new ArithmeticException("Illegal log(x) for x <= 0: x = " + x);
	}

	int maxPrecision = mathContext.getPrecision() + 4;
	BigDecimal acceptableError = BigDecimal.ONE.movePointLeft(mathContext.getPrecision() + 1);
	
	BigDecimal result = BigDecimal.valueOf(Math.log(x.doubleValue()));
	int adaptivePrecision = 17;
	BigDecimal step = null;
	
	do {
		adaptivePrecision = adaptivePrecision * 3;
		if (adaptivePrecision > maxPrecision) {
			adaptivePrecision = maxPrecision;
		}
		MathContext mc = new MathContext(adaptivePrecision, mathContext.getRoundingMode());
		
		BigDecimal expY = BigDecimalMath.exp(result, mc); // available on https://github.com/eobermuhlner/big-math
		step = TWO.multiply(x.subtract(expY, mc), mc).divide(x.add(expY, mc), mc);
		result = result.add(step);
	} while (adaptivePrecision < maxPrecision || step.abs().compareTo(acceptableError) > 0);

	return result.round(mathContext);
}

The performance comparison between the two implementations is impressive.
The following chart shows the time in nanoseconds it takes to calculate the log() of values of x in the range from 0 to 1 with a precision of 300 digits.

Here some more charts to show the performance improvements of the adaptive precision technique applied to different approximative implementations:

This method can only be applied to approximative methods that improve the result with every iteration and discard the previous result, such as Newton’s Method.

It does obviously not work on methods that accumulate the results of each iteration to calculate the final result, such as Taylor series which add the terms.