# [HACKERS] Bug in numeric multiplication

```Hi,

By chance, while testing the nearby numeric log/exp/pow patch, I came
across the following case which generates an initially puzzling
looking error on HEAD -- (5.6-1e-500) ^ (3.2-1e-200). This computation
actually works OK with that other patch, but only by blind luck. It
turns out that the underlying problem is a bug in the low-level
numeric multiplication function mul_var(). It is possible to trigger
it directly with the following carefully crafted inputs:```
```
select
4790999999999999999999999999999999999999999999999999999999999999999999999999999999999999
*
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999;

Result:
47909999999999999999999999999999999999999999999999999999999999999999999999999999997852304953000000000000000000000000000000000000000000000000000000000000000000000000000000000001

That answer is actually incorrect. Tweaking the input a little, it is
possible to generate a much more obviously nonsensical result:

select
4789999999999999999999999999999999999999999999999999999999999999999999999999999999999999
*
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999;

Result:
4789999999999999999999999999999999999999999999999999999999999999999999999999999999785231+0,*000000000000000000000000000000000000000000000000000000000000000000000000000000000001

Notice those garbage digits in the middle of the number returned.

The problem is that these examples trigger an overflow of the digits
in the accumulator array in mul_var().

The number on the left in the first example consists of 21 copies of
9999, preceded by 4790. Those are chosen so that when added together
they lead to a value for maxdig in mul_var() of 21*9999 + 4790 =
214769, which is exactly equal to INT_MAX / (NBASE - 1). So this
doesn't quite trigger a normalisation of the accumulator array, and
leaves several of the digits in that array a little under INT_MAX at
the end of the main multiplication loop.

The problem then arises in the final carry propagation pass. During
this phase of the computation, the carry from one digit (which can be
a shade under INT_MAX / NBASE) is added to the next digit, and that's
where the overflow happens.

To fix that, the initial value for maxdig needs to be made larger to
leave headroom for the carry. The largest possible carry is INT_MAX /
NBASE, and maxdig is the maximum possible dig value divided by
NBASE-1, so maxdig needs to be initialised to

(INT_MAX / NBASE) / (NBASE - 1)

which is 21 for NBASE = 10000.

A new corner-case input that doesn't quite trigger an accumulator
normalisation is then 47699999... The worst case inputs are now values
like this for which the sum of a sequence of input digits is INT_MAX /
(NBASE - 1) - 21 = 214769 - 21 = 214748. So in the worst case, the
accumulator's digits can be up to 214748 * 9999 = 2147265252 in the
main multiplication loop. Then, during the carry propagation phase (or
any of the normalisation phases), the carry can be anything up to
INT_MAX / NBASE = 214748. So the maximum value that can be assigned to
any individual digit is now 2147265252 + 214748 = 2147480000, which is
now less than INT_MAX.

Patch attached.

Regards,
Dean
```
```diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c
new file mode 100644
index 1bfa29e..4b39c7a
@@ -5792,9 +5792,13 @@ mul_var(NumericVar *var1, NumericVar *va
* threatens to exceed INT_MAX, we take the time to propagate carries. To
* avoid overflow in maxdig itself, it actually represents the max
* possible value divided by NBASE-1.
+	 *
+	 * Note that the carry propagation steps may carry as much as INT_MAX/NBASE
+	 * from one digit to the next, so we have to leave headroom for that as
+	 * well.
*/
dig = (int *) palloc0(res_ndigits * sizeof(int));
-	maxdig = 0;
+	maxdig = (INT_MAX / NBASE) / (NBASE - 1);

ri = res_ndigits - 1;
for (i1 = var1ndigits - 1; i1 >= 0; ri--, i1--)
@@ -5824,7 +5828,7 @@ mul_var(NumericVar *var1, NumericVar *va
}
Assert(carry == 0);
/* Reset maxdig to indicate new worst-case */
-			maxdig = 1 + var1digit;
+			maxdig = 1 + var1digit + (INT_MAX / NBASE) / (NBASE - 1);
}

/* Add appropriate multiple of var2 into the accumulator */
diff --git a/src/test/regress/expected/numeric.out b/src/test/regress/expected/numeric.out
new file mode 100644
index e6ee548..c1886fd
--- a/src/test/regress/expected/numeric.out
+++ b/src/test/regress/expected/numeric.out
@@ -1334,6 +1334,33 @@ SELECT * FROM num_input_test;
(7 rows)

--
+-- Test some corner cases for multiplication
+--
+select 4790999999999999999999999999999999999999999999999999999999999999999999999999999999999999 * 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999;
+                                                                                     ?column?
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ 47909999999999999999999999999999999999999999999999999999999999999999999999999999999999985209000000000000000000000000000000000000000000000000000000000000000000000000000000000001
+(1 row)
+
+select 4789999999999999999999999999999999999999999999999999999999999999999999999999999999999999 * 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999;
+                                                                                     ?column?
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ 47899999999999999999999999999999999999999999999999999999999999999999999999999999999999985210000000000000000000000000000000000000000000000000000000000000000000000000000000000001
+(1 row)
+
+select 4770999999999999999999999999999999999999999999999999999999999999999999999999999999999999 * 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999;
+                                                                                     ?column?
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ 47709999999999999999999999999999999999999999999999999999999999999999999999999999999999985229000000000000000000000000000000000000000000000000000000000000000000000000000000000001
+(1 row)
+
+select 4769999999999999999999999999999999999999999999999999999999999999999999999999999999999999 * 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999;
+                                                                                     ?column?
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ 47699999999999999999999999999999999999999999999999999999999999999999999999999999999999985230000000000000000000000000000000000000000000000000000000000000000000000000000000000001
+(1 row)
+
+--
-- Test some corner cases for division
--
select 999999999999999999999::numeric/1000000000000000000000;
diff --git a/src/test/regress/sql/numeric.sql b/src/test/regress/sql/numeric.sql
new file mode 100644
index 982287c..49ec478
--- a/src/test/regress/sql/numeric.sql
+++ b/src/test/regress/sql/numeric.sql
@@ -822,6 +822,18 @@ INSERT INTO num_input_test(n1) VALUES ('
SELECT * FROM num_input_test;

--
+-- Test some corner cases for multiplication
+--
+
+select 4790999999999999999999999999999999999999999999999999999999999999999999999999999999999999 * 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999;
+
+select 4789999999999999999999999999999999999999999999999999999999999999999999999999999999999999 * 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999;
+
+select 4770999999999999999999999999999999999999999999999999999999999999999999999999999999999999 * 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999;
+
+select 4769999999999999999999999999999999999999999999999999999999999999999999999999999999999999 * 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999;
+
+--
-- Test some corner cases for division
--

```
```--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
```