This is an automated email from the ASF dual-hosted git repository.
pjfanning pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/poi.git
The following commit(s) were added to refs/heads/trunk by this push:
new cfc76edcc3 IRR: fall back to bracketed Newton-Raphson when the
iteration diverges (bug 64137 follow-up) (#1216)
cfc76edcc3 is described below
commit cfc76edcc3a416cadb006083d53c54c285eb62b5
Author: falhenaki <[email protected]>
AuthorDate: Sun Aug 16 06:27:38 2026 -0400
IRR: fall back to bracketed Newton-Raphson when the iteration diverges (bug
64137 follow-up) (#1216)
* Bug 64137 follow-up: add bracketed Newton-Raphson fallback for divergent
IRR
Plain Newton-Raphson in Irr.irr() can converge to financially
meaningless rates at or below -100%, or return NaN for cash flows that
have an ordinary root. The fix for bug 64137 raised the iteration cap
from 20 to 1000, which was enough for that report but left the
divergence itself in place.
Keep the historical loop as an unchanged fast path so existing results
stay identical. Only when it returns NaN or a rate <= -1, fall back to
a bracketed Newton-Raphson with bisection safeguard over (-1, 10000].
The 'returning NaN' warn logs move to the fallback, where a NaN really
is final.
* Bug 64137 follow-up: address review comments on the bracketed fallback
- comment that the coarse bracket-grid tail is intentional (only paired
roots inside one gap can be missed, never a single root)
- comment on the result > -1 guard in irr() explaining when the
fallback runs and why a converged rate above -100% is returned as-is
- harden the rtsafe loop against NPV overflow in the sliver next to -1:
a non-finite f or df now forces a bisection step instead of feeding
Newton inf/inf, and a NaN NPV no longer moves a bracket endpoint
(its sign is unknown; moving one could break the bracket invariant).
For any iterate where f and df are finite, behaviour is unchanged.
---------
Co-authored-by: falhenaki <[email protected]>
---
.../org/apache/poi/ss/formula/functions/Irr.java | 221 +++++++++++++++++++--
.../apache/poi/ss/formula/functions/TestIrr.java | 27 +++
2 files changed, 234 insertions(+), 14 deletions(-)
diff --git a/poi/src/main/java/org/apache/poi/ss/formula/functions/Irr.java
b/poi/src/main/java/org/apache/poi/ss/formula/functions/Irr.java
index d1805966c5..e97d8bfede 100644
--- a/poi/src/main/java/org/apache/poi/ss/formula/functions/Irr.java
+++ b/poi/src/main/java/org/apache/poi/ss/formula/functions/Irr.java
@@ -17,6 +17,8 @@
package org.apache.poi.ss.formula.functions;
+import java.util.Arrays;
+
import org.apache.logging.log4j.Logger;
import org.apache.poi.logging.PoiLogManager;
import org.apache.poi.ss.formula.eval.ErrorEval;
@@ -37,6 +39,32 @@ public final class Irr implements Function {
private static final double ABSOLUTE_ACCURACY = 1E-7;
private static final Logger LOGGER = PoiLogManager.getLogger(Irr.class);
+ // Rates at or below -100% are meaningless, and NPV blows up as the rate
+ // approaches -1. The grid starts just above -1 and is dense there, since
+ // roots pushed toward -100% by extreme cash flows are exactly the ones
+ // plain Newton-Raphson used to miss. The coarse tail (100, 1000, 10000)
+ // is intentional: a single root between two grid points still flips the
+ // sign of NPV at the endpoints and is found; only an even number of
+ // roots inside one gap can be missed, and cash flows with paired roots
+ // between 10,000% and 1,000,000% are pathological.
+ private static final double[] BRACKET_GRID;
+ static {
+ BRACKET_GRID = new double[8 + 20 + 7];
+ int n = 0;
+ for (int e = 9; e >= 2; e--) {
+ BRACKET_GRID[n++] = -1 + Math.pow(10, -e);
+ }
+ for (int i = -9; i <= 10; i++) {
+ BRACKET_GRID[n++] = i / 10.0;
+ }
+ BRACKET_GRID[n++] = 2.0;
+ BRACKET_GRID[n++] = 3.0;
+ BRACKET_GRID[n++] = 5.0;
+ BRACKET_GRID[n++] = 10.0;
+ BRACKET_GRID[n++] = 100.0;
+ BRACKET_GRID[n++] = 1000.0;
+ BRACKET_GRID[n] = 10000.0;
+ }
public ValueEval evaluate(final ValueEval[] args, final int srcRowIndex,
final int srcColumnIndex) {
if(args.length == 0 || args.length > 2) {
@@ -72,21 +100,22 @@ public final class Irr implements Function {
/**
- * Calculates IRR using the Newton-Raphson Method.
- * <p>
- * Starting with the guess, the method cycles through the calculation
until the result
- * is accurate within 0.00001 percent. If IRR can't find a result that
works
- * after 1000 tries, the {@code Double.NaN} is returned.
- *
- * <p>
- * The implementation is inspired by the NewtonSolver from the Apache
Commons-Math library,
- * @see <a href="http://commons.apache.org">http://commons.apache.org</a>
- *
+ * Calculates IRR in two stages. First, plain Newton-Raphson from the
+ * guess; for compatibility this is exactly the historical algorithm, so
+ * every cash flow it already solved keeps its bit-identical result. If it
+ * fails to converge (as in bug #64137, where the iteration overshoots to
+ * a rate just above -100% and cannot recover) or converges to a
+ * meaningless rate at or below -100%, the method falls back to a
+ * bracketed Newton-Raphson (the classic "rtsafe" safeguard): the NPV
+ * function is bracketed between two rates of opposite NPV sign, then
+ * Newton-Raphson steps are taken as long as they stay inside the bracket
+ * and converge fast enough, with bisection otherwise. The fallback cannot
+ * diverge and cannot return a rate at or below -100%.
*
* @param values the income values.
* @param guess the initial guess of irr.
* @return the irr value. The method returns {@code Double.NaN}
- * if the maximum iteration count is exceeded
+ * if no rate with zero NPV could be found
*
* @see <a
href="http://en.wikipedia.org/wiki/Internal_rate_of_return#Numerical_solution">
*
http://en.wikipedia.org/wiki/Internal_rate_of_return#Numerical_solution</a>
@@ -94,6 +123,25 @@ public final class Irr implements Function {
* http://en.wikipedia.org/wiki/Newton%27s_method</a>
*/
public static double irr(double[] values, double guess) {
+ double result = newtonIrr(values, guess);
+ // Any finite rate above -100% is a genuinely converged root of NPV,
+ // so it is returned as-is for backward compatibility; the fallback
+ // runs only when the historical algorithm diverged (NaN) or landed
+ // on a financially meaningless root at or below -100%.
+ if (!Double.isNaN(result) && result > -1) {
+ return result;
+ }
+ return bracketedIrr(values, guess);
+ }
+
+ /**
+ * The historical POI algorithm: unguarded Newton-Raphson from the guess.
+ * Kept unchanged as the fast path so existing results stay identical.
+ * Returns {@code Double.NaN} when it diverges; the "returning NaN" warn
+ * logs now live in {@link #bracketedIrr(double[], double)}, where a NaN
+ * really is final.
+ */
+ private static double newtonIrr(double[] values, double guess) {
double x0 = guess;
@@ -103,7 +151,6 @@ public final class Irr implements Function {
final double factor = 1.0 + x0;
double denominator = factor;
if (denominator == 0) {
- LOGGER.atWarn().log("Returning NaN because IRR has found an
denominator of 0");
return Double.NaN;
}
@@ -118,7 +165,6 @@ public final class Irr implements Function {
// the essence of the Newton-Raphson Method
if (fDerivative == 0) {
- LOGGER.atWarn().log("Returning NaN because IRR has found an
fDerivative of 0");
return Double.NaN;
}
double x1 = x0 - fValue/fDerivative;
@@ -130,7 +176,154 @@ public final class Irr implements Function {
x0 = x1;
}
// maximum number of iterations is exceeded
- LOGGER.atWarn().log("Returning NaN because IRR has reached max number
of iterations allowed: {}", MAX_ITERATION_COUNT);
return Double.NaN;
}
+
+ /**
+ * Bracketed Newton-Raphson with bisection safeguard, used when
+ * {@link #newtonIrr(double[], double)} diverges or leaves the domain.
+ */
+ private static double bracketedIrr(double[] values, double guess) {
+ double[] bracket = findBracket(values, guess);
+ if (bracket == null) {
+ LOGGER.atWarn().log(
+ "Returning NaN because IRR found no rate in (-1, 10000]
where NPV changes"
+ + " sign");
+ return Double.NaN;
+ }
+ double lo = bracket[0];
+ double flo = bracket[1];
+ double hi = bracket[2];
+ if (lo == hi) {
+ return lo;
+ }
+ // orient the bracket so that npv(lo) < 0 < npv(hi)
+ if (flo > 0) {
+ double t = lo;
+ lo = hi;
+ hi = t;
+ }
+ double rts = (Math.min(lo, hi) < guess && guess < Math.max(lo, hi))
+ ? guess : 0.5 * (lo + hi);
+ double dxold = Math.abs(hi - lo);
+ double dx = dxold;
+ double f = npv(values, rts);
+ double df = npvDerivative(values, rts);
+ for (int i = 0; i < MAX_ITERATION_COUNT; i++) {
+ // Newton is unusable when NPV or its derivative overflowed (an
+ // iterate in the overflow sliver next to -1), when the derivative
+ // is 0, when the step would leave the bracket, or when it is not
+ // converging fast enough (would not halve the bracket).
+ boolean newtonUnusable = !Double.isFinite(f) ||
!Double.isFinite(df)
+ || df == 0
+ || ((rts - hi) * df - f) * ((rts - lo) * df - f) > 0
+ || Math.abs(2.0 * f) > Math.abs(dxold * df);
+ if (newtonUnusable) {
+ // bisection step
+ dxold = dx;
+ dx = 0.5 * (hi - lo);
+ rts = lo + dx;
+ if (lo == rts) {
+ return rts;
+ }
+ } else {
+ // Newton-Raphson step
+ dxold = dx;
+ dx = f / df;
+ double tmp = rts;
+ rts -= dx;
+ if (tmp == rts) {
+ return rts;
+ }
+ }
+ if (Math.abs(dx) < ABSOLUTE_ACCURACY) {
+ return rts;
+ }
+ f = npv(values, rts);
+ df = npvDerivative(values, rts);
+ // a NaN NPV (indeterminate inf - inf next to -1) must not move
+ // either end: its sign is unknown, and a wrong move would break
+ // the bracket invariant npv(lo) < 0 < npv(hi)
+ if (f < 0) {
+ lo = rts;
+ } else if (f > 0) {
+ hi = rts;
+ }
+ }
+ LOGGER.atWarn().log(
+ "Returning NaN because IRR has reached max number of
iterations allowed: {}",
+ MAX_ITERATION_COUNT);
+ return Double.NaN;
+ }
+
+ /**
+ * Scans {@link #BRACKET_GRID} for two adjacent rates whose NPVs have
+ * opposite signs. When several such brackets exist (multiple IRR roots),
+ * the one containing the guess is preferred, then the one closest to it.
+ *
+ * @return {@code {lo, npv(lo), hi, npv(hi)}}, a degenerate
+ * {@code {x, 0, x, 0}} if a grid point is an exact root, or
+ * {@code null} if NPV never changes sign on the grid
+ */
+ private static double[] findBracket(double[] values, double guess) {
+ double[] grid = BRACKET_GRID;
+ if (guess > -1 && guess <= 10000 && Arrays.binarySearch(BRACKET_GRID,
guess) < 0) {
+ grid = Arrays.copyOf(BRACKET_GRID, BRACKET_GRID.length + 1);
+ grid[grid.length - 1] = guess;
+ Arrays.sort(grid);
+ }
+ double[] best = null;
+ double bestDistance = Double.POSITIVE_INFINITY;
+ double prevX = Double.NaN;
+ double prevF = Double.NaN;
+ for (double x : grid) {
+ double fx = npv(values, x);
+ if (Double.isNaN(fx)) {
+ continue;
+ }
+ if (fx == 0) {
+ return new double[]{x, 0, x, 0};
+ }
+ if (!Double.isNaN(prevX) && (fx < 0) != (prevF < 0)) {
+ double distance = (prevX <= guess && guess <= x)
+ ? 0.0
+ : Math.min(Math.abs(guess - prevX), Math.abs(guess -
x));
+ if (distance < bestDistance) {
+ bestDistance = distance;
+ best = new double[]{prevX, prevF, x, fx};
+ }
+ }
+ prevX = x;
+ prevF = fx;
+ }
+ return best;
+ }
+
+ /**
+ * NPV computed via powers of {@code y = 1/(1+x)} so that rates very close
+ * to -1 overflow to infinity (usable for sign tests) instead of
+ * underflowing a shared denominator to 0 and dividing by it.
+ */
+ private static double npv(double[] values, double x) {
+ final double y = 1.0 / (1.0 + x);
+ double f = 0;
+ double p = 1;
+ for (double value : values) {
+ f += value * p;
+ p *= y;
+ }
+ return f;
+ }
+
+ /** First derivative of {@link #npv(double[], double)} with respect to x.
*/
+ private static double npvDerivative(double[] values, double x) {
+ final double y = 1.0 / (1.0 + x);
+ double df = 0;
+ double p = y;
+ for (int k = 1; k < values.length; k++) {
+ p *= y;
+ df -= k * values[k] * p;
+ }
+ return df;
+ }
}
diff --git a/poi/src/test/java/org/apache/poi/ss/formula/functions/TestIrr.java
b/poi/src/test/java/org/apache/poi/ss/formula/functions/TestIrr.java
index 8071b8d8cd..457ca576e5 100644
--- a/poi/src/test/java/org/apache/poi/ss/formula/functions/TestIrr.java
+++ b/poi/src/test/java/org/apache/poi/ss/formula/functions/TestIrr.java
@@ -20,6 +20,7 @@ package org.apache.poi.ss.formula.functions;
import static org.apache.poi.ss.util.Utils.addRow;
import static org.apache.poi.ss.util.Utils.assertDouble;
import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertTrue;
import org.apache.poi.hssf.HSSFTestDataSamples;
import org.apache.poi.hssf.usermodel.HSSFCell;
@@ -158,6 +159,32 @@ final class TestIrr {
assertEquals(-0.009463562705856032, result, 1E-4); // should agree
within 0.01%
}
+ @Test
+ void bug64137StyleDivergenceIsRescuedByBracketedFallback() {
+ // From an unlucky guess, plain Newton-Raphson overshoots far outside
the
+ // domain, the shared denominator overflows and the derivative
collapses
+ // to zero; the bracketed fallback must still find the root.
+ double[] incomes = {-1000, 0, 0, 0, 0, 0, 0, 0, 0, 6000};
+ // true IRR: 6000/1000 = (1+r)^9 => r = 6^(1/9) - 1
+ assertEquals(Math.pow(6.0, 1.0 / 9) - 1, Irr.irr(incomes, 9.0), 1E-7);
+ }
+
+ @Test
+ void irrNeverReturnsRateAtOrBelowMinus100Percent() {
+ // NPV of {-2, 1, 1} is zero at 0% and at -150%; a rate of -150% is
+ // financially meaningless and must not be returned even when the
+ // caller's guess sits next to that spurious root.
+ assertEquals(0.0, Irr.irr(new double[]{-2, 1, 1}, -1.4), 1E-7);
+ }
+
+ @Test
+ void noValidIrrReturnsNaN() {
+ // all-positive cash flow: NPV is positive for every rate
+ assertTrue(Double.isNaN(Irr.irr(new double[]{100, 50, 60})));
+ // NPV polynomial of {-1, 3, -2.5} has no real root
+ assertTrue(Double.isNaN(Irr.irr(new double[]{-1, 3, -2.5})));
+ }
+
private static void assertFormulaResult(CellValue cv, HSSFCell cell){
double actualValue = cv.getNumberValue();
double expectedValue = cell.getNumericCellValue(); // cached formula
result calculated by Excel
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]