Re: [PATCH] Support the factoring of arbitrarily-long numbers with GNU MP.

[Jim Meyering]

James Youngman <address@hidden> wrote:
> 2008-07-27  James Youngman  <address@hidden>
>
>       Support arbitrarily-long numbers with GNU MP.

Thanks again!

I've added a note in NEWS, and prefer prefer the spelling
--no-bignum over --nobignum.
I've changed the "0u" constants to "0", since I didn't
see a good reason to keep the "u".

Plus, I added the following change to avoid one of those
probably-never-happen-and-don't-care-even-if-it-does problems ;-)
to avoid overflow of the unsigned int with a size_t value
larger than UINT_MAX.

diff --git a/src/factor.c b/src/factor.c
index 80daba9..c7cd29e 100644
--- a/src/factor.c
+++ b/src/factor.c
@@ -272,6 +272,7 @@ static bool
 extract_factors_multi (char const *s)
 {
   unsigned int division_limit;
+  size_t n_bits;
   mpz_t t;

   mpz_init (t);
@@ -289,12 +290,10 @@ extract_factors_multi (char const *s)
       return true;             /* 0; no factors */
     }

-  /* Set the trial division limit according the size of t.  */
-  division_limit = mpz_sizeinbase (t, 2);
-  if (division_limit > 1000)
-    division_limit = 1000 * 1000;
-  else
-    division_limit = division_limit * division_limit;
+  /* Set the trial division limit according to the size of t.  */
+  n_bits = mpz_sizeinbase (t, 2);
+  division_limit = MIN (n_bits, 1000);
+  division_limit *= division_limit;

   factor_using_division (t, division_limit);


Plus a few more syntax and scoping nits.
Oh, and in --help output, there must be two or more spaces
after each long option name -- otherwise, help2man misbehaves.
Here's the rest of the incremental.

Once you've signed off, I'll push it.

diff --git a/NEWS b/NEWS
index 5796dfa..b286be2 100644
--- a/NEWS
+++ b/NEWS
@@ -19,6 +19,9 @@ GNU coreutils NEWS                                    -*- 
outline -*-
   With this new option, after a short read, dd repeatedly calls read,
   until it fills the incomplete block, reaches EOF, or encounters an error.

+  factor accepts arbitrarily large numbers and factors them using
+  Pollard's rho algorithm.
+
   md5sum now accepts the new option, --quiet, to suppress the printing of
   'OK' messages.  sha1sum, sha224sum, sha384sum, and sha512sum accept it, too.

diff --git a/doc/coreutils.texi b/doc/coreutils.texi
index 54798fd..c789a6c 100644
--- a/doc/coreutils.texi
+++ b/doc/coreutils.texi
@@ -14366,12 +14366,12 @@ The @command{factor} command supports only a small 
number of options:
 Print a short help on standard output, then exit without further
 processing.

address@hidden --use-mp
address@hidden --bignum
 Forces the use of the GNU MP library.   By default, @command{factor}
 selects between using GNU MP and using native operations on the basis
 of the length of the number to be factored.

address@hidden --nouse-mp
address@hidden --no-bignum
 Forces the use of native operations instead of GNU MP.  This causes
 @command{factor} to fail for larger inputs.

diff --git a/src/factor.c b/src/factor.c
index 5960d21..80daba9 100644
--- a/src/factor.c
+++ b/src/factor.c
@@ -53,19 +53,16 @@ typedef enum
   {
     ALGO_AUTOSELECT,           /* default */
     ALGO_GMP,                  /* --bignum */
-    ALGO_SINGLE                        /* --nobignum */
+    ALGO_SINGLE                        /* --no-bignum */
   } ALGORITHM_CHOICE;
 static ALGORITHM_CHOICE algorithm = ALGO_AUTOSELECT;


-
 #if HAVE_GMP
 static mpz_t *factor = NULL;
 static size_t nfactors_found = 0;
 static size_t nfactors_allocated = 0;

-static unsigned add[] = {4, 2, 4, 2, 4, 6, 2, 6};
-
 static void
 debug (char const *fmt, ...)
 {
@@ -88,7 +85,7 @@ emit_factor (mpz_t n)
 }

 static void
-emit_ul_factor (unsigned long i)
+emit_ul_factor (unsigned long int i)
 {
   mpz_t t;
   mpz_init (t);
@@ -102,7 +99,8 @@ factor_using_division (mpz_t t, unsigned int limit)
   mpz_t q, r;
   unsigned long int f;
   int ai;
-  unsigned *addv = add;
+  static unsigned int const add[] = {4, 2, 4, 2, 4, 6, 2, 6};
+  unsigned int const *addv = add;
   unsigned int failures;

   debug ("[trial division (%u)] ", limit);
@@ -410,7 +408,7 @@ print_factors_single (char const *s)

 #if HAVE_GMP
 static int
-mpcompare (const void* av, const void *bv)
+mpcompare (const void *av, const void *bv)
 {
   mpz_t *const *a = av;
   mpz_t *const *b = bv;
@@ -420,17 +418,17 @@ mpcompare (const void* av, const void *bv)
 static void
 sort_and_print_factors (void)
 {
-  mpz_t** faclist;
+  mpz_t **faclist;
   size_t i;

   faclist = xcalloc (nfactors_found, sizeof *faclist);
-  for (i=0u; i < nfactors_found; ++i)
+  for (i = 0; i < nfactors_found; ++i)
     {
       faclist[i] = &factor[i];
     }
   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]);
@@ -444,12 +442,12 @@ free_factors (void)
 {
   size_t i;

-  for (i=0u; i<nfactors_found; ++i)
+  for (i = 0; i < nfactors_found; ++i)
     {
       mpz_clear (factor[i]);
     }
   /* Don't actually free factor[] because in the case where we are
-     reading 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;
 }

@@ -466,7 +464,7 @@ print_factors (char const *s)
 {
   if (ALGO_AUTOSELECT == algorithm)
     {
-      const size_t digits = strlen(s); /* upper limit on number of digits */
+      const size_t digits = strlen (s); /* upper limit on number of digits */
       algorithm = digits < 6 ? ALGO_SINGLE : ALGO_GMP;
     }
   if (ALGO_GMP == algorithm)
@@ -513,7 +511,7 @@ static struct option const long_options[] =
 {
   {"verbose", no_argument, NULL, VERBOSE_OPTION},
   {"bignum", no_argument, NULL, USE_BIGNUM},
-  {"nobignum", no_argument, NULL, NO_USE_BIGNUM},
+  {"no-bignum", no_argument, NULL, NO_USE_BIGNUM},
   {GETOPT_HELP_OPTION_DECL},
   {GETOPT_VERSION_OPTION_DECL},
   {NULL, 0, NULL, 0}
@@ -537,8 +535,8 @@ Print the prime factors of each NUMBER.\n\
 \n\
 "), stdout);
       fputs (_("\
-      --bignum   force the use of arbitrary-precision arithmetic\n\
-      --nobignum force the use of single-precision arithmetic\n"),
+      --bignum     always use arbitrary-precision arithmetic\n\
+      --no-bignum  always use single-precision arithmetic\n"),
               stdout);
       fputs (HELP_OPTION_DESCRIPTION, stdout);
       fputs (VERSION_OPTION_DESCRIPTION, stdout);
@@ -605,7 +603,7 @@ main (int argc, char **argv)

        case_GETOPT_HELP_CHAR;

-        case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
+       case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);

        default:
          usage (EXIT_FAILURE);