1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
import sys
try:
from _operator import index
except ImportError:
pass # for tests only
def factorial(x):
"""factorial(x) -> Integral
"Find x!. Raise a ValueError if x is negative or non-integral."""
if isinstance(x, float):
fl = int(x)
if fl != x:
raise ValueError("float arguments must be integral")
x = fl
if x > sys.maxsize:
raise OverflowError("Too large for a factorial")
if x <= 100:
if x < 0:
raise ValueError("x must be >= 0")
res = 1
for i in range(2, x + 1):
res *= i
return res
# Experimentally this gap seems good
gap = max(100, x >> 7)
def _fac_odd(low, high):
if low + gap >= high:
t = 1
for i in range(low, high, 2):
t *= i
return t
mid = ((low + high) >> 1) | 1
return _fac_odd(low, mid) * _fac_odd(mid, high)
def _fac1(x):
if x <= 2:
return 1, 1, x - 1
x2 = x >> 1
f, g, shift = _fac1(x2)
g *= _fac_odd((x2 + 1) | 1, x + 1)
return (f * g, g, shift + x2)
res, _, shift = _fac1(x)
return res << shift
def gcd(x, y):
"""greatest common divisor of x and y"""
x = abs(index(x))
y = abs(index(y))
while x > 0:
x, y = y % x, x
return y
|
