[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH] Support the factoring of arbitrarily-long numbers with GNU M
From: |
Jim Meyering |
Subject: |
Re: [PATCH] Support the factoring of arbitrarily-long numbers with GNU MP. |
Date: |
Thu, 31 Jul 2008 11:53:25 +0200 |
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);