[Gmp-commit] /home/hgfiles/gmp: File removed. All references purged.
mercurial at gmplib.org
mercurial at gmplib.org
Sun Dec 20 23:13:44 CET 2009
details: /home/hgfiles/gmp/rev/6e09fac92fc2
changeset: 13147:6e09fac92fc2
user: Torbjorn Granlund <tege at gmplib.org>
date: Sun Dec 20 23:13:41 2009 +0100
description:
File removed. All references purged.
diffstat:
ChangeLog | 2 +
configure.in | 2 +-
doc/gmp.texi | 38 +++------------
gmp-h.in | 3 -
mpn/generic/bdivmod.c | 124 --------------------------------------------------
mpz/jacobi.c | 5 +-
6 files changed, 12 insertions(+), 162 deletions(-)
diffs (248 lines):
diff -r a61a05feb8cb -r 6e09fac92fc2 ChangeLog
--- a/ChangeLog Sun Dec 20 21:56:57 2009 +0100
+++ b/ChangeLog Sun Dec 20 23:13:41 2009 +0100
@@ -1,5 +1,7 @@
2009-12-20 Torbjorn Granlund <tege at gmplib.org>
+ * mpn/generic/bdivmod.c: File removed. All references purged.
+
* mpn/generic/mul_fft.c (mpn_mul_fft_full): Disable.
* gmp-impl.h: Define mpn_fft_mul as an alias for mpn_nussbaumer_mul.
diff -r a61a05feb8cb -r 6e09fac92fc2 configure.in
--- a/configure.in Sun Dec 20 21:56:57 2009 +0100
+++ b/configure.in Sun Dec 20 23:13:41 2009 +0100
@@ -2485,7 +2485,7 @@
random random2 pow_1 \
rootrem sqrtrem get_str set_str scan0 scan1 popcount hamdist cmp \
perfsqr perfpow \
- bdivmod gcd_1 gcd gcdext_1 gcdext gcd_lehmer gcd_subdiv_step \
+ gcd_1 gcd gcdext_1 gcdext gcd_lehmer gcd_subdiv_step \
gcdext_lehmer gcdext_subdiv_step \
tdiv_qr jacbase get_d \
matrix22_mul hgcd2 hgcd mullo_n mullo_basecase \
diff -r a61a05feb8cb -r 6e09fac92fc2 doc/gmp.texi
--- a/doc/gmp.texi Sun Dec 20 21:56:57 2009 +0100
+++ b/doc/gmp.texi Sun Dec 20 23:13:41 2009 +0100
@@ -5304,27 +5304,6 @@
@var{s1n} can be zero.
@end deftypefun
- at deftypefun mp_limb_t mpn_bdivmod (mp_limb_t *@var{rp}, mp_limb_t *@var{s1p}, mp_size_t @var{s1n}, const mp_limb_t *@var{s2p}, mp_size_t @var{s2n}, unsigned long int @var{d})
-This function puts the low
- at math{@GMPfloor{@var{d}/@nicode{mp\_bits\_per\_limb}}} limbs of @var{q} =
-@{@var{s1p}, @var{s1n}@}/@{@var{s2p}, @var{s2n}@} mod @m{2^d,2^@var{d}} at
- at var{rp}, and returns the high @var{d} mod @code{mp_bits_per_limb} bits of
- at var{q}.
-
-@{@var{s1p}, @var{s1n}@} - @var{q} * @{@var{s2p}, @var{s2n}@} mod @m{2
-\GMPraise{@var{s1n}*@code{mp\_bits\_per\_limb}},
-2^(@var{s1n}*@nicode{mp\_bits\_per\_limb})} is placed at @var{s1p}. Since the
-low @math{@GMPfloor{@var{d}/@nicode{mp\_bits\_per\_limb}}} limbs of this
-difference are zero, it is possible to overwrite the low limbs at @var{s1p}
-with this difference, provided @math{@var{rp} @le{} @var{s1p}}.
-
-This function requires that @math{@var{s1n} * @nicode{mp\_bits\_per\_limb}
- at ge{} @var{D}}, and that @{@var{s2p}, @var{s2n}@} is odd.
-
- at strong{This interface is preliminary. It might change incompatibly in future
-revisions.}
- at end deftypefun
-
@deftypefun mp_limb_t mpn_lshift (mp_limb_t *@var{rp}, const mp_limb_t *@var{sp}, mp_size_t @var{n}, unsigned int @var{count})
Shift @{@var{sp}, @var{n}@} left by @var{count} bits, and write the result to
@{@var{rp}, @var{n}@}. The bits shifted out at the left are returned in the
@@ -8352,10 +8331,9 @@
divisions saved. When @math{d} is a single limb some simplifications arise,
providing good speedups on a number of processors.
- at code{mpn_bdivmod}, @code{mpn_divexact_by3}, @code{mpn_modexact_1_odd} and the
- at code{redc} function in @code{mpz_powm} differ subtly in how they return
- at math{r}, leading to some negations in the above formula, but all are
-essentially the same.
+ at code{mpn_divexact_by3}, @code{mpn_modexact_1_odd} and the @code{mpn_redc_X}
+functions differ subtly in how they return @math{r}, leading to some negations
+in the above formula, but all are essentially the same.
@cindex Divisibility algorithm
@cindex Congruence algorithm
@@ -8364,9 +8342,8 @@
than a normal division.
The factor of @math{b^n} on @math{r} can be ignored in a GCD when @math{d} is
-odd, hence the use of @code{mpn_bdivmod} in @code{mpn_gcd}, and the use of
- at code{mpn_modexact_1_odd} by @code{mpn_gcd_1} and @code{mpz_kronecker_ui} etc
-(@pxref{Greatest Common Divisor Algorithms}).
+odd, hencethe use of @code{mpn_modexact_1_odd} by @code{mpn_gcd_1} and
+ at code{mpz_kronecker_ui} etc (@pxref{Greatest Common Divisor Algorithms}).
Montgomery's REDC method for modular multiplications uses operands of the form
of @m{xb^{-n}, x*b^-n} and @m{yb^{-n}, y*b^-n} and on calculating @m{(xb^{-n})
@@ -10298,8 +10275,9 @@
wrote the new GMP 4.3 nth root code (with Torbj@"orn).
Ken Weber (Kent State University, Universidade Federal do Rio Grande do Sul)
-contributed @code{mpz_gcd}, @code{mpz_divexact}, @code{mpn_gcd}, and
- at code{mpn_bdivmod}, partially supported by CNPq (Brazil) grant 301314194-2.
+contributed now defunct versions of @code{mpz_gcd}, @code{mpz_divexact},
+ at code{mpn_gcd}, and @code{mpn_bdivmod}, partially supported by CNPq (Brazil)
+grant 301314194-2.
Per Bothner of Cygnus Support helped to set up GMP to use Cygnus' configure.
He has also made valuable suggestions and tested numerous intermediary
diff -r a61a05feb8cb -r 6e09fac92fc2 gmp-h.in
--- a/gmp-h.in Sun Dec 20 21:56:57 2009 +0100
+++ b/gmp-h.in Sun Dec 20 23:13:41 2009 +0100
@@ -1509,9 +1509,6 @@
#define mpn_addmul_1 __MPN(addmul_1)
__GMP_DECLSPEC mp_limb_t mpn_addmul_1 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_limb_t));
-#define mpn_bdivmod __MPN(bdivmod)
-__GMP_DECLSPEC mp_limb_t mpn_bdivmod __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, unsigned long int));
-
#define mpn_cmp __MPN(cmp)
#if __GMP_INLINE_PROTOTYPES || defined (__GMP_FORCE_mpn_cmp)
__GMP_DECLSPEC int mpn_cmp __GMP_PROTO ((mp_srcptr, mp_srcptr, mp_size_t)) __GMP_NOTHROW __GMP_ATTRIBUTE_PURE;
diff -r a61a05feb8cb -r 6e09fac92fc2 mpn/generic/bdivmod.c
--- a/mpn/generic/bdivmod.c Sun Dec 20 21:56:57 2009 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,124 +0,0 @@
-/* mpn/bdivmod.c: mpn_bdivmod for computing U/V mod 2^d.
-
-Copyright 1991, 1993, 1994, 1995, 1996, 1999, 2000, 2001, 2002 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/. */
-
-/* q_high = mpn_bdivmod (qp, up, usize, vp, vsize, d).
-
- Puts the low d/GMP_LIMB_BITS limbs of Q = U / V mod 2^d at qp, and
- returns the high d%GMP_LIMB_BITS bits of Q as the result.
-
- Also, U - Q * V mod 2^(usize*GMP_LIMB_BITS) is placed at up. Since the
- low d/GMP_LIMB_BITS limbs of this difference are zero, the code allows
- the limb vectors at qp to overwrite the low limbs at up, provided qp <= up.
-
- Preconditions:
- 1. V is odd.
- 2. usize * GMP_LIMB_BITS >= d.
- 3. If Q and U overlap, qp <= up.
-
- Ken Weber (kweber at mat.ufrgs.br, kweber at mcs.kent.edu)
-
- Funding for this work has been partially provided by Conselho Nacional
- de Desenvolvimento Cienti'fico e Tecnolo'gico (CNPq) do Brazil, Grant
- 301314194-2, and was done while I was a visiting researcher in the Instituto
- de Matema'tica at Universidade Federal do Rio Grande do Sul (UFRGS).
-
- References:
- T. Jebelean, An algorithm for exact division, Journal of Symbolic
- Computation, v. 15, 1993, pp. 169-180.
-
- K. Weber, The accelerated integer GCD algorithm, ACM Transactions on
- Mathematical Software, v. 21 (March), 1995, pp. 111-122. */
-
-#include "gmp.h"
-#include "gmp-impl.h"
-#include "longlong.h"
-
-
-mp_limb_t
-mpn_bdivmod (mp_ptr qp, mp_ptr up, mp_size_t usize,
- mp_srcptr vp, mp_size_t vsize, unsigned long int d)
-{
- mp_limb_t v_inv;
-
- ASSERT (usize >= 1);
- ASSERT (vsize >= 1);
- ASSERT (usize * GMP_NUMB_BITS >= d);
- ASSERT (! MPN_OVERLAP_P (up, usize, vp, vsize));
- ASSERT (! MPN_OVERLAP_P (qp, d/GMP_NUMB_BITS, vp, vsize));
- ASSERT (MPN_SAME_OR_INCR2_P (qp, d/GMP_NUMB_BITS, up, usize));
- ASSERT_MPN (up, usize);
- ASSERT_MPN (vp, vsize);
-
- /* 1/V mod 2^GMP_NUMB_BITS. */
- binvert_limb (v_inv, vp[0]);
-
- /* Fast code for two cases previously used by the accel part of mpn_gcd.
- (Could probably remove this now it's inlined there.) */
- if (usize == 2 && vsize == 2 &&
- (d == GMP_NUMB_BITS || d == 2*GMP_NUMB_BITS))
- {
- mp_limb_t hi, lo;
- mp_limb_t q = (up[0] * v_inv) & GMP_NUMB_MASK;
- umul_ppmm (hi, lo, q, vp[0] << GMP_NAIL_BITS);
- up[0] = 0;
- up[1] -= hi + q*vp[1];
- qp[0] = q;
- if (d == 2*GMP_NUMB_BITS)
- {
- q = (up[1] * v_inv) & GMP_NUMB_MASK;
- up[1] = 0;
- qp[1] = q;
- }
- return 0;
- }
-
- /* Main loop. */
- while (d >= GMP_NUMB_BITS)
- {
- mp_limb_t q = (up[0] * v_inv) & GMP_NUMB_MASK;
- mp_limb_t b = mpn_submul_1 (up, vp, MIN (usize, vsize), q);
- if (usize > vsize)
- mpn_sub_1 (up + vsize, up + vsize, usize - vsize, b);
- d -= GMP_NUMB_BITS;
- up += 1, usize -= 1;
- *qp++ = q;
- }
-
- if (d)
- {
- mp_limb_t b;
- mp_limb_t q = (up[0] * v_inv) & (((mp_limb_t)1<<d) - 1);
- if (q <= 1)
- {
- if (q == 0)
- return 0;
- else
- b = mpn_sub_n (up, up, vp, MIN (usize, vsize));
- }
- else
- b = mpn_submul_1 (up, vp, MIN (usize, vsize), q);
-
- if (usize > vsize)
- mpn_sub_1 (up + vsize, up + vsize, usize - vsize, b);
- return q;
- }
-
- return 0;
-}
diff -r a61a05feb8cb -r 6e09fac92fc2 mpz/jacobi.c
--- a/mpz/jacobi.c Sun Dec 20 21:56:57 2009 +0100
+++ b/mpz/jacobi.c Sun Dec 20 23:13:41 2009 +0100
@@ -64,10 +64,7 @@
Enhancements:
- mpn_bdivmod could be used instead of mpn_tdiv_qr, like in mpn_gcd.
- Currently tdiv_qr is preferred since it's sub-quadratic on big sizes,
- although bdivmod might be a touch quicker on small sizes. This can be
- revised when bdivmod becomes sub-quadratic too.
+ mpn_bdiv_qr should be used instead of mpn_tdiv_qr.
Some sort of multi-step algorithm should be used. The current subtract
and shift for every bit is very inefficient. Lehmer (per current gcdext)
More information about the gmp-commit
mailing list