Mailing List Archive

Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv4820/python/Objects

Modified Files:
longobject.c
Log Message:
k_mul() and long_mul(): I'm confident that the Karatsuba algorithm is
correct now, so added some final comments, did some cleanup, and enabled
it for all long-int multiplies. The KARAT envar no longer matters,
although I left some #if 0'ed code in there for my own use (temporary).
k_mul() is still much slower than x_mul() if the inputs have very
differenent sizes, and that still needs to be addressed.


Index: longobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/longobject.c,v
retrieving revision 1.126
retrieving revision 1.127
diff -C2 -d -r1.126 -r1.127
*** longobject.c 12 Aug 2002 15:08:20 -0000 1.126
--- longobject.c 12 Aug 2002 17:36:03 -0000 1.127
***************
*** 1646,1650 ****
if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;

! /* Allocate result space. */
ret = _PyLong_New(asize + bsize);
if (ret == NULL) goto fail;
--- 1646,1666 ----
if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;

! /* The plan:
! * 1. Allocate result space (asize + bsize digits: that's always
! * enough).
! * 2. Compute ah*bh, and copy into result at 2*shift.
! * 3. Compute al*bl, and copy into result at 0. Note that this
! * can't overlap with #2.
! * 4. Subtract al*bl from the result, starting at shift. This may
! * underflow (borrow out of the high digit), but we don't care:
! * we're effectively doing unsigned arithmetic mod
! * BASE**(sizea + sizeb), and so long as the *final* result fits,
! * borrows and carries out of the high digit can be ignored.
! * 5. Subtract ah*bh from the result, starting at shift.
! * 6. Compute (ah+al)*(bh+bl), and add it into the result starting
! * at shift.
! */
!
! /* 1. Allocate result space. */
ret = _PyLong_New(asize + bsize);
if (ret == NULL) goto fail;
***************
*** 1654,1658 ****
#endif

! /* t1 <- ah*bh, and copy into high digits of result. */
if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
assert(t1->ob_size >= 0);
--- 1670,1674 ----
#endif

! /* 2. t1 <- ah*bh, and copy into high digits of result. */
if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
assert(t1->ob_size >= 0);
***************
*** 1667,1671 ****
i * sizeof(digit));

! /* t2 <- al*bl, and copy into the low digits. */
if ((t2 = k_mul(al, bl)) == NULL) {
Py_DECREF(t1);
--- 1683,1687 ----
i * sizeof(digit));

! /* 3. t2 <- al*bl, and copy into the low digits. */
if ((t2 = k_mul(al, bl)) == NULL) {
Py_DECREF(t1);
***************
*** 1681,1693 ****
memset(ret->ob_digit + t2->ob_size, 0, i * sizeof(digit));

! /* Subtract ah*bh (t1) and al*bl (t2) from "the middle" digits. */
i = ret->ob_size - shift; /* # digits after shift */
! v_isub(ret->ob_digit + shift, i, t2->ob_digit, t2->ob_size);
Py_DECREF(t2);

! v_isub(ret->ob_digit + shift, i, t1->ob_digit, t1->ob_size);
Py_DECREF(t1);

! /* t3 <- (ah+al)(bh+bl) */
if ((t1 = x_add(ah, al)) == NULL) goto fail;
Py_DECREF(ah);
--- 1697,1711 ----
memset(ret->ob_digit + t2->ob_size, 0, i * sizeof(digit));

! /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2). We do al*bl first
! * because it's fresher in cache.
! */
i = ret->ob_size - shift; /* # digits after shift */
! (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, t2->ob_size);
Py_DECREF(t2);

! (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, t1->ob_size);
Py_DECREF(t1);

! /* 6. t3 <- (ah+al)(bh+bl), and add into result. */
if ((t1 = x_add(ah, al)) == NULL) goto fail;
Py_DECREF(ah);
***************
*** 1710,1715 ****

/* Add t3. */
! v_iadd(ret->ob_digit + shift, ret->ob_size - shift,
! t3->ob_digit, t3->ob_size);
Py_DECREF(t3);

--- 1728,1732 ----

/* Add t3. */
! (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, t3->ob_size);
Py_DECREF(t3);

***************
*** 1744,1751 ****
--- 1761,1772 ----
}

+ #if 0
if (Py_GETENV("KARAT") != NULL)
z = k_mul(a, b);
else
z = x_mul(a, b);
+ #else
+ z = k_mul(a, b);
+ #endif
if(z == NULL) {
Py_DECREF(a);