Add mpz_inp_str to mini-gmp
nisse at lysator.liu.se
Fri Jul 8 12:13:22 UTC 2016
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
> 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
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.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel