]> git.ipfire.org Git - thirdparty/Python/cpython.git/commit
Issue #5512: speed up the long division algorithm for Python longs.
authorMark Dickinson <dickinsm@gmail.com>
Mon, 23 Mar 2009 18:25:13 +0000 (18:25 +0000)
committerMark Dickinson <dickinsm@gmail.com>
Mon, 23 Mar 2009 18:25:13 +0000 (18:25 +0000)
commit0b666bfdf94b04af370d28806f16a9977d6f5792
treec10773218ecd685b388676c601258cb3e38a8609
parent906f95e80bfdd801470cf8225ff9e6f99cd98187
Issue #5512: speed up the long division algorithm for Python longs.
The basic algorithm remains the same; the most significant speedups
come from the following three changes:

  (1) normalize by shifting instead of multiplying and dividing
  (2) the old algorithm usually did an unnecessary extra iteration of
      the outer loop; remove this.  As a special case, this means that
      long divisions with a single-digit result run twice as fast as
      before.
  (3) make inner loop much tighter.

Various benchmarks show speedups of between 50% and 150% for long
integer divisions and modulo operations.
Misc/NEWS
Objects/longobject.c