From: hrubin@mentor.cc.purdue.edu (Herman Rubin)
Subject: Re: Hardware Support for Numeric Algorithms
Organization: Purdue University Statistics Department
Date: Sat, 7 Nov 1992 12:55:41 GMT

In article <721104899@sheol.UUCP> throopw@sheol.UUCP (Wayne Throop) writes:

>: From: bs@gauss.mitre.org (Robert D. Silverman)
>: Message-ID: <1992Nov5.202412.7266@linus.mitre.org>
>: Needless to say, there are people who have to worry about speed FIRST,
>: and that other considerations are (almost) irrelevent.

>: From: bs@gauss.mitre.org (Robert D. Silverman)
>: Message-ID: <1992Nov5.203759.8030@linus.mitre.org>
>: Dr. Rubin's main rule is:
>:       "The code should run as fast as possible"
>: For him, all other considerations are secondary. Who are you to tell
>: him what his priorities should be?

>Ah, Robert seems to be saying that Dr. Rubin is a member of that large
>class of people for whom it is very very important to get the wrong
>answer as soon as possible.  But wait.... if "The code should run as
>fast as possible" and "all other considerations are secondary", why
>doesn't he just run the null istream?

>Since Dr. Rubin *doesn't* suggest running the null istream, I conclude
>that the "(almost) irrelevant" above contains a very, very large point
>swept under the rug.  It is of *primary* importance that the code be
>correct.

Now where did you get the idea that either of us wants an incorrect
routine?  Of course it is important that code be correct.  However,
program?  Of course, code to be useful should be correct, but I suspect
that every operating system has some essential bug in it; Murphy's Law
applies to computer programming.  However, any errors in the code I
posted were not due to my use of gotos, or code rearrangement to gain
performance.  One of my respondents suggested that I post to the net
a long explanation of how the algorithm was derived, and that will be
done next week.

Certainly code should be checked in whatever way possible for correctness.
In principle, the code I have posted could be so checked by setting up a
good trace program, feeding in random numbers of a higher quality than I
know how to get, and running it more than 10^20 times.  This would be more
than 10^13 of Dr. Silverman's MIPS-years; it cannot be done.  So I am 
required to make a proof of correctness by investigating that the code
follows the algorithm.

But it is quite possible to speed up the flow of the code, and in parallel
remove the bugs.  This is not all that different from what language designers,
compiler writers, and hardware designers do.  Designing for the goal does not
mean that all the implementation bugs are removed first; this cannot even be
done, as any change may introduce bugs.  The particular code I posted is not
tailored for a specific machine; hardware can cause things to be done in a
different manner, and what is essentially the same algorithm should be done
somewhat differently on different machines, such as vector and parallel
processors.  The results will be different, so that that method of comparison
cannot be used.

As far as readability, portability, and ease of maintenance are concerned,
the code I have posted is quite portable.  The most readable version was
the one which had ONLY gotos for control; this got the most responses,
both to the net and by email, and these responses were quite accurate,
even the ones which would have slowed down the operation of the compiled
version.  Part of the reason is that I find the logic of the goto quite
simple, and I suspect that even those who condemn it do so for reasons
other than understandability of what it means.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@snap.stat.purdue.edu (Internet, bitnet)  
{purdue,pur-ee}!snap.stat!hrubin(UUCP)