Обсуждение: BUG #5428: Discrepency in remainder on mod function.
The following bug has been logged online: Bug reference: 5428 Logged by: Khee Chin Email address: kheechin@gmail.com PostgreSQL version: HEAD Operating system: Debian Description: Discrepency in remainder on mod function. Details: I'm not certain if this is a bug or an intended behavior. I noticed a discrepency in calculating the remainders across pgsql (PG), wolframalpha (W) and using Knuth's description of floored division for the function a mod n, -- where a (-4), n (-3), P - -1 W - -1 K - -1 where a (-4), n (+3), P - -1 W - +2 K - +2 where a (+4), n (-3), P - +1 W - -2 K - -2 where a (+4), n (+3), P - 1 W - 1 K - 1 Tracing the discrepency when either the dividend or divisor is negative, I took a look at src/backend/utils/adt/ numeric.c , int8.c and int.c and made the changes to the mod functions for int2/int4/int8/numeric to use Knuth's description for floored divisions where the remainder will have the same sign as the divisor. Attached is a proposed fix. diff --git a/src/backend/utils/adt/int.c b/src/backend/utils/adt/int.c index 43508b7..7c87a3a 100644 --- a/src/backend/utils/adt/int.c +++ b/src/backend/utils/adt/int.c @@ -1084,7 +1084,13 @@ int4mod(PG_FUNCTION_ARGS) /* No overflow is possible */ - PG_RETURN_INT32(arg1 % arg2); + /* + * Traditional arg1 % arg2 produces incorrect results in cases where + * either arg1 or arg2 is negative. This uses Knuth's description of floored + * division. + * a mod n = a - n * floor(a/n) + */ + PG_RETURN_INT32(arg1 - arg2 * floor((double) arg1 / arg2)); } Datum @@ -1099,7 +1105,13 @@ int2mod(PG_FUNCTION_ARGS) errmsg("division by zero"))); /* No overflow is possible */ - PG_RETURN_INT16(arg1 % arg2); + /* + * Traditional arg1 % arg2 produces incorrect results in cases where + * either arg1 or arg2 is negative. This uses Knuth's description of floored + * division. + * a mod n = a - n * floor(a/n) + */ + PG_RETURN_INT16(arg1 - arg2 * floor((double) arg1 / arg2)); } diff --git a/src/backend/utils/adt/int8.c b/src/backend/utils/adt/int8.c index 3245181..5d1b36d 100644 --- a/src/backend/utils/adt/int8.c +++ b/src/backend/utils/adt/int8.c @@ -644,7 +644,13 @@ int8mod(PG_FUNCTION_ARGS) errmsg("division by zero"))); /* No overflow is possible */ - PG_RETURN_INT64(arg1 % arg2); + /* + * Traditional arg1 % arg2 produces incorrect results in cases where + * either arg1 or arg2 is negative. This uses Knuth's description of floored + * division. + * a mod n = a - n * floor(a/n) + */ + PG_RETURN_INT64(arg1 - arg2 * floor((double) arg1 / arg2)); } diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c index 5766a8b..9fd31c2 100644 --- a/src/backend/utils/adt/numeric.c +++ b/src/backend/utils/adt/numeric.c @@ -4876,17 +4876,20 @@ mod_var(NumericVar *var1, NumericVar *var2, NumericVar *result) init_var(&tmp); - /* --------- - * We do this using the equation - * mod(x,y) = x - trunc(x/y)*y - * div_var can be persuaded to give us trunc(x/y) directly. - * ---------- - */ - div_var(var1, var2, &tmp, 0, false); + /* + * Traditional arg1 % arg2 produces incorrect results in cases where + * either arg1 or arg2 is negative. This uses Knuth's description of floored + * division. + * a mod n = a - n * floor(a/n) + */ + + div_var(var1, var2, &tmp, NUMERIC_MAX_DISPLAY_SCALE, true); + + floor_var(&tmp,&tmp); - mul_var(var2, &tmp, &tmp, var2->dscale); + mul_var(var2, &tmp, &tmp, var2->dscale); - sub_var(var1, &tmp, result); + sub_var(var1, &tmp, result); free_var(&tmp); }
"Khee Chin" <kheechin@gmail.com> writes: > I'm not certain if this is a bug or an intended behavior. > I noticed a discrepency in calculating the remainders across pgsql (PG), > wolframalpha (W) and using Knuth's description of floored division We follow whatever the C compiler's idea of modulo is. This is somewhat standardized, in fact, and I'm not excited about changing it. Especially not by introducing roundoff-prone double arithmetic into what had been an exact operation. regards, tom lane
On Sat, Apr 17, 2010 at 5:11 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote: > "Khee Chin" <kheechin@gmail.com> writes: >> I'm not certain if this is a bug or an intended behavior. > >> I noticed a discrepency in calculating the remainders across pgsql (PG), >> wolframalpha (W) and using Knuth's description of floored division > > We follow whatever the C compiler's idea of modulo is. =C2=A0This is some= what > standardized, in fact, and I'm not excited about changing it. > Especially not by introducing roundoff-prone double arithmetic into what > had been an exact operation. > > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0regards, tom lane > Hi Tom, Thks for the reply. I understand your first point on following the C compiler's idea of modulo is. For archiving purposes, to address your second concern, I have replaced the double arithmetic operation with this equation to address the modulo in int2/4/8 a mod n =3D ((a % n) + n) % n Regards, Khee Chin. diff --git a/src/backend/utils/adt/int.c b/src/backend/utils/adt/int.c index 43508b7..8b7ca05 100644 --- a/src/backend/utils/adt/int.c +++ b/src/backend/utils/adt/int.c @@ -1084,7 +1084,12 @@ int4mod(PG_FUNCTION_ARGS) /* No overflow is possible */ - PG_RETURN_INT32(arg1 % arg2); + /* + * Traditional arg1 % arg2 in C produces incorrect results in cases where + * either arg1 or arg2 is negative. + * a mod n =3D ((a % n) + n) % n + */ + PG_RETURN_INT32(((arg1 % arg2) + arg2) % arg2);; } Datum @@ -1099,7 +1104,12 @@ int2mod(PG_FUNCTION_ARGS) errmsg("division by zero"))); /* No overflow is possible */ - PG_RETURN_INT16(arg1 % arg2); + /* + * Traditional arg1 % arg2 in C produces incorrect results in cases where + * either arg1 or arg2 is negative. + * a mod n =3D ((a % n) + n) % n + */ + PG_RETURN_INT16(((arg1 % arg2) + arg2) % arg2); } diff --git a/src/backend/utils/adt/int8.c b/src/backend/utils/adt/int8.c index 3245181..57252da 100644 --- a/src/backend/utils/adt/int8.c +++ b/src/backend/utils/adt/int8.c @@ -644,7 +644,12 @@ int8mod(PG_FUNCTION_ARGS) errmsg("division by zero"))); /* No overflow is possible */ - PG_RETURN_INT64(arg1 % arg2); + /* + * Traditional arg1 % arg2 in C produces incorrect results in cases where + * either arg1 or arg2 is negative. + * a mod n =3D ((a % n) + n) % n + */ + PG_RETURN_INT64(((arg1 % arg2) + arg2) % arg2);; } diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeri= c.c index 5766a8b..a9b86df 100644 --- a/src/backend/utils/adt/numeric.c +++ b/src/backend/utils/adt/numeric.c @@ -4876,17 +4876,20 @@ mod_var(NumericVar *var1, NumericVar *var2, NumericVar *result) init_var(&tmp); - /* --------- - * We do this using the equation - * mod(x,y) =3D x - trunc(x/y)*y - * div_var can be persuaded to give us trunc(x/y) directly. - * ---------- - */ - div_var(var1, var2, &tmp, 0, false); + /* + * Traditional arg1 % arg2 in C produces incorrect results in cases where + * either arg1 or arg2 is negative. This uses Knuth's description of floored + * division. + * a mod n =3D a - n * floor(a/n) + */ + + div_var(var1, var2, &tmp, NUMERIC_MAX_DISPLAY_SCALE, true); + + floor_var(&tmp,&tmp); - mul_var(var2, &tmp, &tmp, var2->dscale); + mul_var(var2, &tmp, &tmp, var2->dscale); - sub_var(var1, &tmp, result); + sub_var(var1, &tmp, result); free_var(&tmp); }