Thread: factorial of negative numbers
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
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.
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
... 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
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
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
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
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
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
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
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
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
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
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
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
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
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
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