[Gmp-commit] /var/hg/gmp: doc: Add Toom[68]'n'half

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/beb71a65699c
changeset: 14628:beb71a65699c
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Sun Feb 12 17:39:11 2012 +0100
description:
doc: Add Toom[68]'n'half

diffstat:

 ChangeLog    |   1 +
 doc/gmp.texi |  44 ++++++++++++++++++++++++++++++++++++--------
 2 files changed, 37 insertions(+), 8 deletions(-)

diffs (114 lines):

diff -r d535babf9ec9 -r beb71a65699c ChangeLog
--- a/ChangeLog	Sat Feb 11 16:17:09 2012 +0100
+++ b/ChangeLog	Sun Feb 12 17:39:11 2012 +0100
@@ -5,6 +5,7 @@
 2012-02-11 Marco Bodrato <bodrato at mail.dm.unipi.it>
 
 	* doc/gmp.texi (Factorial): Shortly describe current algorithm.
+	(Multiplication Algorithms): Add Toom[68]'n'half, (too) shortly.
 	* gmp-impl.h (ASSERT_ALWAYS): Consider failures UNLIKELY.
 
 2012-02-10  Niels Möller  <nisse at lysator.liu.se>
diff -r d535babf9ec9 -r beb71a65699c doc/gmp.texi
--- a/doc/gmp.texi	Sat Feb 11 16:17:09 2012 +0100
+++ b/doc/gmp.texi	Sun Feb 12 17:39:11 2012 +0100
@@ -1034,9 +1034,9 @@
 @item FFT Multiplication, @option{--disable-fft}
 @cindex FFT multiplication
 @cindex @code{--disable-fft}
-By default multiplications are done using Karatsuba, 3-way Toom, and
-Fermat FFT at .  The FFT is only used on large to very large operands and can be
-disabled to save code size if desired.
+By default multiplications are done using Karatsuba, 3-way Toom, higher degree
+Toom, and Fermat FFT at .  The FFT is only used on large to very large operands
+and can be disabled to save code size if desired.
 
 @item Assertion Checking, @option{--enable-assert}
 @cindex Assertion checking
@@ -7312,7 +7312,7 @@
 @section Multiplication
 @cindex Multiplication algorithms
 
-N at cross{}N limb multiplications and squares are done using one of five
+N at cross{}N limb multiplications and squares are done using one of seven
 algorithms, as the size N increases.
 
 @quotation
@@ -7322,6 +7322,8 @@
 @item Karatsuba @tab @code{MUL_TOOM22_THRESHOLD}
 @item Toom-3    @tab @code{MUL_TOOM33_THRESHOLD}
 @item Toom-4    @tab @code{MUL_TOOM44_THRESHOLD}
+ at item Toom-6.5  @tab @code{MUL_TOOM6H_THRESHOLD}
+ at item Toom-8.5  @tab @code{MUL_TOOM8H_THRESHOLD}
 @item FFT       @tab @code{MUL_FFT_THRESHOLD}
 @end multitable
 @end quotation
@@ -7338,6 +7340,7 @@
 * Karatsuba Multiplication::
 * Toom 3-Way Multiplication::
 * Toom 4-Way Multiplication::
+* Higher degree Toom'n'half::
 * FFT Multiplication::
 * Other Multiplication::
 * Unbalanced Multiplication::
@@ -7794,7 +7797,7 @@
 Squaring follows the same procedure as multiplication, but there's only one
 @math{X(t)} and it's evaluated at the 5 points, and those values squared to
 give values of @math{W(t)}.  The interpolation is then identical, and in fact
-the same @code{toom3_interpolate} subroutine is used for both squaring and
+the same @code{toom_interpolate_5pts} subroutine is used for both squaring and
 multiplying.
 
 Toom-3 is asymptotically @math{O(N^@W{1.465})}, the exponent being
@@ -7832,7 +7835,7 @@
 done.
 
 
- at node Toom 4-Way Multiplication, FFT Multiplication, Toom 3-Way Multiplication, Multiplication Algorithms
+ at node Toom 4-Way Multiplication, Higher degree Toom'n'half, Toom 3-Way Multiplication, Multiplication Algorithms
 @subsection Toom 4-Way Multiplication
 @cindex Toom multiplication
 
@@ -7875,7 +7878,32 @@
 original size each.
 
 
- at node FFT Multiplication, Other Multiplication, Toom 4-Way Multiplication, Multiplication Algorithms
+ at node Higher degree Toom'n'half, FFT Multiplication, Toom 4-Way Multiplication, Multiplication Algorithms
+ at subsection Higher degree Toom'n'half
+ at cindex Toom multiplication
+
+The Toom algorithms described above (@pxref{Toom 3-Way Multiplication},
+ at pxref{Toom 4-Way Multiplication}) generalizes to split into an arbitrary
+number of pieces. In general a split of two equally long operands into
+ at math{r} pieces leads to evaluations and pointwise multiplications done at
+ at m{2r-1,2*r-1} points. To fully exploit symmetries it would be better to have
+a multiple of 4 points, that's why for higher degree Toom'n'half is used.
+
+Toom'n'half means that the existence of one more piece is considered for a
+single operand. It can be virtual, i.e. zero, or real, when the two operand
+are not exactly balanced. By chosing an even @math{r},
+Toom- at m{r{1\over2},r+1/2} requires @math{2r} points, a multiple of four.
+
+The four-plets of points inlcude 0, @m{\infty,inf}, +1, -1 and
+ at m{\pm2^i,+-2^i}, @m{\pm2^{-i},+-2^-i} . Each of them giving shortcuts for the
+evaluation phase and for some steps in the interpolation phase. Further tricks
+are used to reduce the memory footprint of the whole multiplication algorithm
+to a memory buffer equanl in size to the result of the product.
+
+Current GMP uses both Toom-6'n'half and Toom-8'n'half.
+
+
+ at node FFT Multiplication, Other Multiplication, Higher degree Toom'n'half, Multiplication Algorithms
 @subsection FFT Multiplication
 @cindex FFT multiplication
 @cindex Fast Fourier Transform
@@ -8002,7 +8030,7 @@
 In general a split into @math{r+1} pieces is made, and evaluations and
 pointwise multiplications done at @m{2r+1,2*r+1} points.  A 4-way split does 7
 pointwise multiplies, 5-way does 9, etc.  Asymptotically an @math{(r+1)}-way
-algorithm is @m{O(N^{log(2r+1)/log(r+1)}, O(N^(log(2*r+1)/log(r+1)))}.  Only
+algorithm is @m{O(N^{log(2r+1)/log(r+1)}), O(N^(log(2*r+1)/log(r+1)))}.  Only
 the pointwise multiplications count towards big- at math{O} complexity, but the
 time spent in the evaluate and interpolate stages grows with @math{r} and has
 a significant practical impact, with the asymptotic advantage of each @math{r}