Thread: factorial of negative numbers

factorial of negative numbers

From
Peter Eisentraut
Date:
Adjacent to the discussion in [0] I wanted to document the factorial() 
function and expand the tests for that slightly with some edge cases.

I noticed that the current implementation returns 1 for the factorial of 
all negative numbers:

SELECT factorial(-4);
  factorial
-----------
          1

While there are some advanced mathematical constructions that define 
factorials for negative numbers, they certainly produce different 
answers than this.

Curiously, before the reimplementation of factorial using numeric 
(04a4821adef38155b7920ba9eb83c4c3c29156f8), it returned 0 for negative 
numbers, which is also not correct by any theory I could find.

I propose to change this to error out for negative numbers.

See attached patches for test and code changes.


[0]: 
https://www.postgresql.org/message-id/flat/38ca86db-42ab-9b48-2902-337a0d6b8311%402ndquadrant.com

-- 
Peter Eisentraut              http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Attachment

Re: factorial of negative numbers

From
Ashutosh Bapat
Date:
On Mon, Jun 15, 2020 at 12:41 PM Peter Eisentraut
<peter.eisentraut@2ndquadrant.com> wrote:
>
> Adjacent to the discussion in [0] I wanted to document the factorial()
> function and expand the tests for that slightly with some edge cases.
>
> I noticed that the current implementation returns 1 for the factorial of
> all negative numbers:
>
> SELECT factorial(-4);
>   factorial
> -----------
>           1
>
> While there are some advanced mathematical constructions that define
> factorials for negative numbers, they certainly produce different
> answers than this.
>
> Curiously, before the reimplementation of factorial using numeric
> (04a4821adef38155b7920ba9eb83c4c3c29156f8), it returned 0 for negative
> numbers, which is also not correct by any theory I could find.
>
> I propose to change this to error out for negative numbers.

+1.
Here are some comments
I see below in the .out but there's not corresponding SQL in .sql.
+SELECT factorial(-4);
+ factorial
+-----------
+         1
+(1 row)
+

Should we also add -4! to cover both function as well as the operator?

+    if (num < 0)
+        ereport(ERROR,
+                (errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),

This looks more of ERRCODE_FEATURE_NOT_SUPPORTED esp. since factorial
of negative numbers is defined but we are not supporting it. I looked
at some other usages of this error code. All of them are really are
out of range value errors.

Otherwise the patches look good to me.



Re: factorial of negative numbers

From
Tom Lane
Date:
Peter Eisentraut <peter.eisentraut@2ndquadrant.com> writes:
> Adjacent to the discussion in [0] I wanted to document the factorial() 
> function and expand the tests for that slightly with some edge cases.
> ...
> I propose to change this to error out for negative numbers.

+1 for all of this, with a couple trivial nitpicks about the error
changes:

* I'd have written the error as "factorial of a negative number is
undefined" ... not sure what a grammar stickler would say about it,
but that seems more natural to me.

* I'd leave the "if (num <= 1)" test after the error check as-is;
it's probably a shade cheaper than "if (num == 0 || num == 1)".

            regards, tom lane



Re: factorial of negative numbers

From
Tom Lane
Date:
... oh, one slightly more important nit-pick: per the catalogs and
code, the function is factorial(bigint):

   Schema   |   Name    | Result data type | Argument data types | Type 
------------+-----------+------------------+---------------------+------
 pg_catalog | factorial | numeric          | bigint              | func

but you have it documented as factorial(numeric).

            regards, tom lane



Re: factorial of negative numbers

From
Peter Eisentraut
Date:
On 2020-06-15 13:15, Ashutosh Bapat wrote:
> Here are some comments
> I see below in the .out but there's not corresponding SQL in .sql.
> +SELECT factorial(-4);
> + factorial
> +-----------
> +         1
> +(1 row)
> +
> 
> Should we also add -4! to cover both function as well as the operator?

I will add that.  I wasn't actually sure about the precedence of these 
operators, so it is interesting as a regression test for that as well.

> +    if (num < 0)
> +        ereport(ERROR,
> +                (errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
> 
> This looks more of ERRCODE_FEATURE_NOT_SUPPORTED esp. since factorial
> of negative numbers is defined but we are not supporting it. I looked
> at some other usages of this error code. All of them are really are
> out of range value errors.

The proposed error message says this is undefined.  If we use an error 
code that says it's not implemented, then the message should also 
reflect that.  But that would in turn open an invitation for someone to 
implement it, and I'm not sure we want that.  It could go either way, 
but we should be clear on what we want.

-- 
Peter Eisentraut              http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services



Re: factorial of negative numbers

From
Ashutosh Bapat
Date:


On Tue, 16 Jun 2020 at 08:48, Peter Eisentraut <peter.eisentraut@2ndquadrant.com> wrote:
On 2020-06-15 13:15, Ashutosh Bapat wrote:
> Here are some comments
> I see below in the .out but there's not corresponding SQL in .sql.
> +SELECT factorial(-4);
> + factorial
> +-----------
> +         1
> +(1 row)
> +
>
> Should we also add -4! to cover both function as well as the operator?

I will add that.  I wasn't actually sure about the precedence of these
operators, so it is interesting as a regression test for that as well.

+1.  
 
> +    if (num < 0)
> +        ereport(ERROR,
> +                (errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
>
> This looks more of ERRCODE_FEATURE_NOT_SUPPORTED esp. since factorial
> of negative numbers is defined but we are not supporting it. I looked
> at some other usages of this error code. All of them are really are
> out of range value errors.

The proposed error message says this is undefined.  If we use an error
code that says it's not implemented, then the message should also
reflect that.

Yes. BTW, OUT_OF_RANGE is not exactly "undefined" either. I searched for an error code for "UNDEFINED" result but didn't find any.
 
But that would in turn open an invitation for someone to
implement it, and I'm not sure we want that.

 It will be more complex code, so difficult to implement but why do we prevent why not.
 
It could go either way,
but we should be clear on what we want.


Divison by zero is really undefined, 12345678 * 12345678 (just some numbers) is out of range of say int4, but factorial of a negative number has some meaning and is defined but PostgreSQL does not support it.

--
Best Wishes,
Ashutosh

Re: factorial of negative numbers

From
Dean Rasheed
Date:
On Tue, 16 Jun 2020 at 06:00, Ashutosh Bapat
<ashutosh.bapat@2ndquadrant.com> wrote:
>
> Divison by zero is really undefined, 12345678 * 12345678 (just some numbers) is out of range of say int4, but
factorialof a negative number has some meaning and is defined but PostgreSQL does not support it.
 
>

Actually, I think undefined/out-of-range is the right error to throw here.

Most common implementations do regard factorial as undefined for
anything other than positive integers, as well as following the
convention that factorial(0) = 1. Some implementations extend the
factorial to non-integer inputs, negative inputs, or even complex
inputs by defining it in terms of the gamma function. However, even
then, it is undefined for negative integer inputs.

Regards,
Dean

[1] https://en.wikipedia.org/wiki/Factorial
[2] https://en.wikipedia.org/wiki/Gamma_function



Re: factorial of negative numbers

From
Bruce Momjian
Date:
On Tue, Jun 16, 2020 at 08:31:21AM +0100, Dean Rasheed wrote:
> On Tue, 16 Jun 2020 at 06:00, Ashutosh Bapat
> <ashutosh.bapat@2ndquadrant.com> wrote:
> >
> > Divison by zero is really undefined, 12345678 * 12345678 (just some numbers) is out of range of say int4, but
factorialof a negative number has some meaning and is defined but PostgreSQL does not support it.
 
> >
> 
> Actually, I think undefined/out-of-range is the right error to throw here.
> 
> Most common implementations do regard factorial as undefined for
> anything other than positive integers, as well as following the
> convention that factorial(0) = 1. Some implementations extend the
> factorial to non-integer inputs, negative inputs, or even complex
> inputs by defining it in terms of the gamma function. However, even
> then, it is undefined for negative integer inputs.

Wow, they define it for negative inputs, but not negative integer
inputs?  I am curious what the logic is behind that.

-- 
  Bruce Momjian  <bruce@momjian.us>        https://momjian.us
  EnterpriseDB                             https://enterprisedb.com

  The usefulness of a cup is in its emptiness, Bruce Lee




Re: factorial of negative numbers

From
Juan José Santamaría Flecha
Date:

On Tue, Jun 16, 2020 at 10:55 AM Bruce Momjian <bruce@momjian.us> wrote:
On Tue, Jun 16, 2020 at 08:31:21AM +0100, Dean Rasheed wrote:
>
> Most common implementations do regard factorial as undefined for
> anything other than positive integers, as well as following the
> convention that factorial(0) = 1. Some implementations extend the
> factorial to non-integer inputs, negative inputs, or even complex
> inputs by defining it in terms of the gamma function. However, even
> then, it is undefined for negative integer inputs.

Wow, they define it for negative inputs, but not negative integer
inputs?  I am curious what the logic is behind that.

It is defined as NaN (or undefined), which is not in the realm of integer numbers. You might get a clear idea of the logic from [1], where they also make a case for the error being ERRCODE_DIVISION_BY_ZERO.


Regards,

Juan José Santamaría Flecha

Re: factorial of negative numbers

From
Dean Rasheed
Date:
On Tue, 16 Jun 2020 at 09:55, Bruce Momjian <bruce@momjian.us> wrote:
>
> On Tue, Jun 16, 2020 at 08:31:21AM +0100, Dean Rasheed wrote:
> >
> > Most common implementations do regard factorial as undefined for
> > anything other than positive integers, as well as following the
> > convention that factorial(0) = 1. Some implementations extend the
> > factorial to non-integer inputs, negative inputs, or even complex
> > inputs by defining it in terms of the gamma function. However, even
> > then, it is undefined for negative integer inputs.
>
> Wow, they define it for negative inputs, but not negative integer
> inputs?  I am curious what the logic is behind that.
>

That's just the way the maths works out. The gamma function is
well-defined for all real and complex numbers except for zero and
negative integers, where it has poles (singularities/infinities).
Actually the gamma function isn't the only possible extension of the
factorial function, but it's the one nearly everyone uses, if they
bother at all (most people don't).

Curiously, the most widespread implementation is probably the
calculator in MS Windows.

Regards,
Dean



Re: factorial of negative numbers

From
Dean Rasheed
Date:
On Tue, 16 Jun 2020 at 10:09, Juan José Santamaría Flecha
<juanjo.santamaria@gmail.com> wrote:
>
> It is defined as NaN (or undefined), which is not in the realm of integer numbers. You might get a clear idea of the
logicfrom [1], where they also make a case for the error being ERRCODE_DIVISION_BY_ZERO. 
>
> [1] http://mathforum.org/library/drmath/view/60851.html
>

Hmm, I think ERRCODE_DIVISION_BY_ZERO should probably be reserved for
actual division functions.

With [1], we could return 'Infinity', which would be more correct from
a mathematical point of view, and might be preferable to erroring-out
in some contexts.

[1] https://www.postgresql.org/message-id/606717.1591924582%40sss.pgh.pa.us

Regards,
Dean



Re: factorial of negative numbers

From
Juan José Santamaría Flecha
Date:

On Tue, Jun 16, 2020 at 11:50 AM Dean Rasheed <dean.a.rasheed@gmail.com> wrote:
On Tue, 16 Jun 2020 at 10:09, Juan José Santamaría Flecha
<juanjo.santamaria@gmail.com> wrote:
>
> It is defined as NaN (or undefined), which is not in the realm of integer numbers. You might get a clear idea of the logic from [1], where they also make a case for the error being ERRCODE_DIVISION_BY_ZERO.
>
> [1] http://mathforum.org/library/drmath/view/60851.html
>

Hmm, I think ERRCODE_DIVISION_BY_ZERO should probably be reserved for
actual division functions.

With [1], we could return 'Infinity', which would be more correct from
a mathematical point of view, and might be preferable to erroring-out
in some contexts.

[1] https://www.postgresql.org/message-id/606717.1591924582%40sss.pgh.pa.us

Returning division-by-zero would be confusing for the user.

I think that out-of-range would be a reasonable solution for "FUNCTION factorial(integer) RETURNS integer", because it could only return an integer when the input is a positive integer, but for "FUNCTION factorial(integer) RETURNS numeric" the returned value should be 'NaN' without error.

Regards,

Juan José Santamaría Flecha

Re: factorial of negative numbers

From
Peter Eisentraut
Date:
On 2020-06-16 11:49, Dean Rasheed wrote:
> With [1], we could return 'Infinity', which would be more correct from
> a mathematical point of view, and might be preferable to erroring-out
> in some contexts.

But the limit of the gamma function is either negative or positive 
infinity, depending on from what side you come, so we can't just return 
one of those two.

-- 
Peter Eisentraut              http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services



Re: factorial of negative numbers

From
Dean Rasheed
Date:
On Tue, 16 Jun 2020 at 12:18, Peter Eisentraut
<peter.eisentraut@2ndquadrant.com> wrote:
>
> On 2020-06-16 11:49, Dean Rasheed wrote:
> > With [1], we could return 'Infinity', which would be more correct from
> > a mathematical point of view, and might be preferable to erroring-out
> > in some contexts.
>
> But the limit of the gamma function is either negative or positive
> infinity, depending on from what side you come, so we can't just return
> one of those two.
>

Hmm yeah, although that's only really the case if you define it in
terms of continuous real input values.

I think you're probably right though. Raising an out-of-range error
seems like the best option.

Regards,
Dean



Re: factorial of negative numbers

From
Peter Eisentraut
Date:
On 2020-06-16 14:17, Dean Rasheed wrote:
> I think you're probably right though. Raising an out-of-range error
> seems like the best option.

committed as proposed then

-- 
Peter Eisentraut              http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services



Re: factorial of negative numbers

From
Juan José Santamaría Flecha
Date:

On Thu, Jun 18, 2020 at 9:13 AM Peter Eisentraut <peter.eisentraut@2ndquadrant.com> wrote:
On 2020-06-16 14:17, Dean Rasheed wrote:
> I think you're probably right though. Raising an out-of-range error
> seems like the best option.

committed as proposed then

The gamma function from math.h returns a NaN for negative integer values, the postgres factorial function returns a numeric, which allows NaN. Raising an out-of-range error seems only reasonable for an integer output.

Regards,

Juan José Santamaría Flecha

Re: factorial of negative numbers

From
Peter Eisentraut
Date:
On 2020-06-18 09:43, Juan José Santamaría Flecha wrote:
> 
> On Thu, Jun 18, 2020 at 9:13 AM Peter Eisentraut 
> <peter.eisentraut@2ndquadrant.com 
> <mailto:peter.eisentraut@2ndquadrant.com>> wrote:
> 
>     On 2020-06-16 14:17, Dean Rasheed wrote:
>      > I think you're probably right though. Raising an out-of-range error
>      > seems like the best option.
> 
>     committed as proposed then
> 
> 
> The gamma function from math.h returns a NaN for negative integer 
> values, the postgres factorial function returns a numeric, which allows 
> NaN. Raising an out-of-range error seems only reasonable for an integer 
> output.

But this is not the gamma function.  The gamma function is undefined at 
zero, but factorial(0) returns 1.  So this is similar but not the same.

Moreover, functions such as log() also error out on unsupportable input 
values, so it's consistent with the spec.

-- 
Peter Eisentraut              http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services



Re: factorial of negative numbers

From
Juan José Santamaría Flecha
Date:

On Thu, Jun 18, 2020 at 1:57 PM Peter Eisentraut <peter.eisentraut@2ndquadrant.com> wrote:
On 2020-06-18 09:43, Juan José Santamaría Flecha wrote:
> The gamma function from math.h returns a NaN for negative integer
> values, the postgres factorial function returns a numeric, which allows
> NaN. Raising an out-of-range error seems only reasonable for an integer
> output.

But this is not the gamma function.  The gamma function is undefined at
zero, but factorial(0) returns 1.  So this is similar but not the same.

factorial(n) = gamma(n + 1)
 
Moreover, functions such as log() also error out on unsupportable input
values, so it's consistent with the spec.

If factorial() ever gets extended to other input types it might get inconsistent, should !(-1.0) also raise an error?

Logarithm is just different case:


Regards,

Juan José Santamaría Flecha