[Python-checkins] python/dist/src/Objects longobject.c,1.126,1.127

2002年8月12日 10:36:05 -0700

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);