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