[Gmp-commit] /home/hgfiles/gmp: Rudimentarily document the MU code.

[mercurial at gmplib.org]

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 @@
 2010-01-12  Torbjorn Granlund  <tege at gmplib.org>
 
+	* doc/gmp.texi (Block-wise 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::
+* Block-Wise 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, Block-wise 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 Block-wise Barrett Division, Exact Division, Divide and Conquer Division, Division Algorithms
+ at subsection Divide and Conquer Division
+
+For the largest divisions, a block-wise 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, Block-wise Barrett Division, Division Algorithms
 @subsection Exact Division
 
+
 A so-called 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}).