Commits

Armin Rigo  committed 37f58b4

Improve to decompose into odd factors only. It gives another
close-to-2x speed-up.

  • Participants
  • Parent commits 0046a4c

Comments (0)

Files changed (2)

File pypy/module/math/app_math.py

         if fl != x:
             raise ValueError("float arguments must be integral")
         x = fl
+
     if x <= 100:
         if x < 0:
             raise ValueError("x must be >= 0")
         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

File pypy/module/math/test/test_factorial.py

 
 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