%% /u/sy/beebe/src/ndiff/ndiff-2.00/README, Sun Dec 10 08:47:09 2000
%% Edit by Nelson H. F. Beebe <beebe@math.utah.edu>

%% Author:
%% 	Nelson H. F. Beebe
%% 	Center for Scientific Computing
%% 	University of Utah
%% 	Department of Mathematics, 322 INSCC
%% 	155 S 1400 E RM 233
%% 	Salt Lake City, UT 84112-0090
%% 	USA
%% 	Email: beebe@math.utah.edu, beebe@acm.org,
%%	       beebe@computer.org, beebe@ieee.org (Internet)
%% 	WWW URL: http://www.math.utah.edu/~beebe
%% 	Telephone: +1 801 581 5254
%% 	FAX: +1 801 585 1640, +1 801 581 4148

This directory contains a utility, ndiff, for comparing putatively
similar files, ignoring small numeric differences.

See "man ndiff" for program documentation.

That documentation is also provided with the distribution in HTML,
Adobe Acrobat Portable Document Format (PDF), PostScript, and ASCII
text formats, all automatically derived from the original source file
in nroff/troff markup, ndiff.man,

See the companion INSTALL file for installation instructions.

%% /u/sy/beebe/tex/bibsort/README.AWK, Sat Nov  9 15:35:00 1996
%% Edit by Nelson H. F. Beebe <beebe@plot79.math.utah.edu>

These notes provide some information about awk, in case you are
unfamiliar with it, or want to learn more about it.

I use the awk programming language for implementing many of my
software tools (I have written more than 114,000 lines of awk code as
of [09-Nov-1996]), and I use it in teaching as an example of a little
language that every computer user who does text processing can benefit
from learning.

While awk is an interpreted language which suffers a runtime
performance penalty compared to natively compiled languages such as
Ada, C, C++, Fortran, and Pascal, for many text processing problems it
is almost perfect.  A C implementation of my bibcheck utility ran 3.5
times faster than the awk version, but took 22.4 times as many lines
of code!  And, of course, the awk version was much easier to write,
and required very little debugging.

awk is a POSIX standard, though I don't yet have on hand the POSIX awk
language description.  This means that you can expect your computer
vendor to provide it, and that it should be widely available for a
long time.

awk is a clean simple language, with few blemishes.  This is in stark
contrast to perl, which I find so ugly that I refuse to learn it, even
though I deeply appreciate what it is trying to do.

The official description of awk is found in the book

@String{pub-AW                  = "Ad{\-d}i{\-s}on-Wes{\-l}ey"}
@String{pub-AW:adr              = "Reading, MA, USA"}

@Book{Aho:1987:APL,
  author =       "Alfred V. Aho and Brian W. Kernighan and Peter J.
                 Weinberger",
  title =        "The {AWK} Programming Language",
  publisher =    pub-AW,
  address =      pub-AW:adr,
  pages =        "x + 210",
  year =         "1988",
  ISBN =         "0-201-07981-X",
  LCCN =         "QA76.73.A95 A35 1988",
  bibdate =      "Tue Dec 14 22:33:46 1993",
}

Another book which you may find useful (though I much prefer the above
one) is

@String{pub-ORA                 = "O'Reilly \& {Associates, Inc.}"}
@String{pub-ORA:adr             = "981 Chestnut Street, Newton, MA 02164, USA"}

@Book{Dougherty:SA91,
  author =       "Dale Dougherty",
  title =        "sed {\&} awk",
  publisher =    pub-ORA,
  address =      pub-ORA:adr,
  pages =        "xxii + 394",
  year =         "1991",
  ISBN =         "0-937175-59-5",
  LCCN =         "QA76.76.U84 D69 1991",
}

There is also a recent one (based on the GNU awk implementation) that
I have not yet seen:

@String{pub-SSC                 = "Specialized Systems Consultants"}
@String{pub-SSC:adr             = "P.O. Box 55549, Seattle, WA 98155"}

