Add mpz_inp_str to mini-gmp

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> tg at gmplib.org (Torbjörn Granlund) writes:
>
>> I haven't looked at mini-gmp's mpz_set_str, but I assume it is O(n^2),
>> so not much is lost by using a trivial implementation like the one
>> above.
>
> It tries to be O(n) when base is a power of two.

And I should add that for non-powers-of-two, it's also a bit more
sophisticated than what you sketch, for good or bad. If m is the largest
integer for which bb = base^m fits in a limb, the inner loop collects m
digits at a time, followed by an outerloop doing an mpn_mul_1 by bb and
an mpn_add_1.

So the O(n^2) constant is mostly independent of the base, and n is the
limb size, not the size in digits.

The interesting functions are mpn_set_str_bits and mpn_set_str_other.

And to limit code-duplication between mpz_inp_str and mpz_set_str, one
approach (which would work regardless of how the input termination
question is solved) is to use a shared helper-function
convert_to_digit_value, collect into a buffer, and then call mpn_set_str
which is responsible for the above tricks.

Regards,
/Niels

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