Repository navigation
bpo-40028: Add is_prime, factorise, previous_prime and next_prime - #19918
remilapeyre wants to merge 3 commits into
Conversation
Sorry, something went wrong.
| i += 1 | ||
|
|
||
|
|
||
| def _factorise(n): |
There was a problem hiding this comment.
Something like this would help to not exceed maximum recursion depth:
def _factorise(n):
stack = [n]
while stack:
n = stack.pop()
if is_prime(n):
yield n
else:
d = _rho_pollard(n)
stack += [n//d, d]_factorise could perhaps then be in-lined, since it seems like factorise doesn't do too much on its own.
This then passes the test set(factorise(2**10000)) == {2}.
Sorry, something went wrong.
There was a problem hiding this comment.
Thanks!
Sorry, something went wrong.
| while q & 1 == 0: | ||
| t += 1 | ||
| q >>= 1 | ||
| u = (n-1)//(2**t) |
There was a problem hiding this comment.
Is there a reason to recompute u here when its value should be the same as q?
Sorry, something went wrong.
| n -= 2 | ||
|
|
||
|
|
||
| def _rho_pollard(n): |
There was a problem hiding this comment.
The following should be exactly the same algorithm, just refactored a little bit, and it runs a little faster for a few tests by my measurements.
def _rho_pollard(n):
# From https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
# and https://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algorithm
tortoise = hare = 2
power = 1
_gcd = gcd
_repeat = itertools.repeat
while True:
# Double the length of the run each time
for _ in _repeat(None, power):
hare = (hare**2 + 1) % n
d = _gcd(hare-tortoise, n)
if d == 1:
continue
elif d == n:
# failure; start another
tortoise = hare = randrange(n)
power = 1
break
else:
return d
else: # no break
tortoise = hare
power *= 2Changes (feel free to pick and choose as you desire):
- starting at 2 rather than random seems to do good things
- Limit the Python int comparisons to one per inner loop
- Factor out the inner loop as a repeat (a little faster than range()), making c code do the comparisons
- making _gcd and _repeat local variables helps a little.
Sorry, something went wrong.
Co-authored-by: Dennis Sweeney <36520290+sweeneyde@users.noreply.github.com>
tiran
left a comment
There was a problem hiding this comment.
The BPO was closed by @mdickinson
I suggest that your PR into a PyPI package and get feedback from the community.
Sorry, something went wrong.
https://bugs.python.org/issue40028