[lmi-commits] [lmi] master fc01b15e 4/4: Avoid overflow on integer multiplication

[Greg Chicares]

branch: master
commit fc01b15e6c4366ba449fa5898b9900f114d6ce22
Author: Gregory W. Chicares <gchicares@sbcglobal.net>
Commit: Gregory W. Chicares <gchicares@sbcglobal.net>

    Avoid overflow on integer multiplication
    
    Multiplying any unsigned integer amount by a rate in [0,1] must yield
    a product that, when rounded, is representable as that integer type.
    Now define a limit that is 1e8 * (maximum value for that integer type).
    If amount is less than that limit, then 1e8 * amount cannot overflow;
    neither can any lower multiple of the amount. Therefore,
      amount * (1e8 * rate) [amount <= limit]
    cannot overflow.
    
    Suppose rate is given as a decimal with no more than eight significant
    digits, 0.12345678 for example. If that's available as a double, then
    it's an inexact representation of the intended rational 12345678 / 1e8,
    but rint(1e8 * rate) recovers the exact numerator of that rational.
    Multiplying amount by that numerator gives 1e8 times the exact product.
    Dividing the product by 1e8 gives the product; if the remainder is zero,
    then it is exact; otherwise, it's as exact as possible, and generally
    more accurate than multiplying an integral amount by a double rate
    because the double's representation error has been removed. The accuracy
    of integer multiplication has been achieved, to the extent possible,
    while avoiding overflow.
    
    If this could be explained in far fewer words, it'd be obvious.
    
    This causes a two-cent regression in guaranteed premium on a single
    testcase, for the reason explained in the preceding commit.
---
 ul_utilities.cpp | 22 ++++++++++++++++++++--
 1 file changed, 20 insertions(+), 2 deletions(-)

diff --git a/ul_utilities.cpp b/ul_utilities.cpp
index e6c51d0f..e9e7646c 100644
--- a/ul_utilities.cpp
+++ b/ul_utilities.cpp
@@ -110,11 +110,29 @@ currency rate_times_currency
     // decimals are required. The accompanying unit test gives some
     // illustrative examples of this precondition's effect.
     constexpr int radix {100'000'000};
-    // Premium rate and specified amount are nonnegative by their nature.
-    // Premium rate cannot plausibly exceed unity.
+    constexpr uint64 limit {UINT64_MAX / radix};
+    static currency const cents_limit {from_cents(limit)};
+    // The 'amount' argument rarely exceeds 'cents_limit', which is
+    // over a billion dollars:
+    //   1'844'674'407'37 = ⌊UINT64_MAX / 1.0e8⌋
+    // However, this has been observed to happen when solving for
+    // guaranteed premium on a policy form that recalculates the
+    // target premium from a table each year. The solve's a priori
+    // upper limit is one billion dollars; paying that amount every
+    // year causes AV to grow to over $300B; a DBO change from B to A
+    // increases specamt by AV; and calculating the target premium
+    // in that year causes this condition to fail.
+    if(cents_limit < amount)
+        {
+        return rounder.c(amount * rate);
+        }
+    // Premium rate and amount are nonnegative by their nature.
+    // Premium rate cannot plausibly exceed unity. If amount exceeds
+    // cents_limit, an early exit was taken above.
     LMI_ASSERT(0.0 <= rate);
     LMI_ASSERT(       rate <= 1.0);
     LMI_ASSERT(C0  <= amount);
+    LMI_ASSERT(       amount <= cents_limit);
     // Do not save and restore prior rounding direction, because lmi
     // generally expects rounding to nearest everywhere.
     std::fesetround(FE_TONEAREST);