Micro-GMP

[Niels Möller]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

> The attached file is the result of "hg diff" compared with the *current*
> development version

I recommend adding -p to the diff flags.

> This code inherits some ideas from the micro- code you published, but I
> reorganised it completely. Basically (except for mpz_cmpabs_ui, already
> described) it is a collection of alternatives implementations. But only in
> some cases they completely substitute the general code, often they handle
> only some special cases.

Cool. I have some comments and questions.

First, how would this be configured? Adding an

#ifndef GMP_LIMB_BITS

around the mp_limb_t typedef in mini-gmp.h, and around the related
defines in mini-gmp.c? Then one could do

  #define GMP_LIMB_BITS 8
  typedef uint8_t mp_limb_t;
  #include "mini-gmp.c"

One could aim to support any GMP_LIMB_BITS between, say, 3 and the size
of unsigned long long. For unusual sizes one would need to combine with
asl.h or something similar.

I think it makes sense with special code for umul_ppmm for this case,
since it's the most performance critical part of all operations with
more than O(n) complexity. One could consider using unsigned long long
or unsigned __int128 where avaiable as well.

For the various _ui and _si functions, I think performance is less
important. For mini-gmp, I think it would make some sense to have a
non-trivial implementation only for mpz_set_ui and mpz_get_ui, and
implement all other _ui and _si functions in terms of that.

In particular, we'd get simplifications to mpz_abs_{add,sub}_ui,
mpz_mul_ui, and mpz_div_qr_ui.

> Is the proposed code too complex to belong to mini-gmp?

I think it is acceptable only if we can do it with only very few
functions needing special handling of mp_limb_t != unsigned long.
And we obviously need test coverage for it.

BTW, please use parentheses in expressions like

      assert ((r0 & GMP_LIMB_MAX >> GMP_LIMB_BITS - shift) == 0);

And I think we should always require that arithmetic on mp_limb_t is mod
(GMP_LIMB_MAX + 1), so that & GMP_LIMB_MAX usually is redundant (with
possible exception for contexts where we might have unsigned int rather
than mp_limb_t, due to type promotion).

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.