jer@peora.UUCP (J. Eric Roskos) (03/04/86)
> Now, is this an architectural question: should or could randomized > rounding be provided by a floating point unit? Assuming you can cheaply > obtain a random number in hardware (amplify transistor noise?) doing > randomized rounding in the floating point unit would be a lot faster than > doing so in software, where you'd have to extract and play around with the > guard bits. Well, we talked about this about 6 months ago, so I apologise to those who have heard it before, but I know the people on the Usenet change fast, thus my reposting. One of the ways to achieve "randomized rounding" is described by Knuth in section 4.2.2 of "Seminumerical Algorithms", around the bottom of page 221 of the 2nd Edition. He says, ...for most numerical calculations the best policy appears to be the rounding scheme specified in Algorithm 4.2.1N, which insists that the least significant digit should always be made even (or always odd) when an ambiguous value is rounded. This is not a trivial technicality, of interest only to nit-pickers; it is an important practical consideration, since the ambiguous case arises surprisingly often and a biased rounding rule produces significantly poor results. ... This phenomenon, called "drift", will not occur when we use a stable rounding rule based on the parity of the least significant digit. ... [but] how should we choose between [rounding to even or rounding to odd]? When the radix ... is odd, ambigous cases never arise except during floating point division, and the rounding in such cases is comparatively unimportant. For even radices, there is reason to prefer the following rule: "Round to even when b/2 is odd, round to odd when b/2 is even". ... Its effect is to provide some memory of an ambiguous rounding so that subsequent rounding will tend to be unambiguous. On the other hand, some people prefer rounding to even in all cases, so that the remainder will tend to be 0 more often. Neither alternative conclusively dominates the other ... As I explained at some length in my previous posting on this subject, however, having the "best" rounding algorithm is not always what people want; Concurrent's floating point unit in the 3200 series machines, for example, uses the above algorithm (the one in quotes), yet it has gotten occasional harsh criticism because certain other large manufacturer(s) use a "worse" rounding algorithm, and people have fixed up their Fortran programs to correct for the errors introduced by these rounding algorithms -- thus when the programs are run on a machine that gives "correct" results for the arithmetic, the results for the programs turn out wrong! This is a common difficulty in trying to implement the best things in the real world... they don't always work out for reasons other than their inherent merits. -- UUCP: Ofc: jer@peora.UUCP Home: jer@jerpc.CCUR.UUCP CCUR DNS: peora, pesnta US Mail: MS 795; CONCURRENT Computer Corp. SDC; (A Perkin-Elmer Company) 2486 Sand Lake Road, Orlando, FL 32809-7642 LOTD(5)=O ---------------------- Amusing error message explaining reason for some returned mail recently: > 554 xxxxxx.xxxxxx.ATT.UUCP!xxx... Unknown domain address: Not a typewriter (The above message is true... only the names have been changed...)