Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: Notesfiles $Revision: 1.7.0.10 $; site ccvaxa
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxn!ihnp4!inuxc!pur-ee!uiucdcs!ccvaxa!aglew
From: aglew@ccvaxa.UUCP
Newsgroups: net.arch
Subject: Re: Oh no! More integer division
Message-ID: <5100014@ccvaxa>
Date: Thu, 27-Feb-86 21:17:00 EST
Article-I.D.: ccvaxa.5100014
Posted: Thu Feb 27 21:17:00 1986
Date-Received: Sat, 1-Mar-86 03:28:36 EST
References: <11896@ucbvax.BERKELEY.EDU>
Lines: 33
Nf-ID: #R:ucbvax.BERKELEY.EDU:11896:ccvaxa:5100014:000:1842
Nf-From: ccvaxa.UUCP!aglew    Feb 27 20:17:00 1986


>/* Written 11:04 am  Feb 17, 1986 by taylor@glasgow.UUCP in ccvaxa:net.arch */
>During my undergraduate days, one of the Great Men who taught us suggested,
>seriously I think, that rounding should be up OR down AT RANDOM, with a 50/50
>chance. This would remove systematic errors introduced by rounding in iteractive
>algorithms. ( which way do you round 0.5 is the hardest question; 0.5000001 and
>0.4999999 are much easier.)

Ref: Digital Signal Processing, Oppenheim and Schafer, Prentice-Hall, 1975.
Section 9.5 Effects of Finite Register Length in Discrete Fourier Transform
Computations, p. 459, Figure 9.23. A graph showing randomized vs. 
non-randomized rounding - randomized rounding is about 3 times better for
1K DFTs. Their reference isWeinstein, "Roundoff Noise in Floating Point Fast 
Fourier Transform Computation", IEEE Trans. Audio Electroacoust., Vol AU-17,
Sept. 1969, pp 209-215.

So much for the formalities: I just felt like going back to that textbook 
since I really enjoyed my DSP courses.

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.

Don't jump on me, RISC proponents! I'm one of you (well, I used to be).
But this could be one of those applications where a bit of hardware support,
a few extra gates, might solve something that would require a lot of 
instructions in software. Hardware randomized rounding doesn't need to be
microcoded.

Related Q: do any signal processing chips have a randomized rounding mode?
If so, how do they do it? I don't recall that it is in the TI32010 specs.