[Gmp-commit] /var/hg/gmp: 3 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Mon Mar 11 19:42:19 CET 2013
details: /var/hg/gmp/rev/17d8eb27d0f4
changeset: 15558:17d8eb27d0f4
user: Torbjorn Granlund <tege at gmplib.org>
date: Mon Mar 11 19:41:00 2013 +0100
description:
(mod): Adhere to mpn_mu_div_qr's overlap requirements.
details: /var/hg/gmp/rev/7809c52b0b7d
changeset: 15559:7809c52b0b7d
user: Torbjorn Granlund <tege at gmplib.org>
date: Mon Mar 11 19:42:01 2013 +0100
description:
Test larger arguments. General cleanup.
details: /var/hg/gmp/rev/3e74ad5ad65e
changeset: 15560:3e74ad5ad65e
user: Torbjorn Granlund <tege at gmplib.org>
date: Mon Mar 11 19:42:15 2013 +0100
description:
ChangeLog
diffstat:
ChangeLog | 6 ++++
mpz/powm_ui.c | 45 +++++++++++++++++++-----------
tests/mpz/t-powm_ui.c | 73 +++++++++++++-------------------------------------
3 files changed, 54 insertions(+), 70 deletions(-)
diffs (229 lines):
diff -r e0f795b7e0e8 -r 3e74ad5ad65e ChangeLog
--- a/ChangeLog Sun Mar 10 20:14:53 2013 +0100
+++ b/ChangeLog Mon Mar 11 19:42:15 2013 +0100
@@ -1,3 +1,9 @@
+2013-03-11 Torbjorn Granlund <tege at gmplib.org>
+
+ * tests/mpz/t-powm_ui.c: Test larger arguments. General cleanup.
+
+ * mpz/powm_ui.c (mod): Adhere to mpn_mu_div_qr's overlap requirements.
+
2013-03-10 Niels Möller <nisse at lysator.liu.se>
* mpn/generic/sbpi1_div_sec.c: Update calls of mpn_addcnd_n and
diff -r e0f795b7e0e8 -r 3e74ad5ad65e mpz/powm_ui.c
--- a/mpz/powm_ui.c Sun Mar 10 20:14:53 2013 +0100
+++ b/mpz/powm_ui.c Mon Mar 11 19:42:15 2013 +0100
@@ -1,24 +1,24 @@
-/* mpz_powm_ui(res,base,exp,mod) -- Set R to (U^E) mod M.
+/* mpz_powm_ui(res,base,exp,mod) -- Set R to (B^E) mod M.
- Contributed to the GNU project by Torbjorn Granlund.
+ Contributed to the GNU project by Torbjörn Granlund.
-Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2002, 2005, 2008,
-2009, 2011, 2012 Free Software Foundation, Inc.
+Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2002, 2005, 2008, 2009,
+2011, 2012, 2013 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 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.
+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/. */
+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 "gmp.h"
@@ -55,12 +55,18 @@
qp = tp;
if (dn == 1)
- np[0] = mpn_divrem_1 (qp, (mp_size_t) 0, np, nn, dp[0]);
+ {
+ np[0] = mpn_divrem_1 (qp, (mp_size_t) 0, np, nn, dp[0]);
+ }
else if (dn == 2)
- mpn_div_qr_2n_pi1 (qp, np, np, nn, dp[1], dp[0], dinv->inv32);
+ {
+ mpn_div_qr_2n_pi1 (qp, np, np, nn, dp[1], dp[0], dinv->inv32);
+ }
else if (BELOW_THRESHOLD (dn, DC_DIV_QR_THRESHOLD) ||
BELOW_THRESHOLD (nn - dn, DC_DIV_QR_THRESHOLD))
- mpn_sbpi1_div_qr (qp, np, nn, dp, dn, dinv->inv32);
+ {
+ mpn_sbpi1_div_qr (qp, np, nn, dp, dn, dinv->inv32);
+ }
else if (BELOW_THRESHOLD (dn, MUPI_DIV_QR_THRESHOLD) || /* fast condition */
BELOW_THRESHOLD (nn, 2 * MU_DIV_QR_THRESHOLD) || /* fast condition */
(double) (2 * (MU_DIV_QR_THRESHOLD - MUPI_DIV_QR_THRESHOLD)) * dn /* slow... */
@@ -70,9 +76,14 @@
}
else
{
+ /* We need to allocate separate remainder area, since mpn_mu_div_qr does
+ not handle overlap between the numerator and remainder areas.
+ FIXME: Make it handle such overlap. */
+ mp_ptr rp = TMP_ALLOC_LIMBS (dn);
mp_size_t itch = mpn_mu_div_qr_itch (nn, dn, 0);
mp_ptr scratch = TMP_ALLOC_LIMBS (itch);
- mpn_mu_div_qr (qp, np, np, nn, dp, dn, scratch);
+ mpn_mu_div_qr (qp, rp, np, nn, dp, dn, scratch);
+ MPN_COPY (np, rp, dn);
}
TMP_FREE;
diff -r e0f795b7e0e8 -r 3e74ad5ad65e tests/mpz/t-powm_ui.c
--- a/tests/mpz/t-powm_ui.c Sun Mar 10 20:14:53 2013 +0100
+++ b/tests/mpz/t-powm_ui.c Mon Mar 11 19:42:15 2013 +0100
@@ -1,6 +1,6 @@
/* Test mpz_powm_ui, mpz_mul, mpz_mod.
-Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2002 Free Software
+Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2002, 2013 Free Software
Foundation, Inc.
This file is part of the GNU MP Library test suite.
@@ -25,9 +25,6 @@
#include "gmp-impl.h"
#include "tests.h"
-void dump_abort (mpz_t, mpz_t);
-void debug_mp (mpz_t, int);
-
int
main (int argc, char **argv)
{
@@ -36,7 +33,7 @@
mp_size_t base_size, exp_size, mod_size;
unsigned long int exp2;
int i;
- int reps = 1000;
+ int reps = 100;
gmp_randstate_ptr rands;
mpz_t bs;
unsigned long bsi, size_range;
@@ -44,22 +41,14 @@
tests_start ();
rands = RANDS;
- mpz_init (bs);
+ TESTS_REPS (reps, argv, argc);
- if (argc == 2)
- reps = atoi (argv[1]);
-
- mpz_init (base);
- mpz_init (exp);
- mpz_init (mod);
- mpz_init (r1);
- mpz_init (r2);
- mpz_init (base2);
+ mpz_inits (bs, base, exp, mod, r1, r2, base2, NULL);
for (i = 0; i < reps; i++)
{
mpz_urandomb (bs, rands, 32);
- size_range = mpz_get_ui (bs) % 13 + 2;
+ size_range = mpz_get_ui (bs) % 18 + 2;
do /* Loop until mathematically well-defined. */
{
@@ -91,16 +80,13 @@
#if 0
putc ('\n', stderr);
- debug_mp (base, -16);
- debug_mp (mod, -16);
+ gmp_fprintf (stderr, "B = 0x%Zx\n", base);
+ gmp_fprintf (stderr, "M = 0x%Zx\n", mod);
#endif
- mpz_powm_ui (r1, base, exp2, mod);
- MPZ_CHECK_FORMAT (r1);
-
+ exp2 = mpz_getlimbn (exp, (mp_size_t) 0);
mpz_set_ui (r2, 1);
mpz_set (base2, base);
-
mpz_mod (r2, r2, mod); /* needed when exp==0 and mod==1 */
while (exp2 != 0)
{
@@ -114,48 +100,29 @@
exp2 = exp2 / 2;
}
+ exp2 = mpz_getlimbn (exp, (mp_size_t) 0);
+ mpz_powm_ui (r1, base, exp2, mod);
+ MPZ_CHECK_FORMAT (r1);
+
#if 0
- debug_mp (r1, -16);
- debug_mp (r2, -16);
+ gmp_fprintf (stderr, "R = 0x%Zx\n", r1);
+ gmp_fprintf (stderr, "REF = 0x%Zx\n", r2);
#endif
if (mpz_cmp (r1, r2) != 0)
{
fprintf (stderr, "\ntest %d: Incorrect results for operands:\n", i);
- debug_mp (base, -16);
- debug_mp (exp, -16);
- debug_mp (mod, -16);
- fprintf (stderr, "mpz_powm_ui result:\n");
- debug_mp (r1, -16);
- fprintf (stderr, "reference result:\n");
- debug_mp (r2, -16);
+ gmp_fprintf (stderr, "B = 0x%Zx\n", base);
+ gmp_fprintf (stderr, "E = 0x%Zx\n", exp);
+ gmp_fprintf (stderr, "M = 0x%Zx\n", mod);
+ gmp_fprintf (stderr, "R = 0x%Zx\n", r1);
+ gmp_fprintf (stderr, "REF = 0x%Zx\n", r2);
abort ();
}
}
- mpz_clear (bs);
- mpz_clear (base);
- mpz_clear (exp);
- mpz_clear (mod);
- mpz_clear (r1);
- mpz_clear (r2);
- mpz_clear (base2);
+ mpz_clears (bs, base, exp, mod, r1, r2, base2, NULL);
tests_end ();
exit (0);
}
-
-void
-dump_abort (mpz_t dividend, mpz_t divisor)
-{
- fprintf (stderr, "ERROR\n");
- fprintf (stderr, "dividend = "); debug_mp (dividend, -16);
- fprintf (stderr, "divisor = "); debug_mp (divisor, -16);
- abort();
-}
-
-void
-debug_mp (mpz_t x, int base)
-{
- mpz_out_str (stderr, base, x); fputc ('\n', stderr);
-}
More information about the gmp-commit
mailing list