[Python-checkins] python/dist/src/Misc NEWS,1.464,1.465

[tim_one@users.sourceforge.net]

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

Modified Files:
	NEWS 
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: NEWS
===================================================================
RCS file: /cvsroot/python/python/dist/src/Misc/NEWS,v
retrieving revision 1.464
retrieving revision 1.465
diff -C2 -d -r1.464 -r1.465
*** NEWS	12 Aug 2002 03:42:03 -0000	1.464
--- NEWS	12 Aug 2002 17:36:02 -0000	1.465
***************
*** 58,64 ****
  Core and builtins
  
! - XXX Karatsuba multiplication.  This is currently used if and only
!   if envar KARAT exists.  It needs more correctness and speed testing,
!   the latter especially with unbalanced bit lengths.
  
  - u'%c' will now raise a ValueError in case the argument is an
--- 58,71 ----
  Core and builtins
  
! - When multiplying very large integers, a version of the so-called
!   Karatsuba algorithm is now used.  This is most effective if the
!   inputs have roughly the same size.  If they both have about N digits,
!   Karatsuba multiplication has O(N**1.58) runtime (the exponent is
!   log_base_2(3)) instead of the previous O(N**2).  Measured results may
!   be better or worse than that, depending on platform quirks.  Note that
!   this is a simple implementation, and there's no intent here to compete
!   with, e.g., gmp.  It simply gives a very nice speedup when it applies.
!   XXX Karatsuba multiplication can be slower when the inputs have very
!   XXX different sizes.
  
  - u'%c' will now raise a ValueError in case the argument is an