Intermediate changes

commit_hash:8c2a03558616560deb74e3412a33769b4f519a0a

1 files changed, 132 insertions, 8 deletions

diff --git a/contrib/python/more-itertools/py3/more_itertools/recipes.py b/contrib/python/more-itertools/py3/more_itertools/recipes.py
index 67f76fa899e..5a11fc5a304 100644
--- a/contrib/python/more-itertools/py3/more_itertools/recipes.py
+++ b/contrib/python/more-itertools/py3/more_itertools/recipes.py
@@ -13,7 +13,7 @@ import operator
 
 from collections import deque
 from collections.abc import Sized
-from functools import partial, reduce
+from functools import lru_cache, partial
 from itertools import (
     chain,
     combinations,
@@ -42,8 +42,10 @@ __all__ = [
     'factor',
     'flatten',
     'grouper',
+    'is_prime',
     'iter_except',
     'iter_index',
+    'loops',
     'matmul',
     'ncycles',
     'nth',
@@ -872,8 +874,10 @@ def polynomial_from_roots(roots):
     >>> polynomial_from_roots(roots)  # x^3 - 4 * x^2 - 17 * x + 60
     [1, -4, -17, 60]
     """
-    factors = zip(repeat(1), map(operator.neg, roots))
-    return list(reduce(convolve, factors, [1]))
+    poly = [1]
+    for root in roots:
+        poly = list(convolve(poly, (1, -root)))
+    return poly
 
 
 def iter_index(iterable, value, start=0, stop=None):
@@ -1005,20 +1009,56 @@ def matmul(m1, m2):
     return batched(starmap(_sumprod, product(m1, transpose(m2))), n)
 
 
+def _factor_pollard(n):
+    # Return a factor of n using Pollard's rho algorithm
+    gcd = math.gcd
+    for b in range(1, n - 2):
+        x = y = 2
+        d = 1
+        while d == 1:
+            x = (x * x + b) % n
+            y = (y * y + b) % n
+            y = (y * y + b) % n
+            d = gcd(x - y, n)
+        if d != n:
+            return d
+    raise ValueError('prime or under 5')
+
+
+_primes_below_211 = tuple(sieve(211))
+
+
 def factor(n):
     """Yield the prime factors of n.
 
     >>> list(factor(360))
     [2, 2, 2, 3, 3, 5]
+
+    Finds small factors with trial division.  Larger factors are
+    either verified as prime with ``is_prime`` or split into
+    smaller factors with Pollard's rho algorithm.
     """
-    for prime in sieve(math.isqrt(n) + 1):
+
+    # Corner case reduction
+    if n < 2:
+        return
+
+    # Trial division reduction
+    for prime in _primes_below_211:
         while not n % prime:
             yield prime
             n //= prime
-            if n == 1:
-                return
-    if n > 1:
-        yield n
+
+    # Pollard's rho reduction
+    primes = []
+    todo = [n] if n > 1 else []
+    for n in todo:
+        if n < 211**2 or is_prime(n):
+            primes.append(n)
+        else:
+            fact = _factor_pollard(n)
+            todo += (fact, n // fact)
+    yield from sorted(primes)
 
 
 def polynomial_eval(coefficients, x):
@@ -1073,3 +1113,87 @@ def totient(n):
     for prime in set(factor(n)):
         n -= n // prime
     return n
+
+
+# Miller–Rabin primality test: https://oeis.org/A014233
+_perfect_tests = [
+    (2047, (2,)),
+    (9080191, (31, 73)),
+    (4759123141, (2, 7, 61)),
+    (1122004669633, (2, 13, 23, 1662803)),
+    (2152302898747, (2, 3, 5, 7, 11)),
+    (3474749660383, (2, 3, 5, 7, 11, 13)),
+    (18446744073709551616, (2, 325, 9375, 28178, 450775, 9780504, 1795265022)),
+    (
+        3317044064679887385961981,
+        (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41),
+    ),
+]
+
+
+@lru_cache
+def _shift_to_odd(n):
+    'Return s, d such that 2**s * d == n'
+    s = ((n - 1) ^ n).bit_length() - 1
+    d = n >> s
+    assert (1 << s) * d == n and d & 1 and s >= 0
+    return s, d
+
+
+def _strong_probable_prime(n, base):
+    assert (n > 2) and (n & 1) and (2 <= base < n)
+
+    s, d = _shift_to_odd(n - 1)
+
+    x = pow(base, d, n)
+    if x == 1 or x == n - 1:
+        return True
+
+    for _ in range(s - 1):
+        x = x * x % n
+        if x == n - 1:
+            return True
+
+    return False
+
+
+def is_prime(n):
+    """Return ``True`` if *n* is prime and ``False`` otherwise.
+
+    >>> is_prime(37)
+    True
+    >>> is_prime(3 * 13)
+    False
+    >>> is_prime(18_446_744_073_709_551_557)
+    True
+
+    This function uses the Miller-Rabin primality test, which can return false
+    positives for very large inputs. For values of *n* below 10**24
+    there are no false positives. For larger values, there is less than
+    a 1 in 2**128 false positive rate. Multiple tests can further reduce the
+    chance of a false positive.
+    """
+    if n < 17:
+        return n in {2, 3, 5, 7, 11, 13}
+    if not (n & 1 and n % 3 and n % 5 and n % 7 and n % 11 and n % 13):
+        return False
+    for limit, bases in _perfect_tests:
+        if n < limit:
+            break
+    else:
+        bases = [randrange(2, n - 1) for i in range(64)]
+    return all(_strong_probable_prime(n, base) for base in bases)
+
+
+def loops(n):
+    """Returns an iterable with *n* elements for efficient looping.
+    Like ``range(n)`` but doesn't create integers.
+
+    >>> i = 0
+    >>> for _ in loops(5):
+    ...     i += 1
+    >>> i
+    5
+
+    """
+    return repeat(None, n)