Re: factor

[Jim Meyering]

ThMO <address@hidden> wrote:
> attached you'll find my final patch for src/factor.c combining the two
> different functions into one, as the underlying computation is the same,
> except for the initial negation.
>
> Additionally the error message regarding to factorize 0 will go to stderr,
> but I do not return an error status in this case.
>
> This combined function factorizes the two given examples within the
> info-file somewhat faster than before (taking 96.4% of the previous time).
>
> As far as the execution speed is concerned, it's IMHO not worth the trouble
> for seeking a faster algorithm, since e.g. pari (v1.39) factorizes the above
> two examples within microseconds.
> FYI, even pari outputs -1 as the 1st factor for negative values.

I'd be more interested in a patch to make GNU factor accept negative
numbers if it weren't so invasive.  How about just examining the string
for a leading `-' (possibly after white space), remembering that, and
skipping over it.  Then the existing unsigned code will work just fine.
Patch below.

BTW, thanks for the improved definition of MAX_N_FACTORS.
I've already checked in that part.

        * src/factor.c (MAX_N_FACTORS): Define in terms of sizeof (uintmax_t)
        rather than hard-coding to 128.  From Thomas M.Ott.

If you're really interested in improving this program, extending it to
use GMP[*] (i.e., -lgmp) is the way to go.  Then, it will be able to
accept arbitrarily long strings of digits, and of course it'll be
much more efficient for large numbers.

The idea is that there'd be a conditionally-compiled (only if -lgmp
and headers are available) function to do the MP factorization,
and if that isn't available, factor would fall through to something
like the current implementation.

[*] The GNU MP Bignum Library <http://www.swox.com/gmp/>

Here's a tentative patch.
I haven't written any tests for it yet.
The `Reject `factor 0'' part keeps it simple.
Otherwise, I'd have to worry about diagnosing  `factor -- -000000000'.

2005-10-03  Jim Meyering  <address@hidden>

        * src/factor.c: Reject `factor 0'.
        Accept negative numbers; for them, print a leading factor of -1
        followed by the factors of the number without a leading `-'.

Index: factor.c
===================================================================
RCS file: /fetish/cu/src/factor.c,v
retrieving revision 1.76
diff -u -p -r1.76 factor.c
--- factor.c    1 Oct 2005 08:01:25 -0000       1.76
+++ factor.c    3 Oct 2005 12:04:57 -0000
@@ -42,9 +42,8 @@
 /* Token delimiters when reading from a file.  */
 #define DELIM "\n\t "
 
-/* FIXME: if this program is ever modified to factor integers larger
-   than 2^128, this constant (and the algorithm :-) will have to change.  */
-#define MAX_N_FACTORS 128
+/* The maximum number of factors, including -1, for negative numbers.  */
+#define MAX_N_FACTORS (sizeof (uintmax_t) * CHAR_BIT)
 
 /* The trial divisor increment wheel.  Use it to skip over divisors that
    are composites of 2, 3, 5, 7, or 11.  The part from WHEEL_START up to
@@ -150,17 +149,32 @@ print_factors (const char *s)
   size_t i;
   char buf[INT_BUFSIZE_BOUND (uintmax_t)];
   strtol_error err;
+  bool is_negative;
+  char const *p = s;
+  char const *s_diag;
+
+  while (ISSPACE (*p))
+    ++p;
+
+  /* Save a copy solely for diagnostics.  */
+  s_diag = p;
+  is_negative = (*p == '-');
+  p += is_negative;
 
-  if ((err = xstrtoumax (s, NULL, 10, &n, "")) != LONGINT_OK)
+  if ((err = xstrtoumax (p, NULL, 10, &n, "")) != LONGINT_OK
+      || n == 0)
     {
       if (err == LONGINT_OVERFLOW)
-       error (0, 0, _("%s is too large"), quote (s));
+       error (0, 0, _("%s is too large"), quote (s_diag));
       else
-       error (0, 0, _("%s is not a valid positive integer"), quote (s));
+       error (0, 0, _("%s is not a valid positive integer"), quote (s_diag));
       return false;
     }
   n_factors = factor (n, MAX_N_FACTORS, factors);
-  printf ("%s:", umaxtostr (n, buf));
+  printf ("%s%s:%s",
+         (is_negative ? "-" : ""),
+         umaxtostr (n, buf),
+         (is_negative ? " -1" : ""));
   for (i = 0; i < n_factors; i++)
     printf (" %s", umaxtostr (factors[i], buf));
   putchar ('\n');