[Gmp-commit] /var/hg/gmp-5.0: 3 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Tue Mar 6 16:12:55 CET 2012
details: /var/hg/gmp-5.0/rev/cfe95bc3ef9e
changeset: 13569:cfe95bc3ef9e
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue Mar 06 15:55:25 2012 +0100
description:
tests/mpz/t-invert and invert documentation backported.
details: /var/hg/gmp-5.0/rev/f39705730f4b
changeset: 13570:f39705730f4b
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue Mar 06 16:03:53 2012 +0100
description:
Backport Toom'n'half documentation.
details: /var/hg/gmp-5.0/rev/9aaece0e5178
changeset: 13571:9aaece0e5178
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue Mar 06 16:12:45 2012 +0100
description:
Backported tests/mpn/logic.c
diffstat:
ChangeLog | 17 +++++++
doc/gmp.texi | 51 ++++++++++++++++----
tests/mpn/Makefile.am | 2 +-
tests/mpn/logic.c | 109 +++++++++++++++++++++++++++++++++++++++++++++
tests/mpz/Makefile.am | 6 +-
tests/mpz/t-invert.c | 120 ++++++++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 290 insertions(+), 15 deletions(-)
diffs (truncated from 419 to 300 lines):
diff -r 760a79b34400 -r 9aaece0e5178 ChangeLog
--- a/ChangeLog Sat Feb 11 10:52:46 2012 +0100
+++ b/ChangeLog Tue Mar 06 16:12:45 2012 +0100
@@ -1,3 +1,20 @@
+2012-03-04 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * tests/mpz/t-invert.c: Avoid testing mod 0.
+ * doc/gmp.texi (mpz_invert): Specify mod 0 is not handled.
+
+2012-02-24 Torbjorn Granlund <tege at gmplib.org>
+
+ * tests/mpn/logic.c: New file.
+ * tests/mpn/Makefile.am (check_PROGRAMS): Add logic.
+
+ * tests/mpz/t-invert.c: New file.
+ * tests/mpz/Makefile.am (check_PROGRAMS): Add t-invert.
+
+2012-02-11 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * doc/gmp.texi (Multiplication Algorithms): Add Toom[68]'n'half.
+
2012-02-10 Torbjorn Granlund <tege at gmplib.org>
* Version 5.0.4 released.
diff -r 760a79b34400 -r 9aaece0e5178 doc/gmp.texi
--- a/doc/gmp.texi Sat Feb 11 10:52:46 2012 +0100
+++ b/doc/gmp.texi Tue Mar 06 16:12:45 2012 +0100
@@ -15,7 +15,7 @@
arithmetic library, version @value{VERSION}.
Copyright 1991, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002,
-2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Free Software
+2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 Free Software
Foundation, Inc.
Permission is granted to copy, distribute and/or modify this document under
@@ -1040,9 +1040,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 Berkeley MP, @option{--enable-mpbsd}
@cindex Berkeley MP compatible functions
@@ -3610,8 +3610,9 @@
@cindex Inverse modulo functions
Compute the inverse of @var{op1} modulo @var{op2} and put the result in
@var{rop}. If the inverse exists, the return value is non-zero and @var{rop}
-will satisfy @math{0 @le{} @var{rop} < @var{op2}}. If an inverse doesn't exist
-the return value is zero and @var{rop} is undefined.
+will satisfy @math{0 < @var{rop} < @GMPabs{@var{op2}}}. If an inverse doesn't
+exist the return value is zero and @var{rop} is undefined. The behaviour of
+this function is undefined when @var{op2} is zero.
@end deftypefun
@deftypefun int mpz_jacobi (mpz_t @var{a}, mpz_t @var{b})
@@ -7453,7 +7454,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
@@ -7463,6 +7464,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
@@ -7479,6 +7482,7 @@
* Karatsuba Multiplication::
* Toom 3-Way Multiplication::
* Toom 4-Way Multiplication::
+* Higher degree Toom'n'half::
* FFT Multiplication::
* Other Multiplication::
* Unbalanced Multiplication::
@@ -7935,7 +7939,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
@@ -7973,7 +7977,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
@@ -8016,7 +8020,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
@@ -8143,7 +8172,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}
diff -r 760a79b34400 -r 9aaece0e5178 tests/mpn/Makefile.am
--- a/tests/mpn/Makefile.am Sat Feb 11 10:52:46 2012 +0100
+++ b/tests/mpn/Makefile.am Tue Mar 06 16:12:45 2012 +0100
@@ -22,7 +22,7 @@
LDADD = $(top_builddir)/tests/libtests.la $(top_builddir)/libgmp.la
check_PROGRAMS = t-asmtype t-aors_1 t-divrem_1 t-mod_1 t-fat t-get_d \
- t-instrument t-iord_u t-mp_bases t-perfsqr t-scan \
+ t-instrument t-iord_u t-mp_bases t-perfsqr t-scan logic \
t-toom22 t-toom32 t-toom33 t-toom42 t-toom43 t-toom44 \
t-toom52 t-toom53 t-toom62 t-toom63 t-toom6h t-toom8h \
t-mul t-mullo t-mulmod_bnm1 t-sqrmod_bnm1 \
diff -r 760a79b34400 -r 9aaece0e5178 tests/mpn/logic.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/mpn/logic.c Tue Mar 06 16:12:45 2012 +0100
@@ -0,0 +1,109 @@
+/* Test mpn_and, mpn_ior, mpn_xor, mpn_andn, mpn_iorn, mpn_xnor, mpn_nand, and
+ mpn_nior.
+
+Copyright 2011, 2012 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of the GNU Lesser General Public License as published by
+the Free Software Foundation; either version 3 of the License, or (at your
+option) any later version.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
+License for more details.
+
+You should have received a copy of the GNU Lesser General Public License
+along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
+
+
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "gmp.h"
+#include "gmp-impl.h"
+#include "tests.h"
+
+void
+check_one (mp_srcptr refp, mp_srcptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n, char *funcname)
+{
+ if (mpn_cmp (refp, rp, n))
+ {
+ printf ("ERROR in mpn_%s_n\n", funcname);
+ printf ("a: "); mpn_dump (ap, n);
+ printf ("b: "); mpn_dump (bp, n);
+ printf ("r: "); mpn_dump (rp, n);
+ printf ("ref: "); mpn_dump (refp, n);
+ abort();
+ }
+}
+
+int
+main (int argc, char **argv)
+{
+ mp_ptr ap, bp, rp, refp;
+ mp_size_t max_n, n;
+ gmp_randstate_ptr rands;
+ long test, reps = 1000;
+ TMP_SDECL;
+ TMP_SMARK;
+
+ tests_start ();
+ TESTS_REPS (reps, argv, argc);
+
+ rands = RANDS;
+
+ max_n = 32;
+
+ ap = TMP_SALLOC_LIMBS (max_n);
+ bp = TMP_SALLOC_LIMBS (max_n);
+ rp = TMP_SALLOC_LIMBS (max_n);
+ refp = TMP_SALLOC_LIMBS (max_n);
+
+ for (test = 0; test < reps; test++)
+ {
+ for (n = 1; n <= max_n; n++)
+ {
+ mpn_random2 (ap, n);
+ mpn_random2 (bp, n);
+
+ refmpn_and_n (refp, ap, bp, n);
+ mpn_and_n (rp, ap, bp, n);
+ check_one (refp, rp, ap, bp, n, "and");
+
+ refmpn_ior_n (refp, ap, bp, n);
+ mpn_ior_n (rp, ap, bp, n);
+ check_one (refp, rp, ap, bp, n, "ior");
+
+ refmpn_xor_n (refp, ap, bp, n);
+ mpn_xor_n (rp, ap, bp, n);
+ check_one (refp, rp, ap, bp, n, "xor");
+
+ refmpn_andn_n (refp, ap, bp, n);
+ mpn_andn_n (rp, ap, bp, n);
+ check_one (refp, rp, ap, bp, n, "andn");
+
+ refmpn_iorn_n (refp, ap, bp, n);
+ mpn_iorn_n (rp, ap, bp, n);
+ check_one (refp, rp, ap, bp, n, "iorn");
+
+ refmpn_nand_n (refp, ap, bp, n);
+ mpn_nand_n (rp, ap, bp, n);
+ check_one (refp, rp, ap, bp, n, "nand");
+
+ refmpn_nior_n (refp, ap, bp, n);
+ mpn_nior_n (rp, ap, bp, n);
+ check_one (refp, rp, ap, bp, n, "nior");
+
+ refmpn_xnor_n (refp, ap, bp, n);
+ mpn_xnor_n (rp, ap, bp, n);
+ check_one (refp, rp, ap, bp, n, "xnor");
+ }
+ }
+
+ TMP_SFREE;
+ tests_end ();
+ return 0;
+}
diff -r 760a79b34400 -r 9aaece0e5178 tests/mpz/Makefile.am
--- a/tests/mpz/Makefile.am Sat Feb 11 10:52:46 2012 +0100
+++ b/tests/mpz/Makefile.am Tue Mar 06 16:12:45 2012 +0100
@@ -1,6 +1,6 @@
## Process this file with automake to generate Makefile.in
-# Copyright 1996, 1997, 1999, 2000, 2001, 2002, 2003, 2009 Free Software
+# Copyright 1996, 1997, 1999, 2000, 2001, 2002, 2003, 2009, 2012 Free Software
# Foundation, Inc.
#
# This file is part of the GNU MP Library.
@@ -23,8 +23,8 @@
LDADD = $(top_builddir)/tests/libtests.la $(top_builddir)/libgmp.la
check_PROGRAMS = t-addsub t-cmp t-mul t-mul_i t-tdiv t-tdiv_ui t-fdiv \
- t-fdiv_ui t-cdiv_ui t-gcd t-gcd_ui t-lcm dive dive_ui t-sqrtrem convert io \
- t-inp_str logic bit t-powm t-powm_ui t-pow t-div_2exp reuse \
+ t-fdiv_ui t-cdiv_ui t-gcd t-gcd_ui t-lcm t-invert dive dive_ui t-sqrtrem \
+ convert io t-inp_str logic bit t-powm t-powm_ui t-pow t-div_2exp reuse \
t-root t-perfsqr t-perfpow t-jac t-bin t-get_d t-get_d_2exp t-get_si \
t-set_d t-set_si \
t-fac_ui t-fib_ui t-lucnum_ui t-scan t-fits \
diff -r 760a79b34400 -r 9aaece0e5178 tests/mpz/t-invert.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/mpz/t-invert.c Tue Mar 06 16:12:45 2012 +0100
@@ -0,0 +1,120 @@
+/* Test mpz_invert.
More information about the gmp-commit
mailing list