[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH 1/2] Support arbitrarily-long numbers with GNU MP.
From: |
Jim Meyering |
Subject: |
Re: [PATCH 1/2] Support arbitrarily-long numbers with GNU MP. |
Date: |
Wed, 30 Jul 2008 16:02:57 +0200 |
James Youngman <address@hidden> wrote:
> Support arbitrarily-long numbers with GNU MP.
> * m4/gmp.m4: New file; adds cu_GMP, which detects GNU MP.
> * configure.ac: Use cu_GMP.
> * src/Makefile.am: Link factor against libgmp if available.
> * src/factor.c: Use GNU MP if it is available.
> (emit_factor, emit_ul_factor, factor_using_division,
> factor_using_pollard_rho, extract_factors_multi,
> sort_and_print_factors, free_factors): new functions
> for the arbitrary-precision implementation, taken from an example
> in GNU MP.
> (factor_wheel): Renamed; was called factor.
> (print_factors_single): Renamed; was called print_factors.
> (print_factors): New function, chooses between the single- and
> arbitrary-precision algorithms according to availability of GNU MP
> and the length of the number to be factored.
> (usage, main): New options --use-mp and --nouse-mp.
What do you think of --mp and --no-mp instead?
"--nouse-mp" makes me think "mouse".
> +static bool verbose = false;
...
> + if (verbose)
> + {
> + printf ("[composite factor--restarting pollard-rho] ");
> + fflush (stdout);
...
> + verbose = 1;
Do you find --verbose useful? I haven't (yet?).
If we end up keeping it, it should print to stderr, not stdout.
Here are a bunch of changes that I expect to merge into yours
before pushing. In fact, I would prefer to combine all of these
(including all 4 of yours) changes into a single change set.
>From b8e65197c3e99b0b2699a2df853557c8276b1d6e Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Wed, 30 Jul 2008 10:28:59 +0200
Subject: [PATCH] * src/factor.c (extract_factors_multi): Don't leak "t".
---
src/factor.c | 1 +
1 files changed, 1 insertions(+), 0 deletions(-)
diff --git a/src/factor.c b/src/factor.c
index 9000424..8b4cf90 100644
--- a/src/factor.c
+++ b/src/factor.c
@@ -315,6 +315,7 @@ extract_factors_multi (const char *s)
factor_using_pollard_rho (t, 1);
}
}
+ mpz_clear (t);
return true;
}
#endif
--
1.6.0.rc1.2.gc4577
>From 61eeb0c4ab38c34947ffc28c6615e36bde2ed709 Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Wed, 30 Jul 2008 10:34:23 +0200
Subject: [PATCH] * m4/gmp.m4: use AC_SEARCH_LIBS, not AC_CHECK_LIB.
---
m4/gmp.m4 | 26 +++++++++++++++++++++-----
1 files changed, 21 insertions(+), 5 deletions(-)
diff --git a/m4/gmp.m4 b/m4/gmp.m4
index c0d1091..e33ca93 100644
--- a/m4/gmp.m4
+++ b/m4/gmp.m4
@@ -12,9 +12,25 @@ dnl Check for libgmp. We avoid use of AC_CHECK_LIBS because
we don't want to
dnl add this to $LIBS for all targets.
AC_DEFUN([cu_GMP],
[
- AC_CHECK_LIB(gmp, __gmpz_init,
- [
- AC_DEFINE(HAVE_GMP,1,[Define if you have GNU libgmp (or
replacement)])
- AC_SUBST(LIB_GMP,[-lgmp])
- ],)
+ LIB_GMP=
+ AC_SUBST([LIB_GMP])
+
+ AC_ARG_WITH([gmp],
+ AS_HELP_STRING([--without-gmp],
+ [do not use the GNU MP library for arbitrary precision
+ calculation (default: use it if available)]),
+ [cu_use_gmp=$withval],
+ [cu_use_gmp=auto])
+
+ if test $cu_use_gmp != no; then
+ cu_saved_libs=$LIBS
+ AC_SEARCH_LIBS([__gmpz_init], [gmp],
+ [test "$ac_cv_search___gmpz_init" = "none required" ||
+ {
+ LIB_GMP=$ac_cv_search___gmpz_init
+ AC_DEFINE([HAVE_GMP], 1,
+ [Define if you have GNU libgmp (or replacement)])
+ }])
+ LIBS=$cu_saved_libs
+ fi
])
--
1.6.0.rc1.2.gc4577
>From 607b91b098926ab414c53c3c23541cfb6ac062ed Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Wed, 30 Jul 2008 11:49:10 +0200
Subject: [PATCH] misc nits
spaces around operators; sizeof *VAR, not sizeof TYPE
remove unused label, S3
syntax: change "const char *" to "char const *"
(mpcompare): avoid casts
fix typo in a comment
(print_factors): Change code to agree with comment: factor numbers
of 6 digits (not 5) and longer using MP.
---
src/factor.c | 48 ++++++++++++++++++++----------------------------
1 files changed, 20 insertions(+), 28 deletions(-)
diff --git a/src/factor.c b/src/factor.c
index 8b4cf90..38d91a8 100644
--- a/src/factor.c
+++ b/src/factor.c
@@ -57,12 +57,10 @@ typedef enum
} ALGORITHM_CHOICE;
static ALGORITHM_CHOICE algorithm = ALGO_AUTOSELECT;
-
-
#if HAVE_GMP
static mpz_t *factors = NULL;
-static size_t nfactors_found = 0u;
-static size_t nfactors_allocated = 0u;
+static size_t nfactors_found = 0;
+static size_t nfactors_allocated = 0;
static unsigned add[] = {4, 2, 4, 2, 4, 6, 2, 6};
@@ -70,7 +68,7 @@ static void
emit_factor (mpz_t n)
{
if (nfactors_found == nfactors_allocated)
- factors = x2nrealloc (factors, &nfactors_allocated, sizeof(*factors));
+ factors = x2nrealloc (factors, &nfactors_allocated, sizeof *factors);
mpz_init (factors[nfactors_found]);
mpz_set (factors[nfactors_found], n);
++nfactors_found;
@@ -85,7 +83,6 @@ emit_ul_factor (unsigned long i)
emit_factor (t);
}
-
static void
factor_using_division (mpz_t t, unsigned int limit)
{
@@ -201,7 +198,7 @@ S2:
goto S4;
mpz_set (y, x);
}
-S3:
+
k--;
if (k > 0)
goto S2;
@@ -273,7 +270,7 @@ S4:
/* Arbitrary-precision factoring */
static bool
-extract_factors_multi (const char *s)
+extract_factors_multi (char const *s)
{
unsigned int division_limit;
mpz_t t;
@@ -330,7 +327,7 @@ extract_factors_multi (const char *s)
http://www.utm.edu/research/primes/glossary/WheelFactorization.html */
#include "wheel-size.h" /* For the definition of WHEEL_SIZE. */
-static const unsigned char wheel_tab[] =
+static unsigned char const wheel_tab[] =
{
#include "wheel.h"
};
@@ -386,7 +383,7 @@ factor_wheel (uintmax_t n0, size_t max_n_factors, uintmax_t
*factors)
/* Single-precision factoring */
static bool
-print_factors_single (const char *s)
+print_factors_single (char const *s)
{
uintmax_t factors[MAX_N_FACTORS];
uintmax_t n;
@@ -413,9 +410,11 @@ print_factors_single (const char *s)
#if HAVE_GMP
static int
-mpcompare (const void* a, const void *b)
+mpcompare (void const *av, void const *bv)
{
- return mpz_cmp(**(const mpz_t**)a, **(const mpz_t**)b);
+ mpz_t *const *a = av;
+ mpz_t *const *b = bv;
+ return mpz_cmp (**a, **b);
}
static void
@@ -424,14 +423,14 @@ sort_and_print_factors (void)
mpz_t** faclist;
size_t i;
- faclist = xcalloc (nfactors_found, sizeof(mpz_t*));
- for (i=0u; i<nfactors_found; ++i)
+ faclist = xcalloc (nfactors_found, sizeof *faclist);
+ for (i = 0; i < nfactors_found; ++i)
{
faclist[i] = &factors[i];
}
- qsort (faclist, nfactors_found, sizeof(*faclist), mpcompare);
+ qsort (faclist, nfactors_found, sizeof *faclist, mpcompare);
- for (i=0u; i<nfactors_found; ++i)
+ for (i = 0; i < nfactors_found; ++i)
{
fputc (' ', stdout);
mpz_out_str (stdout, 10, *faclist[i]);
@@ -445,13 +444,12 @@ free_factors (void)
{
size_t i;
- for (i=0u; i<nfactors_found; ++i)
+ for (i = 0; i < nfactors_found; ++i)
{
mpz_clear (factors[i]);
}
/* Don't actually free factors[] because in the case where we are
- * reasding numbers from stdin, we may be about to use it again.
- */
+ reading numbers from stdin, we may be about to use it again. */
nfactors_found = 0;
}
@@ -464,12 +462,12 @@ free_factors (void)
if the number presented has small factors, we just switch over at 6 digits.
*/
static bool
-print_factors (const char *s)
+print_factors (char const *s)
{
if (ALGO_AUTOSELECT == algorithm)
{
const size_t digits = strlen(s); /* upper limit on number of digits */
- algorithm = digits < 5 ? ALGO_SINGLE : ALGO_GMP;
+ algorithm = digits < 6 ? ALGO_SINGLE : ALGO_GMP;
}
if (ALGO_GMP == algorithm)
{
@@ -495,7 +493,7 @@ print_factors (const char *s)
}
#else
static bool
-print_factors (const char *s) /* Single-precision only. */
+print_factors (char const *s) /* Single-precision only. */
{
if (ALGO_GMP == algorithm)
{
@@ -506,10 +504,6 @@ print_factors (const char *s) /* Single-precision
only. */
}
#endif
-
-
-
-
enum
{
VERBOSE_OPTION = CHAR_MAX + 1,
@@ -630,8 +624,6 @@ main (int argc, char **argv)
}
#if HAVE_GMP
free (factors);
- nfactors_allocated = 0;
- factors = NULL;
#endif
exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
}
--
1.6.0.rc1.2.gc4577
>From 7d23ebde6629ee35bd0958dd00df2a8803bc9619 Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Wed, 30 Jul 2008 10:57:26 +0200
Subject: [PATCH] don't use parse_long_options
* src/factor.c: Don't #include "long-options.h".
(main): Don't use parse_long_options.
Handle --help and --version options via
case_GETOPT_HELP_CHAR and case_GETOPT_VERSION_CHAR macros.
---
src/factor.c | 7 ++++---
1 files changed, 4 insertions(+), 3 deletions(-)
diff --git a/src/factor.c b/src/factor.c
index 38d91a8..254ff3d 100644
--- a/src/factor.c
+++ b/src/factor.c
@@ -34,7 +34,6 @@
#include "system.h"
#include "error.h"
-#include "long-options.h"
#include "quote.h"
#include "readtokens.h"
#include "xstrtol.h"
@@ -589,8 +588,6 @@ main (int argc, char **argv)
atexit (close_stdout);
- parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE_NAME, VERSION,
- usage, AUTHORS, (char const *) NULL);
while ((c = getopt_long (argc, argv, "", long_options, NULL)) != -1)
{
switch (c)
@@ -607,6 +604,10 @@ main (int argc, char **argv)
algorithm = ALGO_SINGLE;
break;
+ case_GETOPT_HELP_CHAR;
+
+ case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
+
default:
usage (EXIT_FAILURE);
}
--
1.6.0.rc1.2.gc4577
>From e6a96ee3f038d7f8de83e4eda1a4204a10f525a7 Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Wed, 30 Jul 2008 11:27:30 +0200
Subject: [PATCH] rename global s/factors/factor/ not to shadow function
parameters
---
src/factor.c | 16 ++++++++--------
1 files changed, 8 insertions(+), 8 deletions(-)
diff --git a/src/factor.c b/src/factor.c
index 254ff3d..2bd16ea 100644
--- a/src/factor.c
+++ b/src/factor.c
@@ -57,7 +57,7 @@ typedef enum
static ALGORITHM_CHOICE algorithm = ALGO_AUTOSELECT;
#if HAVE_GMP
-static mpz_t *factors = NULL;
+static mpz_t *factor = NULL;
static size_t nfactors_found = 0;
static size_t nfactors_allocated = 0;
@@ -67,9 +67,9 @@ static void
emit_factor (mpz_t n)
{
if (nfactors_found == nfactors_allocated)
- factors = x2nrealloc (factors, &nfactors_allocated, sizeof *factors);
- mpz_init (factors[nfactors_found]);
- mpz_set (factors[nfactors_found], n);
+ factor = x2nrealloc (factor, &nfactors_allocated, sizeof *factor);
+ mpz_init (factor[nfactors_found]);
+ mpz_set (factor[nfactors_found], n);
++nfactors_found;
}
@@ -425,7 +425,7 @@ sort_and_print_factors (void)
faclist = xcalloc (nfactors_found, sizeof *faclist);
for (i = 0; i < nfactors_found; ++i)
{
- faclist[i] = &factors[i];
+ faclist[i] = &factor[i];
}
qsort (faclist, nfactors_found, sizeof *faclist, mpcompare);
@@ -445,9 +445,9 @@ free_factors (void)
for (i = 0; i < nfactors_found; ++i)
{
- mpz_clear (factors[i]);
+ mpz_clear (factor[i]);
}
- /* Don't actually free factors[] because in the case where we are
+ /* Don't actually free factor[] because in the case where we are
reading numbers from stdin, we may be about to use it again. */
nfactors_found = 0;
}
@@ -624,7 +624,7 @@ main (int argc, char **argv)
ok = false;
}
#if HAVE_GMP
- free (factors);
+ free (factor);
#endif
exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
}
--
1.6.0.rc1.2.gc4577