Re: Computation of binomials modulo p^M

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

* Xavier-François Roblot [2010-05-19 09:20]:
> Let p be a prime (say less than 50), M an integer (such that p^M is
> about 10^10) and N another integer (say smaller than 30). For s of
> size p^M, I am interesting to compute all the binomial coefficients
> binom{s}{n} modulo p^M for n = 0 up to N-1. At the moment, I am doing
> that in the straightforward way using the classic relation between
> binom{s}{n+1} and binom{s}{n} and it works okay. But, since this
> computation is really the bottleneck in the project I am working on at
> the moment, I'll be very interested to hear about faster solutions. 

Not sure I understand : starting from binom{s}{1} = s, your
"straightforward" way performs N-1 multiplications and divisions mod p^M,
right ? And you want to do this for many essentially random values of s ?

The only simply thing I see is to precompute 1/2, ..., 1/N mod p^M so as to
avoid modular inversions. And program the loop in C using ulong's of
course (Fl_mul, etc.), on a 64 bit machine.

If you're really serious about this you can precompute the polynomials
binomial(X, k) mod p^M for 0 <= k <= N, then implement a multipoint
evaluation via product trees (partially re-using the trees associated
to a set of values of s for the various polynomials).

And of course, this is embarassingly easy to paralellize :-).

Good luck,

    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]
`