[Gmpcommit] /home/hgfiles/gmp: Rudimentarily document the MU code.
mercurial at gmplib.org
mercurial at gmplib.org
Tue Jan 12 00:32:57 CET 2010
details: /home/hgfiles/gmp/rev/95a804f5571b
changeset: 13367:95a804f5571b
user: Torbjorn Granlund <tege at gmplib.org>
date: Tue Jan 12 00:32:49 2010 +0100
description:
Rudimentarily document the MU code.
diffstat:
ChangeLog  2 ++
doc/gmp.texi  21 ++++++++++++++
2 files changed, 16 insertions(+), 7 deletions()
diffs (58 lines):
diff r bc2c19e257f1 r 95a804f5571b ChangeLog
 a/ChangeLog Tue Jan 12 00:18:22 2010 +0100
+++ b/ChangeLog Tue Jan 12 00:32:49 2010 +0100
@@ 1,5 +1,7 @@
20100112 Torbjorn Granlund <tege at gmplib.org>
+ * doc/gmp.texi (Blockwise Barrett Division): New node.
+
* mpn/generic/powm.c: Change some #if to plain 'if' to avoid fat build
problems.
diff r bc2c19e257f1 r 95a804f5571b doc/gmp.texi
 a/doc/gmp.texi Tue Jan 12 00:18:22 2010 +0100
+++ b/doc/gmp.texi Tue Jan 12 00:32:49 2010 +0100
@@ 8154,6 +8154,7 @@
* Single Limb Division::
* Basecase Division::
* Divide and Conquer Division::
+* BlockWise Barrett Division::
* Exact Division::
* Exact Remainder::
* Small Quotient Division::
@@ 8234,7 +8235,7 @@
divide for each of the Q quotient limbs.
 at node Divide and Conquer Division, Exact Division, Basecase Division, Division Algorithms
+ at node Divide and Conquer Division, Blockwise Barrett Division, Basecase Division, Division Algorithms
@subsection Divide and Conquer Division
For divisors larger than @code{DC_DIV_QR_THRESHOLD}, division is done by dividing.
@@ 8270,14 +8271,20 @@
N, log(N)}. In practice, at moderate to large sizes, a 2N at cross{}N division
is about 2 to 4 times slower than an N at cross{}N multiplication.
Newton's method used for division is asymptotically @math{O(M(N))} and should
therefore be superior to divide and conquer, but it's believed this would only
be for large to very large N.


 at node Exact Division, Exact Remainder, Divide and Conquer Division, Division Algorithms
+
+ at node Blockwise Barrett Division, Exact Division, Divide and Conquer Division, Division Algorithms
+ at subsection Divide and Conquer Division
+
+For the largest divisions, a blockwise Barrett division algorithm is used.
+Here, the divisor is inverted to a precision determined by the relative size
+of the dividend and divisor. Blocks of quotient limbs are then generated by
+multiplying blocks from the dividend by the inverse.
+
+
+ at node Exact Division, Exact Remainder, Blockwise Barrett Division, Division Algorithms
@subsection Exact Division
+
A socalled exact division is when the dividend is known to be an exact
multiple of the divisor. Jebelean's exact division algorithm uses this
knowledge to make some significant optimizations (@pxref{References}).
More information about the gmpcommit
mailing list