Re: [PATCH 1/2] Support arbitrarily-long numbers with GNU MP.

[Jim Meyering]

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