Reduced number of allocated limbs after calling mpz_remove

[Niels Möller]

Torbjörn Granlund <tg at gmplib.org> writes:

> It is possible that the docs need clarification.

I think so, we should not write "never" if that's not what we mean.

My understanding is that allocation grows as needed, and is not returned
to the the system until mpz_clear. Except that allocation can shrink
only as the effect of mpz_realloc2 (never called internally) or mpz_swap
(called internally in few places).

But we also shouldn't over-allocate things. It could perhaps be
described like this: Each mpz output for a gmp function has an "expected
size" depending on the sizes of the inputs. E.g., excpected size of the
mpz_add output is the size of the largest input + 1, while actual size
may be as small as zero, due to cancellation.

On return, the allocation size of of an mpz_t output parameter should
either be unchanged (available storage could be reused, without any
reallocation, pointer would typically be unchanged too in this case), or
at most a limb or two larger than the expected output size for the
operation. E.g., mpz_powm internally needs storage for squares (twice
the expected output size), but it shouldn't inflate the allocation of
the output parameter to that size.

To the GMP application, the allocation size of an mpz_t is then bounded
by the largest "expected size" for any operation ever using that mpz_t
as output (+ effects of any mpz_swap or mpz_realloc2 in the
*application* code), which should be sufficient to get predictable
memory usage.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.