wrap-around interface

Zimmermann Paul Paul.Zimmermann at loria.fr
Sun Oct 21 09:44:22 CEST 2012


       Dear Marco,

> Date: Sat, 20 Oct 2012 17:31:33 +0200 (CEST)
> From: bodrato at mail.dm.unipi.it
> 
> Ciao Paul, and hi GMP-ECM developers!

ciao!!!

> Il Gio, 18 Ottobre 2012 11:06 am, Zimmermann Paul ha scritto:
> 
> >> > void mpn_mulmod_bnm1 (mp_ptr rp, mp_size_t rn, mp_srcptr ap, mp_size_t
> >> an,
> >> >                       mp_srcptr, bp, mp_size_t bn, mp_ptr tp)
> >> > Multiplies {ap, an} by {bp, bn} mod B^rn-1 where B=2^mp_bits_per_limb,
> >> > and stores the result into {rp, rn}. The scratch space tp is either
> >> NULL,
> >> > in which case the function allocates itself the needed memory, or it
> >> should
> >> > contain at least 2*rn+4 limbs (or the number of needed limbs should be
> >> > documented).
> 
> > Then I suggest removing the tp argument
> 
> Then I think we should write a wrapper to the current internal function,
> not only to deal with scratch space, but for the reason that it has some
> more limitations than the interface you propose.
> 
> Eg. the current implementation requires rn >= an >= bn > 0, and an + bn >
> rn/2.
> Moreover, if an + bn < rn, the result is stored in {rp, an+bn} (the
> remaining limbs are not zeroed).

this is fine. We won't use the wrap-around trick for an+bn < rn.

> In particular there is a detail that should be specified in a public
> interface: the representation of the class [0] = [B^rn-1]. The comment to
> the current internal function reads:
> 
>  * The result is expected to be ZERO if and only if one of the operand
>  * already is. Otherwise the class [0] Mod(B^rn-1) is represented by
>  * B^rn-1.
> 
> I.e. both representations are used. Does this "ambiguous" behaviour fit
> the public interface you have in mind?

no, I thought about the classical non-redundant representation 0 <= r < B^rn-1.
Indeed a wrapper function makes sense.

Paul


More information about the gmp-devel mailing list