From dcdb435cfa3c8642fb38fdb7c3e282422faa9707 Mon Sep 17 00:00:00 2001 From: Kirill Smelkov Date: Sat, 9 Feb 2008 10:59:27 +0300 Subject: [PATCH] numbers: speedup gcd MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit I think there is no reason to use @Memoizer for (almost) internal numbers.gcd . In my view Memoizer is slow because at least it checks its args. I propose we use direct approach in performance critical things -- direct cache without typechecks. We can always wrap such caching with a decorator if we find a way not to degrade performance. Timing ------ from sympy.core.numbers import gcd as gcd_ %timeit %timeit %timeit gcd_(1,1) gcd_(23,17) gcd_(60,3600) old: 10.7 µs 10.7 µs 10.7 µs new: 3.07 µs 3.07 µs 3.24 µs --- sympy/core/numbers.py | 17 +++++++++++++---- 1 file changed, 13 insertions(+), 4 deletions(-) diff --git a/sympy/core/numbers.py b/sympy/core/numbers.py index d5a9a6e..e880491 100644 --- a/sympy/core/numbers.py +++ b/sympy/core/numbers.py @@ -9,14 +9,23 @@ from power import integer_nthroot # from mul import Mul /cyclic/ # from power import Pow /cyclic/ -@Memoizer((int, long), (int, long)) +# (a,b) -> gcd(a,b) +_gcdcache = {} + +# TODO caching with decorator, but not to degrade performance def gcd(a, b): """ Returns the Greatest Common Divisor, implementing Euclid's algorithm. """ - while a: - a, b = b%a, a - return b + try: + return _gcdcache[(a,b)] + except KeyError: + key = (a,b) + while a: + a, b = b%a, a + + _gcdcache[key] = b + return b @Memoizer((int, long), return_value_converter = lambda d: d.copy()) def factor_trial_division(n): -- 2.11.4.GIT