Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimizing isqrt and fsqrt #6

Open
arseniiv opened this issue Jun 23, 2020 · 0 comments
Open

Optimizing isqrt and fsqrt #6

arseniiv opened this issue Jun 23, 2020 · 0 comments

Comments

@arseniiv
Copy link
Contributor

arseniiv commented Jun 23, 2020

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant