Re: binomial function

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Robert Gerbicz [2008-05-26 19:02]:
> I'm really surprised that computing binomial numbers for floating point
> real/complex numbers so slow in Pari-Gp. For example:
> binomial(1140000.78,420000) takes about 6 seconds and more than 22 MB Ram on
> my computer.
> A much faster way:
> F(n,k)=gamma(n+1)/gamma(k+1)/gamma(n-k+1) gives binomial(n,k)

Nobody had really needed it, but it's indeed easy to improve...

Not quite so simple as the above though, since gamma() becomes relatively more
costly as the precision increases:

(00:36) gp > \p1000
   realprecision = 1001 significant digits (1000 digits displayed)
(01:03) gp > for(i=1,10, F(1140000.78,100))
time = 709 ms.

(01:03) gp > for(i=1,10, binomial(1140000.78,  100))
time = 56 ms.
(01:05) gp > for(i=1,10, binomial(1140000.78, 1000))
time = 509 ms.

At this accuracy (\p1000) the threshold in favour of the gamma quotient is
around k ~ 1400, for binomial(n, k)  [ k <= n/2 ]



I have committed an improved version to svn.

Thanks for pointing this out,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`