ni...@lysator.liu.se (Niels Möller) writes: > t...@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. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel