From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Dean Rasheed <dean.a.rasheed@gmail.com>
To: David Fetter <david@fetter.org>
Cc: Alvaro Herrera <alvherre@2ndquadrant.com>
Cc: PostgreSQL Hackers <pgsql-hackers@postgresql.org>
Subject: Re: multivariate statistics (v19)
Date: Sat, 11 Feb 2017 02:17:23 +0100
Message-ID: <fcd7e80f-6c5c-5ae4-8ed6-1496b364e673@2ndquadrant.com> (raw)
In-Reply-To: <CAEZATCUaVN0WQN_S3dR4y9SMRU8gmJc3vDggfvAR0W4cz3apcg@mail.gmail.com>
References: <90fd1100-1886-cb4b-10ee-c556ac6c3d12@2ndquadrant.com>
<20170206212616.itctsg6x7u6atbtp@alvherre.pgsql>
<CAEZATCXagY1GjO=jgK3-1z_gKaFFYkiTNRUyOZscOT1M-DJiUg@mail.gmail.com>
<20170208160908.GC8118@fetter.org>
<CAEZATCUaVN0WQN_S3dR4y9SMRU8gmJc3vDggfvAR0W4cz3apcg@mail.gmail.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
On 02/08/2017 07:40 PM, Dean Rasheed wrote:
> On 8 February 2017 at 16:09, David Fetter <david@fetter.org> wrote:
>> Combinations are n!/(k! * (n-k)!), so computing those is more
>> along the lines of:
>>
>> unsigned long long
>> choose(unsigned long long n, unsigned long long k) {
>> if (k > n) {
>> return 0;
>> }
>> unsigned long long r = 1;
>> for (unsigned long long d = 1; d <= k; ++d) {
>> r *= n--;
>> r /= d;
>> }
>> return r;
>> }
>>
>> which greatly reduces the chance of overflow.
>>
>
> Hmm, but that doesn't actually prevent overflows, since it can
> overflow in the multiplication step, and there is no protection
> against that.
>
> In the algorithm I presented, the inputs and the intermediate result
> are kept below INT_MAX, so the multiplication step cannot overflow the
> 64-bit integer, and it will only raise an overflow error if the actual
> result won't fit in a 32-bit int. Actually a crucial part of that,
> which I failed to mention previously, is the first step replacing k
> with min(k, n-k). This is necessary for inputs like (100,99), which
> should return 100, and which must be computed as 100 choose 1, not 100
> choose 99, otherwise it will overflow internally before getting to the
> final result.
>
Thanks for the feedback, I'll fix this. I've allowed myself to be a bit
sloppy because the number of attributes in the statistics is currently
limited to 8, so the overflows are currently not an issue. But it
doesn't hurt to make it future-proof, in case we change that mostly
artificial limit sometime in the future.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: tomas.vondra@2ndquadrant.com, dean.a.rasheed@gmail.com, david@fetter.org, alvherre@2ndquadrant.com
Subject: Re: multivariate statistics (v19)
In-Reply-To: <fcd7e80f-6c5c-5ae4-8ed6-1496b364e673@2ndquadrant.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox