3 ms·

It turns out that there is no modular multiplicative inverse for this, so that trick cannot be used to avoid the modulus and division when getting the base 10 d

• thequux 2y ago
  Indeed there isn't; 10 is not relatively prime to 2^32. However, 5 is (and therefore has a multiplicative inverse), so you can right shift and then multiply by the inverse.
  • zahlman 2y ago
    All of this is missing the point that doing basic arithmetic like this in Python drowns in the overhead of manipulating objects (at least with the reference C implementation). For that matter, the naive "convert to string and convert each digit to int" approach becomes faster in pure Python than using explicit div/mod arithmetic for very large numbers. This is in part thanks to algorithmic improvements implemented at least partially in Python (https://github.com/python/cpython/blob/main/Lib/_pylong.py#L178 https://github.com/python/cpython/blob/main/Lib/_pylong.py#L...). But I can also see improved performance even for only a couple hundred digits (i.e. less than DIGLIM for the recursion) which I think comes from being able to do the div/mod loop in C (although my initial idea about the details doesn't make much sense if I keep thinking about it).