Horton

Thread

Commits

  1. Disallow factorial of negative numbers

  2. Expand tests for factorial

  3. doc: Document factorial function

  4. Attached is a patch implementing factorial(), returning numeric. Points

  1. factorial of negative numbers

    Peter Eisentraut <peter.eisentraut@2ndquadrant.com> — 2020-06-15T07:11:16Z

    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

  2. Re: factorial of negative numbers

    Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> — 2020-06-15T11:15:25Z

    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.

  3. Re: factorial of negative numbers

    Tom Lane <tgl@sss.pgh.pa.us> — 2020-06-15T13:59:21Z

    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

  4. Re: factorial of negative numbers

    Tom Lane <tgl@sss.pgh.pa.us> — 2020-06-15T14:24:22Z

    ... 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

  5. Re: factorial of negative numbers

    Peter Eisentraut <peter.eisentraut@2ndquadrant.com> — 2020-06-16T03:18:25Z

    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

  6. Re: factorial of negative numbers

    Ashutosh Bapat <ashutosh.bapat@2ndquadrant.com> — 2020-06-16T05:00:20Z

    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

  7. Re: factorial of negative numbers

    Dean Rasheed <dean.a.rasheed@gmail.com> — 2020-06-16T07:31:21Z

    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 factorial of 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

  8. Re: factorial of negative numbers

    Bruce Momjian <bruce@momjian.us> — 2020-06-16T08:55:18Z

    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 factorial of 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

  9. Re: factorial of negative numbers

    Juan José Santamaría Flecha <juanjo.santamaria@gmail.com> — 2020-06-16T09:08:56Z

    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.

[1] http://mathforum.org/library/drmath/view/60851.html

Regards,

Juan José Santamaría Flecha

  10. Re: factorial of negative numbers

    Dean Rasheed <dean.a.rasheed@gmail.com> — 2020-06-16T09:34:38Z

    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

  11. Re: factorial of negative numbers

    Dean Rasheed <dean.a.rasheed@gmail.com> — 2020-06-16T09:49:59Z

    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

Regards,
Dean

  12. Re: factorial of negative numbers

    Juan José Santamaría Flecha <juanjo.santamaria@gmail.com> — 2020-06-16T10:30:16Z

    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

  13. Re: factorial of negative numbers

    Peter Eisentraut <peter.eisentraut@2ndquadrant.com> — 2020-06-16T11:18:54Z

    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

  14. Re: factorial of negative numbers

    Dean Rasheed <dean.a.rasheed@gmail.com> — 2020-06-16T12:17:59Z

    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

  15. Re: factorial of negative numbers

    Peter Eisentraut <peter.eisentraut@2ndquadrant.com> — 2020-06-18T07:13:35Z

    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

  16. Re: factorial of negative numbers

    Juan José Santamaría Flecha <juanjo.santamaria@gmail.com> — 2020-06-18T07:43:54Z

    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

  17. Re: factorial of negative numbers

    Peter Eisentraut <peter.eisentraut@2ndquadrant.com> — 2020-06-18T11:57:49Z

    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

  18. Re: factorial of negative numbers

    Juan José Santamaría Flecha <juanjo.santamaria@gmail.com> — 2020-06-18T12:19:10Z

    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:

https://en.wikipedia.org/wiki/Logarithm#/media/File:Log4.svg

Regards,

Juan José Santamaría Flecha