Optimizing isqrt and fsqrt

[arseniiv]

I thought I might try to add a couple of ideas about this todo as well. One naive optimization would be just precomputing decompositions of integers up to some not too large N, and then deferring to them as soon as b in isqrt is no greater than N.

Instead of precomputing decompositions, one can decorate those functions with functools.lru_cache with a suitable cache size, but that one doesn’t seem to exist in Python 2.7, ugh. And precomputing seems to be more suitable here anyway.

---

Also en.wikipedia claims the following:

No algorithm is known for computing any of these square-free factors which is faster than computing the complete prime factorization. In particular, there is no known polynomial-time algorithm for computing the square-free part of an integer, nor even for determining whether an integer is square-free.

So the current implementation is quite tight already; probably it can be optimized only to a small degree, and regarding only small inputs which hopefully are more common in computations.