Small limb-size in mini-gmp?

[Marco Bodrato]

Ciao,

Il 2019-11-19 22:20 nisse at lysator.liu.se ha scritto:
> "Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:
>> Il Mar, 19 Novembre 2019 7:50 pm, Torbjörn Granlund ha scritto:
>>> If there is special code for several asl cases, doesn't that defeat 
>>> the
>>> purpose of asl, at least to some extent?
> 
> I think it defeats small-limb testing of mini-gmp. If it makes mini-gmp
> with small limbs much faster, it might aid small-limb tests of mpfr.

Not only, it also aid small-limb testing of the implementations in 
mini-gmp of gcd, primality testing, combinatorics, modular 
exponentiation...

>> It is possible (and not really difficult, I think) to adapt the 
>> default
>> code and remove any special shortcut from both those functions too.
> 
> When the special code was added (about a year ago, 2018-12-21), was 
> that
> as an optimization, or because the original code didn't work properly
> for small limb size?

The special code for umul_ppmm was added for speed. The generic code 
works also for smaller limbs.

On the invert_3by2 side, the same kind of optimisation was used. Not 
only for speed, I have to admit, but also because the code could get 
simpler.

I was thinking also to some embedded systems I used some years ago, 
where "unsigned long" was supported by the compiler, but slow on the 
hardware...

But currently also those embedded systems are probably obsolete.

>> I think that special code to use plain unsigned long multiplication 
>> and
>> plain unsigned long division for those two critical macros, when limbs 
>> are
>> small enough, is a reasonable compromise.
> 
> Maybe for umul_ppmm, but I disagree about mpn_invert_3by2. The latter
> function isn't used in any inner loops.

Ok. We can decide to keep a single variant for mpn_invert_3by2.
Will changing the type currently used for "half limbs", taking care of 
negations and carry detection... be enough? We should try.

Ĝis,
m