seq: 70x faster for non-negative whole numbers and incr==1

Handle non-negative whole numbers robustly and efficiently when
the increment is 1 and when no format-changing option is specified.
On the correctness front, for very large numbers, seq now works fine:

    $ b=1000000000000000000000000000
    $ src/seq ${b}09 ${b}11
    100000000000000000000000000009
    100000000000000000000000000010
    100000000000000000000000000011

while the old one would infloop, printing garbage:

    $ seq ${b}09 ${b}11 | head -2
    99999999999999999997315645440
    99999999999999999997315645440

The new code is much more efficient, too:
Old vs new: 55.81s vs 0.82s

  $ env time --f=%e seq $((10**8)) > /dev/null
  55.81
  $ env time --f=%e src/seq $((10**8)) > /dev/null
  0.82

* seq.c (incr): New function, inspired by the one in cat.c.
(cmp, seq_fast): New functions, inspired by code in nt-factor
by Torbjörn Granlund and Niels Möller.
(trim_leading_zeros): New function, without which cmp would malfunction.
(all_digits_p): New function.
(main): Hoist the format_str-vs-equal_width check to precede first
treatment of operands, and insert code to call seq_fast when possible.
* NEWS (Bug fixes): Mention the correctness fix.
(Improvements): Mention the speed-up.
* tests/misc/seq.pl: Exercise the new code.

Improved by: Bernhard Voelker.
http://thread.gmane.org/gmane.comp.gnu.coreutils.general/3340

1 files changed, 10 insertions, 0 deletions

diff --git a/NEWS b/NEWS
index f63df92a4..2e69391ce 100644
--- a/NEWS
+++ b/NEWS
@@ -29,12 +29,22 @@ GNU coreutils NEWS                                    -*- outline -*-
   "Too many levels of symbolic links" diagnostic.
   [bug introduced in coreutils-8.6]
 
+  seq now handles arbitrarily long non-negative whole numbers when the
+  increment is 1 and when no format-changing option is specified.
+  Before, this would infloop:
+    b=100000000000000000000; seq $b $b
+  [the bug dates back to the initial implementation]
+
 ** Changes in behavior
 
   nproc now diagnoses with an error, non option command line parameters.
 
 ** Improvements
 
+  seq is now up to 70 times faster than it was in coreutils-8.19 and prior,
+  but only with non-negative whole numbers, an increment of 1, and no
+  format-changing options.
+
   stat and tail work better with ZFS and VZFS.  stat -f --format=%T now
   reports the file system type, and tail -f now uses inotify for files
   on those file systems, rather than the default (for unknown file system