Skip Menu |
 

This queue is for tickets about the Math-BigInt CPAN distribution.

Report information
The Basics
Id: 95628
Status: resolved
Priority: 0/
Queue: Math-BigInt

People
Owner: Nobody in particular
Requestors: DANAJ [...] cpan.org
Cc:
AdminCc:

Bug Information
Severity: Normal
Broken in: 1.9993
Fixed in: 1.999816



Subject: binomial with negative n
Download (untitled) / with headers
text/plain 1.1k
Math::BigInt does not implement the standard extension of binomials to negative arguments. See: http://mathworld.wolfram.com/BinomialCoefficient.html which is what Pari, Mathematica, GMP, and the development version of Math::Prime::Util implement. $ perl -MMath::Pari=binomial -E 'say binomial(-10,5)' -2002 $ perl -MMath::GMPz=:mpz -E 'my $n = Rmpz_init(); Rmpz_bin_ui($n, Math::GMPz->new(-10), Math::GMPz->new(5)); say $n' -2002 http://www.wolframalpha.com/input/?i=Binomial[-10%2C5] Result: -2002 In contrast: $ perl -Mbigint=lib,Calc -E 'my $n = -10; say $n->bnok(5)' -252 $ perl -Mbigint=lib,GMP -E 'my $n = -10; say $n->bnok(5)' -252 $ perl -Mbigint=lib,Pari -E 'my $n = -10; say $n->bnok(5)' 14 The last entry is especially troubling. The Calc and GMP backends have _nok routines, Pari does not. Interestingly, GMP and Pari both have binomial built in, but neither backend uses the library function. The following, put right after the inf/NaN checks and before the k > n checks, will give the correct results for these examples. It has not been tested extensively. return $self->bnok(-$x+$y-1,$y,@r) * (1,-1)[$CALC->_is_odd($y->{value})] if $x->{sign} =~ /^-/;
Download (untitled) / with headers
text/plain 780b
Followup for the example patch. We need the k<0 test early, and make sure we modify $x. Hence after the NaN and inf tests: # k < 0 => 0 return $x->bzero() if $y->{sign} =~ /^-/; # negative x => (-1)^y * binomial(-x+y-1,y) if ($x->{sign} =~ /^-/) { $x->bneg()->badd($y)->bdec(); $x->bnok($y,@r); $x->bneg() if $CALC->_is_odd($y->{value}); return $x; } # k > n => 0 my $cmp = $x->bacmp($y); return $x->bzero() if $cmp < 0; # k == n => 1 return $x->bone(@r) if $cmp == 0; This passes the simple test: perl -MMath::Pari=binomial -MMath::BigInt -E 'for $n (0..100) { for $k (-10 .. $n+10) { die "$n,$k" unless binomial($n,$k) == Math::BigInt->new($n)->bnok($k); die "-$n,$k" unless binomial(-$n,$k) == Math::BigInt->new(-$n)->bnok($k); } }'
Download (untitled) / with headers
text/plain 551b
While we're at it, perhaps add the k > n/2 optimization. Feel free to adjust or ignore as desired. Replaces the code inside the !$y->is_zero() loop at the end, so actually one line shorter. my $n = $x->copy; my $k = ($y->bacmp($x->brsft(1)) > 0) ? $n-$y : $y; $x->bone(); my $d = $self->bone(); while ($d->bacmp($k) <= 0) { $x->bmul($n)->bdiv($d); $n->bdec(); $d->binc(); } This only gets used if the backend doesn't implement _nok, e.g. Math::BigInt::Pari. The Calc and GMP backends do this optimization.
On Tue May 13 21:06:30 2014, DANAJ wrote: Show quoted text
> Math::BigInt does not implement the standard extension of binomials to > negative arguments. See: > > http://mathworld.wolfram.com/BinomialCoefficient.html > > which is what Pari, Mathematica, GMP, and the development version of > Math::Prime::Util implement. > > $ perl -MMath::Pari=binomial -E 'say binomial(-10,5)' > -2002 > > $ perl -MMath::GMPz=:mpz -E 'my $n = Rmpz_init(); Rmpz_bin_ui($n, > Math::GMPz->new(-10), Math::GMPz->new(5)); say $n' > -2002
Thanks for the report. I have created a test suite for this RT based on how Mathematica does it. By the way, Math::Pari and Math::GMPz don't always seem to get it right either: According to http://www.wolframalpha.com/input/?i=Binomial%5B-5%2C+-10%5D bnok(-5,-10) is -126. However, $ perl -MMath::Pari=binomial -E 'say binomial(-5,-10)' 0 $ perl -MMath::GMPz=:mpz -E 'my $n = Rmpz_init(); Rmpz_bin_ui($n, Math::GMPz->new(-5), Math::GMPz->new(-10)); say $n' 4824670384888174801469080539461978543841287286996873199424178601750570205310
RT-Send-CC: sisyphus [...] cpan.org, ilyaz [...] cpan.org
Download (untitled) / with headers
text/plain 1.4k
On Fri May 16 10:54:41 2014, pjacklam wrote: Show quoted text
> Thanks for the report. I have created a test suite for this RT based > on how Mathematica does it. > > By the way, Math::Pari and Math::GMPz don't always seem to get it > right either: > > According to http://www.wolframalpha.com/input/?i=Binomial%5B-5%2C+- > 10%5D bnok(-5,-10) is -126. However, > > $ perl -MMath::Pari=binomial -E 'say binomial(-5,-10)' > 0 > > $ perl -MMath::GMPz=:mpz -E 'my $n = Rmpz_init(); Rmpz_bin_ui($n, > Math::GMPz->new(-5), Math::GMPz->new(-10)); say $n' > 4824670384888174801469080539461978543841287286996873199424178601750570205310
Thanks! Yes, Mathematica implements the full Kronenburg extensions, which I recently added to my module. GMP does not allow a negative second argument at all. Math::GMPz probably should either trap this case or implement the extensions. I did this in GMP as: /* the two arguments have been read as a,b */ if (mpz_sgn(a) >= 0 && mpz_sgn(b) < 0) mpz_set_ui(a, 0); if (mpz_sgn(a) < 0 && mpz_sgn(b) < 0) { if (mpz_cmp(b,a) <= 0) mpz_sub(b, a, b); else mpz_set_ui(a, 0); } mpz_bin_ui(a, a, mpz_get_ui(b)); For Pari, I found out after filing the RT and looking into it more that Pari doesn't do the second [Mathworld eq 5] clause: n < 0, k <= n. A simple search didn't show any comments in the Pari mailing lists about it. I tested 2.7.0 and the latest Pari/GP repo as well. I think it would just be one line before calling Pari's binomial.
RT-Send-CC: sisyphus [...] cpan.org, sisyphus [...] cpan.org
Download (untitled) / with headers
text/plain 558b
(1) A little clearer GMP, given n and k: if (mpz_sgn(k) < 0) { /* Handle negative k */ if (mpz_sgn(n) >= 0 || mpz_cmp(k,n) > 0) mpz_set_ui(n, 0); else mpz_sub(k, n, k); } mpz_bin_ui(n, n, mpz_get_ui(k)); It looks like Math::GMPz's current code would be easy to put a trap in, but a bit more awkward for handling negative k. It's possible, just more code. (2) Attached is a patch for BigInt.pm 1.9993. Edit or replace as desired. Let me know if it does not pass your test suite.
Subject: bigint-binomial.patch
--- BigInt-orig.pm 2014-04-04 03:07:22.000000000 -0700 +++ BigInt.pm 2014-05-16 13:50:28.977265801 -0700 @@ -1323,15 +1323,21 @@ return $x->bnan() if $x->{sign} eq 'NaN' || $y->{sign} eq 'NaN'; return $x->binf() if $x->{sign} eq '+inf'; - # k > n or k < 0 => 0 my $cmp = $x->bacmp($y); - return $x->bzero() if $cmp < 0 || $y->{sign} =~ /^-/; - # k == n => 1 - return $x->bone(@r) if $cmp == 0; + my $xneg = $x->{sign} =~ /^-/; + my $yneg = $y->{sign} =~ /^-/; + return $x->bzero() if $xneg && $yneg && $cmp > 0; + return $x->bzero() if !$xneg && ($yneg || $cmp < 0); + my $k = ($yneg) ? $x - $y : $y->copy(); + + if ($xneg) { + $x->bneg->badd($k)->bdec(); + $xneg = 0 if $k->is_even; + } if ($CALC->can('_nok')) { - $x->{value} = $CALC->_nok($x->{value},$y->{value}); + $x->{value} = $CALC->_nok($x->{value},$k->{value}); } else { @@ -1339,21 +1345,21 @@ # ( - ) = --------- = --------------- = --------- = 5 * - * - # ( 3 ) (7-3)! 3! 1*2*3*4 * 1*2*3 1 * 2 * 3 2 3 - if (!$y->is_zero()) + if (!$k->is_zero()) { - my $z = $x - $y; - $z->binc(); - my $r = $z->copy(); $z->binc(); - my $d = $self->new(2); - while ($z->bacmp($x) <= 0) # f <= x ? + my $n = $x->copy; + $k = $n - $k if $k->bacmp($x->brsft(1)) > 0; + $x->bone(); + my $d = $self->bone(); + while ($d->bacmp($k) <= 0) { - $r->bmul($z); $r->bdiv($d); - $z->binc(); $d->binc(); + $x->bmul($n)->bdiv($d); + $n->bdec(); $d->binc(); } - $x->{value} = $r->{value}; $x->{sign} = '+'; } else { $x->bone(); } } + $x->bneg if $xneg; $x->round(@r); }
CC: <sisyphus [...] cpan.org>
Subject: Re: [rt.cpan.org #95628] binomial with negative n
Date: Sat, 17 May 2014 18:42:49 +1000
To: <bug-Math-BigInt [...] rt.cpan.org>
From: <sisyphus1 [...] optusnet.com.au>
Download (untitled) / with headers
text/plain 2.3k
Show quoted text
-----Original Message----- From: Dana Jacobsen via RT
> (1) A little clearer GMP, given n and k: > > if (mpz_sgn(k) < 0) { /* Handle negative k */ > if (mpz_sgn(n) >= 0 || mpz_cmp(k,n) > 0) mpz_set_ui(n, 0); > else mpz_sub(k, n, k); > } > mpz_bin_ui(n, n, mpz_get_ui(k)); > > It looks like Math::GMPz's current code would be easy to put a trap in, > but a bit more awkward for handling negative k. It's possible, just more > code.
Thanks for alerting me to this. I don't think it would be a good idea for a sub named "Rmpz_bin_ui" to start accepting negative values for k. The terminating "_ui" implies that the final arg is an unsigned long int, so accepting a signed long int would only make things confusing. However, even though the gmp library doesn't provide an mpz_bin_si function, it probably wouldn't hurt for Math::GMPz to provide an Rmpz_bin_si function (using the technique given above) - and I'll do that for the next release. I'm a little averse to having Math::GMPz get more involved in argument checking, though it's almost certainly the perlish thing to do. Do we really have to code to cover users providing signed args to functions that are documented to take only unsigned args ? (Admittedly, one can sometimes be unaware that the actual arg provided was signed. But if that's a possibility, then the user could be doing his own checks to make sure that doesn't happen.) My other concern is that once you start doing such additional checks, where do you stop ? On systems where ivsize == longsize it's fairly simple to check whether the supplied value was in fact a valid unsigned long. Not so simple when you take into account those perls (eg x64 windows) where ivsize != longsize. And if you do that check for one sub that takes a "ui" arg, then you really ought to do it for every sub that takes a "ui" arg. And if you're checking the validity of the unsigned long int arg, you really ought to do the (converse) checks for the signed long int args, too. Certainly not impossible - in fact, it would be quite interesting. And it's just one additional function call for every "_ui" or "_si" that appears in the sub's name. And it's not as though I don't have time to do this. But I still have this feeling that it's the *user's* responsibility to sort out these aspects ..... maybe I'll change my mind tomorrow .... Cheers, Rob
Download (untitled) / with headers
text/plain 1019b
On Sat May 17 04:43:41 2014, sisyphus1@optusnet.com.au wrote: Show quoted text
> > I don't think it would be a good idea for a sub named "Rmpz_bin_ui" to start > accepting negative values for k. > The terminating "_ui" implies that the final arg is an unsigned long int, so > accepting a signed long int would only make things confusing.
I certainly agree. I suspected "_ui" stood for unsigned int, and checked the docs for "Rmpz_bin_ui", which didn't confirm it. I should of course have searched for "_ui" in the docs which would have confirmed my suspicion. Show quoted text
> Do we really have to code to cover users providing signed args to functions > that are documented to take only unsigned args?
I vote for no. I like the blazing speed of Math::GMP[fqz] and don't want anything to slow it down. :) I wouldn't mind more checks in Math::Big(Int|Float|Rat), though, as these modules are often a user's first encounter with arbitrarily large numbers in Perl, but that's a different matter. Anyway, we have wandered off topic now, I believe. :)
RT-Send-CC: sisyphus1 [...] optusnet.com.au
Download (untitled) / with headers
text/plain 325b
Sorry for derailing the conversation. Rob, you make excellent points and I agree. Either Rmpz_bin_si, or just a short documentation note. It is a rather odd condition, and Pari/GP has gone along just fine without it for years. Probably best for callers to handle on their own, or higher level modules (e.g. Math::BigInt).
Subject: Re: [rt.cpan.org #95628] binomial with negative n
Date: Sun, 18 May 2014 12:51:51 -0400
To: bug-Math-BigInt [...] rt.cpan.org
From: "Tels" <nospam-abuse [...] bloodgate.com>
Download (untitled) / with headers
text/plain 513b
Hello Peter, On Fri, May 16, 2014 10:54 am, Peter John Acklam via RT wrote: Show quoted text
> Queue: Math-BigInt > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=95628 > > > On Tue May 13 21:06:30 2014, DANAJ wrote:
>> Math::BigInt does not implement the standard extension of binomials to >> negative arguments. See:
Is there any way I can prevent getting copies of all bugreports for the various Math modules? In almost all cases there is nothing I can do, except deleting the emails. best regards, tels
CC: sisyphus [...] cpan.org
Subject: Re: [rt.cpan.org #95628] binomial with negative n
Date: Fri, 6 May 2016 22:18:38 -0700
To: Dana Jacobsen via RT <bug-Math-BigInt [...] rt.cpan.org>
From: Ilya Zakharevich <nospam-abuse [...] ilyaz.org>
Download (untitled) / with headers
text/plain 2.4k
On Fri, May 16, 2014 at 11:35:16AM -0400, Dana Jacobsen via RT wrote: Show quoted text
> <URL: https://rt.cpan.org/Ticket/Display.html?id=95628 > > > On Fri May 16 10:54:41 2014, pjacklam wrote:
> > Thanks for the report. I have created a test suite for this RT based > > on how Mathematica does it.
Show quoted text
> > By the way, Math::Pari and Math::GMPz don't always seem to get it > > right either:
Show quoted text
> Yes, Mathematica implements the full Kronenburg extensions, which I recently added to my module.
Show quoted text
> GMP does not allow a negative second argument at all. Math::GMPz probably should either trap this case or implement the extensions. I did this in GMP as:
Show quoted text
> For Pari, I found out after filing the RT and looking into it more that Pari doesn't do the second [Mathworld eq 5] clause: n < 0, k <= n. A simple search didn't show any comments in the Pari mailing lists about it. I tested 2.7.0 and the latest Pari/GP repo as well. I think it would just be one line before calling Pari's binomial.
Interesting! A) Looking into this, I found that we addressed this question just recently on our Math circles (for kids in grades 1–4). Nobody of them wanted to make this error (make a symmetric continuation)! (If somebody is interested, I may HTML-email my notes of these classes.) B) I grepped, and Kronenburg paper has no words “pole” and “indeterminacy” (or similar ones, AFAICS). Apparently, he does not understand these concepts at all. Without them, it makes no sense to discuss behaviour of meromorphic functions in more than 1 variable. (The value in indeterminacy point makes no sense. Approaching this point from different directions gives different limits.) C) The STANDARD definition of binomial() takes a limit along a certain PARTICULAR direction. Going along the same direction for all the points preserves most of the important identities for binomial(). (Actually, there are 2 “natural” directions to choose. “Symmetrizing” exchanges these two “natural” choices. So the symmetrized definition goes to some indeterminacy points in one direction, and to other points in the other direction.) D) I found discussions of this bug (in Mathematica, Marple, Kronenburg etc) in http://trac.sagemath.org/ticket/17123 It looks like software made for mathematicians uses the standard definition of binomial(). Software made for engineers has this “symmetrization” bug. Hope this helps, Ilya


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

Please report any issues with rt.cpan.org to rt-cpan-admin@bestpractical.com.