@Book{Robbins:1996:EAP,
  author =       "Arnold Robbins",
  title =        "Effective {AWK} Programming",
  publisher =    pub-SSC,
  address =      pub-SSC:adr,
  year =         "1996",
  URL =          "http://www.ssc.com/ssc/eap/",
  ISBN =         "0-916151-88-3",
  LCCN =         "",
  acknowledgement = ack-nhfb,
  pages =        "321",
  price =        "US\$27.00",
  bibdate =      "Fri Jun 14 17:24:04 1996",
  libnote =      "Not yet in my library.",
}

Some other publications on, and suppliers of, awk are:

@String{j-SUNEXPERT             = "SunExpert"}
@Article{Collinson:awk,
  author =       "Peter Collinson",
  title =        "Awk",
  journal =      j-SUNEXPERT,
  volume =       "2",
  number =       "1",
  pages =        "33--36",
  month =        jan,
  year =         "1991",
}

@String{pub-FSF                 = "{Free Software Foundation}"}
@String{pub-FSF:adr             = "675 Mass Ave, Cambridge, MA 02139,
                                  USA, Tel: (617) 876-3296"}

@Misc{FSF:gawk,
  key =          "GAWK",
  title =        "The {GAWK} Manual",
  howpublished = pub-FSF # " " # pub-FSF:adr,
  year =         "1987",
  note =         "Also available via ANONYMOUS FTP to
                 \path|prep.ai.mit.edu|. See also \cite{Aho:APL87}.",
}

@Misc{MKS:awk,
  author =       "{Mortice Kern Systems, Inc.}",
  title =        "{MKSAWK}",
  year =         "1987",
  note =         "35 King Street North, Waterloo, Ontario, Canada, Tel:
                 (519) 884-2251. See also \cite{Aho:APL87}.",
}

@Misc{ONW:awk,
  author =       "{OpenNetwork}",
  title =        "{The Berkeley Utilities}",
  year =         "1991",
  note =         "215 Berkeley Place, Brooklyn, NY 11217, USA, Tel:
                 (718) 398-3838.",
  altnote =      "See ad on p. 108 of April 1991 UNIX Review.",
}

@Misc{Polytron:polyawk,
  author =       "Polytron Corporation",
  title =        "{Poly{\-}AWK}",
  year =         "1987",
  note =         "170 NW 167th Place, Beaverton, OR 97006. See also
                 \cite{Aho:APL87}.",
}

@String{j-SPE                   = "Soft{\-}ware\emdash Prac{\-}tice
                                  and Experience"}

@Article{VanWyk:awk,
  author =       "Christopher J. Van Wyk",
  title =        "{AWK} as Glue for Programs",
  journal =      j-SPE,
  volume =       "16",
  number =       "4",
  pages =        "369--388",
  month =        apr,
  year =         "1986",
}

These entries are all taken from

	ftp://ftp.math.utah.edu/pub/tex/bib/index.html#master

which records books in my library, and other selected references; by
the time you read this, there may be more awk-related entries in that
bibliography.

At the time that the Aho, Kernighan, and Weinberger book appeared, awk
was only available in UNIX systems, and it took a few years for UNIX
vendors to incorporate the new, and much enhanced, version of the
language described in the book.  Most UNIX vendors retain the name
`awk' for the old original function-less language from 1978, and call
the 1987 one `nawk' (for `new awk').  An important exception is IBM,
which supplies the new implementation on RS/6000 AIX systems, but
calls it just awk.

Unfortunately, several vendors have not kept up with Brian Kernighan's
further development of awk, with the result that some nawk
implementations lack features that were added after the 1987 book was
published, notably the ENVIRON[] array for access to environment
variables.  Also, some of the vendor implementations have not
incorporated bug fixes which Kernighan introduced.

Fortunately, this situation has improved through three important
developments:

	(1) Arnold Robbin's gawk, the GNU Project implementation of
	awk, available at
		ftp://prep.ai.mit.edu/pub/gnu/gawk-x.yy.tar.gz
	The gawk distribution includes ports for the Amiga, the IBM
	PC, the Atari, and for DEC OpenVMS.

	(2) Brian Kernighan's awk has been released by AT&T Bell Labs,
	and is available at
		http://cm.bell-labs.com/who/bwk/awk.sh

	(3) Mike Brennan's mawk, available at
		ftp://ftp.whidbey.net/pub/brennan/mawkx.y.z.tar.gz

Besides these freely-distributable (for non-commercial purposes, as
detailed in licenses included with their distributions), there are
commercially-supported versions of awk for the IBM PC world and other
machines, recorded in the BibTeX entries above.

Robbins, Kernighan, and Brennan are in contact with one another, so
their implementations support the same features, although gawk has
added a number of (well-documented) extensions that the others have
not yet incorporated.  With a few exceptions, I've tried hard in my
awk programs to stick to the standard language as documented in the
1987 book.

	(1) gawk and recent AT&T awk have the IGNORECASE extension,
	which I only rarely use.  That feature is difficult to
	simulate in a portable awk program.

	(2) gawk and mawk have toupper() and tolower() for efficient
	lettercase conversion; it is possible to implement these in
	awk itself, but only very inefficiently

	(3) gawk, mawk, and recent AT&T awk support the ENVIRON[]
	array for efficient access to environment variables.

	(4) gawk, mawk, and recent AT&T awk support the names
	/dev/stderr and /dev/stdout for the standard UNIX devices
	(which sadly, UNIX never got around to giving names), and gawk
	and AT&T awk support /dev/stdin.  The alternative to
	/dev/stderr is /dev/tty (except it fails if the process is
	running without a controlling terminal, which happens for
	batch jobs, and for background processes), or a horrid
	contortion to invoke the shell and cat.  Since any realistic
	program will require the ability to write error messages, use
	of /dev/stderr is the one feature that is likely to cause
	portability problems.

	(5) only gawk is 8-bit clean, and capable of processing all
	256 8-bit byte values, including NUL, and accepting 8-bit
	characters in regexp patterns.  Recent AT&T awk loses NUL
	during processing (because it uses C-style strings internally,
	which reserve NUL for a string terminator), and it rejects
	characters 128..255 in regexp patterns.  mawk gets thoroughly
	confused by NUL in its input stream, and terminates; it
	handles the other 255 byte values (1..255) correctly, at least
	for I/O.

For further discussion of awk implementation differences and language
evolution, see the
	(gawk.info)Language History
node in the GNU Emacs info system.

     Comments on quadruple-precision machine epsilon computation

				  by

			  Nelson H. F. Beebe
		   Center for Scientific Computing
			  University of Utah
		 Department of Mathematics, 322 INSCC
			 155 S 1400 E RM 233
		    Salt Lake City, UT 84112-0090
				 USA
 Email: beebe@math.utah.edu, beebe@acm.org, beebe@ieee.org (Internet)
	       WWW URL: http://www.math.utah.edu/~beebe
		      Telephone: +1 801 581 5254
		FAX: +1 801 585 1640, +1 801 581 4148

		Last revised: Mon Feb 21 16:31:12 2000


Several vendors have implemented a 128-bit quadruple-precision
floating-point format, among them, Compaq/DEC, HP, SGI, and Sun, all
implemented as a 1-bit sign, 15-bit exponent, and 113-bit fraction
(including one hidden bit).  This makes the machine epsilon 2^{-112} =
1.93e-34.  [If the significand is 1.fffff...fff, with p-1 bits, f,
after the binary point, then the machine epsilon is 0.000...001, which
is 2^(p-1).]

Intel and Motorola offer IEEE 754 80-bit temporary real (1-bit sign,
15-bit exponent, 64-bit significand with no hidden bit), which C
compilers offer as long double, padding to 96 bits (12 bytes) or 128
bits (16 bytes) for storage access efficiency.  The gcc compilers in
GNU/Linux on Intel x86 use 12 bytes for long double, and the machine
epsilon is 2^{-63} = 1.08e-19.

IBM RS/6000 systems also have a 128-bit quadruple-precision format, but
unlike the others, this is a pair of normal IEEE 754 64-bit values.
The IBM compilers require an extra option, -qlongdouble, to enable
code generation for it; without that option, long double is treated
like double.

This `double-double' representation, while convenient for the
implementation of quadruple-precision operations using only the
double-precision hardware instructions, and particularly, the fused
multiply-add instruction, has a serious side effect: given
double-precision values a and b, the quadruple-precision value a + b
represents a significand of the form

	pppppp...ppp?????....?????qqqqq....qqqq

in which there can be unknown bits in the middle.  For example, one
can have a = 1 and b = 1e-323: this does not imply that their sum has
323 accurate decimal digits, even though 1 + 1.e-323 differs from 1.

On this system, code of the form

	do
	{
		tolerance = ...
	}
	until ((x + tolerance) != x)

which works perfectly well in IEEE 754 single, double, and
temporary-real formats, as well as Sun-style quadruple-precision
arithmetic, and also Cray, IBM, and Compaq/DEC VAX mainframe formats,
will not work as expected, because tolerance must underflow to zero
before the sum x + tolerance finally differs from x, when x == 1.

This affects the computation of the machine epsilon, which normally
takes the form

fp_t machine_epsilon(void)
{
    fp_t x;

    while ((1 + x/2) != 1)
	x /= 2;

    return (x);
}

(writing it in a form that doesn't require length modifiers on the
constants, allowing typedefs of fp_t to float, double, and long double
without changing the code, and assuming that longer registers are not
involved in the computation in while condition).

On the IBM RS/6000, this code produces the incorrect answer
4.9406564584124654e-324 (== 2^(-1074)).

Since there are only 53 bits in each of the two significands, the
expected precision is only (2*53 =) 106 bits, corresponding to just
under 31 decimal digits.  The machine epsilon should therefore be
2^{-105} = 2.47e-32.

Despite several experiments, and considerable thought over the course
of a day, I haven't yet been able to program a MACHINE-INDEPENDENT way
to write the machine_epsilon() function for the quadruple-precision
precision case.  I've therefore temporarily taken the easy way out,
and put in a machine-dependent conditional that checks for the IBM
RS/6000, and long double revert to double.  During my Web searching, I
came across a reference to an Apple floating-point implementation that
uses a similar double + double representation; thus, this problem may
be endemic on all systems based on the Power and PowerPC chips.

On Apple Rhapsody (also known as MacOS 10), the C compiler (gcc
2.7.2.1) treats long double like double, so this problem isn't
exhibited.

On GNU/Linux on Apple Macintosh, the C and C++ compilers also
treat long double like double; they define the symbols
	__powerpc__
	__PPC
	__PPC__
	powerpc
	PPC

The IBM RS/6000 compilers on AIX 4.x define the symbols
	_IBMR2
	_POWER
independent of which architecture subset (com, pwr, pwr2,
pwrx, ppc, ppcgr) is selected by a -qarch=xxx flag.

The Apple Rhapsody compiler defines

    __ARCHITECTURE__="ppc"
    __ppc
    __ppc__
    ppc

I've therefore modified confix.h to test for some of these symbols,
and if any are found, to disable long double arithmetic.  There was
already a similar disabling there for the NeXT, where the compiler
handles long double, but the run-time library doesn't.

Fri Mar 31 15:24:16 2000
I tracked down an IBM Web page that discusses implications of their
peculiar 128-bit floating-point format:

http://www.rs6000.ibm.com/doc_link/en_US/a_doc_lib/aixprggd/genprogc/128bit_long_double_floating-point_datatype.htm#CE7AE41923raga

Just in case that page disappears, or moves, here is what IBM has to
say about the machine epsilon:

>> ...
>> Epsilon
>>
>> The ANSI C standard defines the value of epsilon as the difference
>> between 1.0 and the least representable value greater than 1.0, that
>> is, b**(1-p), where b is the radix (2) and p is the number of base b
>> digits in the number. This definition requires that the number of base
>> b digits is fixed, which is not true for 128-bit long double numbers.
>>
>> The smallest representable value greater than 1.0 is this number:
>>
>> 0x3FF0000000000000, 0x0000000000000001
>>
>> The difference between this value and 1.0 is this number:
>>
>> 0x0000000000000001, 0x0000000000000000
>> 0.4940656458412465441765687928682213E-323
>>
>> Because 128-bit numbers usually provide at least 106 bits of
>> precision, an appropriate minimum value for p is 106. Thus, b**(1-p)
>> and 2**(-105) yield this value:
>>
>> 0x3960000000000000, 0x0000000000000000
>> 0.24651903288156618919116517665087070E-31
>>
>> Both values satisfy the definition of epsilon according to standard
>> C. The long double subroutines use the second value because it better
>> characterizes the accuracy provided by the 128-bit implementation.
>> ...