[Sven R. Kunze <srkunze at mail.de>] > What about > > diff = x - x_base > if diff and gcd(diff, n) > 1: > return gcd(diff, n) > > # or > > if (x - x_base) and gcd(x - x_base, n) > 1: > return gcd(x - x_base, n) > > > and have the interpreter handle the optimization, or apply an lru_cache? ;-) Surely you're joking. This is math.gcd(), which is expensive for multi-thousand bit integers, and the interpreter knows nothing about it. Adding a cache of _any_ kind (LRU or otherwise) would make it even slower (in the application, there's no reason to expect that x - x_base will repeat a value before O(sqrt(n)) iterations, which itself can be thousands of bits - a cache hit would be a miracle).
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4