diff options
author | Tim Peters <tim.peters@gmail.com> | 2002-08-16 03:40:07 +0000 |
---|---|---|
committer | Tim Peters <tim.peters@gmail.com> | 2002-08-16 03:40:07 +0000 |
commit | 65c63a54b4dfa7c44f7e6e45d1a1e0357f380005 (patch) | |
tree | eb8287fa76cd80f8c331b0e99570f0a25a50f1d0 /Misc | |
parent | 3e332bd849fcd03714bd5887e886cf6aadb70612 (diff) | |
download | cpython-65c63a54b4dfa7c44f7e6e45d1a1e0357f380005.tar.gz |
Newly-relaxed limits on random.randrange(). Also added some info about
Karatsuba's better cache behavior with extremely large multiplicands.
Diffstat (limited to 'Misc')
-rw-r--r-- | Misc/NEWS | 17 |
1 files changed, 12 insertions, 5 deletions
@@ -93,11 +93,13 @@ Core and builtins 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 gives a very nice speedup when it applies, but - a package devoted to fast large-integer arithmetic should run circles - around it. + be better or worse than that, depending on platform quirks. Besides + the O() improvement in raw instruction count, the Karatsuba algorithm + appears to have much better cache behavior on extremely large integers + (starting in the ballpark of a million bits). Note that this is a + simple implementation, and there's no intent here to compete with, + e.g., GMP. It gives a very nice speedup when it applies, but a package + devoted to fast large-integer arithmetic should run circles around it. - u'%c' will now raise a ValueError in case the argument is an integer outside the valid range of Unicode code point ordinals. @@ -296,6 +298,11 @@ Extension modules Library +- random.randrange(-sys.maxint-1, sys.maxint) no longer raises + OverflowError. That is, it now accepts any combination of 'start' + and 'stop' arguments so long as each is in the range of Python's + bounded integers. + - New "algorithms" module: heapq, implements a heap queue. Thanks to Kevin O'Connor for the code and François Pinard for an entertaining write-up explaining the theory and practical uses of heaps. |