Author: stian
Branch: improve-rbigint
Changeset: r56325:2e062df94210
Date: 2012-06-24 21:49 +0200
http://bitbucket.org/pypy/pypy/changeset/2e062df94210/
Log: Add speedup for all (power of two)**num.
One of the tests ((2**31)**(2**31)) is now 100 times faster (this
beats CPython, and even C)
diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -8,7 +8,7 @@
from pypy.rpython.lltypesystem import lltype, rffi
from pypy.rpython import extregistry
-import math, sys
+import math, sys, array
# note about digit sizes:
# In division, the native integer type must be able to hold
@@ -459,7 +459,9 @@
"cannot be negative when 3rd argument specified")
# XXX failed to implement
raise ValueError("bigint pow() too negative")
-
+
+ size_b = b.numdigits()
+
if c is not None:
if c.sign == 0:
raise ValueError("pow() 3rd argument cannot be 0")
@@ -483,9 +485,8 @@
a, temp = a.divmod(c)
a = temp
- size_b = b.numdigits()
-
- if not c and size_b == 1 and a.sign == 1:
+
+ elif size_b == 1 and a.sign == 1:
digit = b.digit(0)
if digit == 0:
return rbigint([ONEDIGIT], 1)
@@ -495,8 +496,8 @@
adigit = a.digit(0)
if adigit == 1:
return rbigint([ONEDIGIT], 1)
- elif adigit == 2:
- return a.lshift(digit-1)
+ elif adigit & (adigit - 1) == 0:
+ return a.lshift(((digit-1)*(ptwotable[adigit]-1)) +
digit-1)
# At this point a, b, and c are guaranteed non-negative UNLESS
# c is NULL, in which case a may be negative. */
@@ -518,6 +519,7 @@
z = _help_mult(z, a, c)
j >>= 1
size_b -= 1
+
else:
# Left-to-right 5-ary exponentiation (HAC Algorithm 14.82)
# This is only useful in the case where c != None.
diff --git a/pypy/rlib/test/test_rbigint.py b/pypy/rlib/test/test_rbigint.py
--- a/pypy/rlib/test/test_rbigint.py
+++ b/pypy/rlib/test/test_rbigint.py
@@ -1,6 +1,6 @@
from __future__ import division
import py
-import operator, sys
+import operator, sys, array
from random import random, randint, sample
from pypy.rlib.rbigint import rbigint, SHIFT, MASK, KARATSUBA_CUTOFF
from pypy.rlib.rbigint import _store_digit
diff --git a/pypy/translator/goal/targetbigintbenchmark.py
b/pypy/translator/goal/targetbigintbenchmark.py
--- a/pypy/translator/goal/targetbigintbenchmark.py
+++ b/pypy/translator/goal/targetbigintbenchmark.py
@@ -20,25 +20,34 @@
6.647562
Pypy with improvements:
- 9.474363
- 5.797121
- 10.068798
- 14.770187
- 1.620009
- 12.054951
- 14.292367
- 6.440351
+ 9.451896
+ 1.122038
+ 5.787821
+ 9.937016
+ 14.927304
+ 0.016683
+ 12.018289
+ 14.261727
+ 6.434917
"""
- t = time()
+ """t = time()
num = rbigint.fromint(10000000)
for n in xrange(10000):
rbigint.pow(rbigint.fromint(2), num)
+ print time() - t"""
+
+ t = time()
+ num = rbigint.fromint(100000000)
+ for n in xrange(31):
+ rbigint.pow(rbigint.pow(rbigint.fromint(2), rbigint.fromint(n)), num)
+
+
print time() - t
-
+
t = time()
num = rbigint.pow(rbigint.fromint(10000), rbigint.fromint(2 ** 8))
for n in xrange(60000):
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit
