Bill Allombert on Wed, 6 Nov 2002 17:32:12 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: CVS branch gmp-kernel-2-2-5

On Wed, Nov 06, 2002 at 04:50:52PM +0100, Karim BELABAS wrote:
> On Wed, 6 Nov 2002, Bill Allombert wrote:
> > --- ratlift() is not implemented. This looks difficult to do without
> > an insight of the code. Help appreciate (Gerhart ?). It need to either
> > be ported to the t_INT API, or rewrtten for the gmp kernel.
> The code is a relatively straightforward implementation of
> Collins/Encarnacion's paper (see comment above function code).
> Porting to the new t_INT API should be easy. There are only a few accesses to
> x[2] for "high word of x" (generally in the case lgefint(x) == 3). Everything
> else is high-level calls.
> Any particular problem I have overlooked ?

Well, I believe Gerhart has implemented Lehmer-Jebelean variation.
The following lines    
    /* do a Lehmer-Jebelean round */
   lhmres = lgcdii((ulong *)d, (ulong *)d1, &xu, &xu1, &xv, &xv1, vmax);
use lgcdii which depend heavily on the t_INT representation, I believe.

> > --- The /*HACK*/ in the code need to be investigated and guard values added,
> > else stack overrun will happen.
> Yes. It's probably better to try and eliminate them all.

It should be easy to add kernel dependant HACK values.

> > --- No Montgomery multiplication support. The GMP code for that is private to
> > GMP.
> Maybe powmodulo can be moved to the kernel then ? (then we could use GMP's
> implementation, including Mongtomery's REDC).

There is no mpn_powmodulo, only a mpz_powmodulo. This will not be
straightforward to use.

> > --- diviiexact is just a call to divii.
> Should be a wrapper to mpz_divexact (the exact equivalent).

Again there is no mpn_divexact, so the overhead of the wrapper might be
to high. There is a mpn_bdivmod that can be used, but I do not
know exactly how, but it is probably easy.

> > --- Lots of things need tuning/testing.
> Any comparison data so far ?

The PARI benchmark is 50% worse with the GMP kernel :-(

Try gcd(fibonacci(n),fibonacci(n+1)). GMP is much faster
if n is large (>10000).

For factorint the cut-off is at 256 bits.
Below PARI kernel is faster, after GMP won.

Unfortunately ratlift is used by lot of interesting functions,
so the tests currently are limited.

You can try bnfinit.