Author: Armin Rigo <[email protected]>
Branch:
Changeset: r68396:37f58b4c73ad
Date: 2013-12-07 12:07 +0100
http://bitbucket.org/pypy/pypy/changeset/37f58b4c73ad/
Log: Improve to decompose into odd factors only. It gives another close-
to-2x speed-up.
diff --git a/pypy/module/math/app_math.py b/pypy/module/math/app_math.py
--- a/pypy/module/math/app_math.py
+++ b/pypy/module/math/app_math.py
@@ -5,6 +5,7 @@
if fl != x:
raise ValueError("float arguments must be integral")
x = fl
+
if x <= 100:
if x < 0:
raise ValueError("x must be >= 0")
@@ -12,17 +13,26 @@
for i in range(2, x + 1):
res *= i
return res
-
+
#Experimentally this gap seems good
gap = max(100, x>>7)
- def _fac(low, high):
+ def _fac_odd(low, high):
if low+gap >= high:
t = 1
- for i in range(low, high):
+ for i in range(low, high, 2):
t *= i
return t
- mid = (low + high) >> 1
- return _fac(low, mid) * _fac(mid, high)
-
- return _fac(1, x+1)
+ 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
diff --git a/pypy/module/math/test/test_factorial.py
b/pypy/module/math/test/test_factorial.py
--- a/pypy/module/math/test/test_factorial.py
+++ b/pypy/module/math/test/test_factorial.py
@@ -11,12 +11,19 @@
def test_timing():
py.test.skip("for manual running only")
- x = 59999
+ import time
+ x = 5000
+ repeat = 1000
+ r1 = app_math.factorial(x)
+ r2 = math.factorial(x)
+ assert r1 == r2
t1 = time.time()
- r1 = app_math.factorial(x)
+ for i in range(repeat):
+ app_math.factorial(x)
t2 = time.time()
- r2 = math.factorial(x)
+ for i in range(repeat):
+ math.factorial(x)
t3 = time.time()
assert r1 == r2
- print t2 - t1
- print t3 - t2
+ print (t2 - t1) / repeat
+ print (t3 - t2) / repeat
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
