From 115c888b97125e31851fc64cc0292c4fc3b122dd Mon Sep 17 00:00:00 2001 From: Tim Peters Date: Mon, 12 Aug 2002 18:25:43 +0000 Subject: [PATCH] x_mul(): Made life easier for C optimizers in the "grade school" algorithm. MSVC 6 wasn't impressed . Something odd: the x_mul algorithm appears to get substantially worse than quadratic time as the inputs grow larger: bits in each input x_mul time k_mul time ------------------ ---------- ---------- 15360 0.01 0.00 30720 0.04 0.01 61440 0.16 0.04 122880 0.64 0.14 245760 2.56 0.40 491520 10.76 1.23 983040 71.28 3.69 1966080 459.31 11.07 That is, x_mul is perfectly quadratic-time until a little burp at 2.56->10.76, and after that goes to hell in a hurry. Under Karatsuba, doubling the input size "should take" 3 times longer instead of 4, and that remains the case throughout this range. I conclude that my "be nice to the cache" reworkings of k_mul() are paying. --- Objects/longobject.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) diff --git a/Objects/longobject.c b/Objects/longobject.c index 0eefc90b1e..0801e64981 100644 --- a/Objects/longobject.c +++ b/Objects/longobject.c @@ -1539,20 +1539,21 @@ x_mul(PyLongObject *a, PyLongObject *b) twodigits carry = 0; twodigits f = a->ob_digit[i]; int j; + digit *pz = z->ob_digit + i; SIGCHECK({ Py_DECREF(z); return NULL; }) for (j = 0; j < size_b; ++j) { - carry += z->ob_digit[i+j] + b->ob_digit[j] * f; - z->ob_digit[i+j] = (digit) (carry & MASK); + carry += *pz + b->ob_digit[j] * f; + *pz++ = (digit) (carry & MASK); carry >>= SHIFT; } for (; carry != 0; ++j) { assert(i+j < z->ob_size); - carry += z->ob_digit[i+j]; - z->ob_digit[i+j] = (digit) (carry & MASK); + carry += *pz; + *pz++ = (digit) (carry & MASK); carry >>= SHIFT; } } -- 2.50.1