From: David Fetter <david@fetter.org>
To: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Alvaro Herrera <alvherre@2ndquadrant.com>
Cc: PostgreSQL Hackers <pgsql-hackers@postgresql.org>
Subject: Re: multivariate statistics (v19)
Date: Sun, 12 Feb 2017 11:42:07 -0800
Message-ID: <20170212194207.GA2120@fetter.org> (raw)
In-Reply-To: <CAEZATCXn1jJSAR0RYtki3ByFiDnkCGZTqvp7GT_+oAj8cmWDvA@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>
<fcd7e80f-6c5c-5ae4-8ed6-1496b364e673@2ndquadrant.com>
<CAEZATCXn1jJSAR0RYtki3ByFiDnkCGZTqvp7GT_+oAj8cmWDvA@mail.gmail.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
On Sun, Feb 12, 2017 at 10:35:04AM +0000, Dean Rasheed wrote:
> On 11 February 2017 at 01:17, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:
> > 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.
> >
>
> Ah right, so it can't overflow at present, but it's neater to have an
> overflow-proof algorithm.
>
> Thinking about the exactness of the division steps is quite
> interesting. Actually, the order of the multiplying factors doesn't
> matter as long as the divisors are in increasing order. So in both my
> proposal:
>
> result = 1
> for (i = 1; i <= k; i++)
> result = (result * (n-k+i)) / i;
>
> and David's proposal, which is equivalent but has the multiplying
> factors in the opposite order, equivalent to:
>
> result = 1
> for (i = 1; i <= k; i++)
> result = (result * (n-i+1)) / i;
>
> the divisions are exact at each step. The first time through the loop
> it divides by 1 which is trivially exact. The second time it divides
> by 2, having multiplied by 2 consecutive factors, one of which is
> therefore guaranteed to be divisible by 2. The third time it divides
> by 3, having multiplied by 3 consecutive factors, one of which is
> therefore guaranteed to be divisible by 3, and so on.
Right. You know you can use integer division, which make sense as
permutations of discrete sets are always integers.
> My approach originally seemed more logical to me because of the way it
> derives from the recurrence relation binomial(n, k) = binomial(n-1,
> k-1) * n / k, but they both work fine as long as they have suitable
> overflow checks.
Right. We could even cache those checks (sorry) based on data type
limits by architecture and OS if performance on those operations ever
matters that much.
> It's also interesting that descriptions of this algorithm tend to
> talk about setting k to min(k, n-k) at the start as an optimisation
> step, as I did in fact, whereas it's actually more than that -- it
> helps prevent unnecessary intermediate overflows when k > n/2. Of
> course, that's not a worry for the current use of this function, but
> it's good to have a robust algorithm.
Indeed. :)
Best,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david(dot)fetter(at)gmail(dot)com
Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate
--
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: david@fetter.org, dean.a.rasheed@gmail.com, tomas.vondra@2ndquadrant.com, alvherre@2ndquadrant.com
Subject: Re: multivariate statistics (v19)
In-Reply-To: <20170212194207.GA2120@fetter.org>
* 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