Skip site navigation (1) Skip section navigation (2)

BUG #5428: Discrepency in remainder on mod function.

From: "Khee Chin" <kheechin(at)gmail(dot)com>
To: pgsql-bugs(at)postgresql(dot)org
Subject: BUG #5428: Discrepency in remainder on mod function.
Date: 2010-04-16 21:05:03
Message-ID: 201004162105.o3GL53pu013625@wwwmaster.postgresql.org (view raw or flat)
Thread:
Lists: pgsql-bugs
The following bug has been logged online:

Bug reference:      5428
Logged by:          Khee Chin
Email address:      kheechin(at)gmail(dot)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);
 }

Responses

pgsql-bugs by date

Next:From: Tom LaneDate: 2010-04-16 21:11:25
Subject: Re: BUG #5428: Discrepency in remainder on mod function.
Previous:From: Tom LaneDate: 2010-04-16 21:03:37
Subject: Re: build error: strlcat/strlcpy used from heimdal libroken.so

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group