[Sven R. Kunze <srku...@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). _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
