That is really interesting, but I can't see how to apply the Kahan's algorithm to a set of signals. In my original question, I was thinkin of mixing signals of arbitrary sizes. I could relax this requirement, and forcing all the signals to be of a given size, but I can't see how a sample by sample summation, where there are M sums (M the forced length of the signals) could profit from a running compensation. Also, with a non linear operation, I fear of introducing discontinuities that could sound even worse than the white noise I expect using the simple approach..
On Dec 10, 2012, at 1:43 AM, Brad Smith <rainwarr...@gmail.com> wrote: > I would consider storing N and your sum separately, doing the division > only to read the output (don't destroy your original sum in the > process). I guess this is the first thing that Bjorn suggested, but > maybe stated a little differently. > > There's a technique called Kahan's Algorithm that tries to compensate > for the running errors accumulated during summation. It can help > increase the precision a bit: > http://en.wikipedia.org/wiki/Kahan_summation_algorithm > > Also, there's the simple technique of recursively dividing the sums > into pairs, which will prevent later results from having greater error > than earlier ones, though you'd probably need to know N in advance for > this to be practical: http://en.wikipedia.org/wiki/Pairwise_summation > > -- Brad Smith > > > > > On Sun, Dec 9, 2012 at 7:32 PM, Alessandro Saccoia > <alessandro.sacc...@gmail.com> wrote: >> Thanks Bjorn, >> >>> >>> On Dec 9, 2012, at 2:33 PM, Alessandro Saccoia wrote: >>> >>>> Hi list, >>>> given a large number of signals (N > 1000), I wonder what happens when >>>> adding them with a running sum Y. >>>> >>>> 1 N - 1 >>>> Y = ----- * X + ( -------) * Y >>>> N N >>>> >>> >>> Yes, your intuition is correct: this is not a good way to go, although how >>> bad it is depends on your datatype. All I can say here is that this formula >>> will result in N roundoff errors for one of your signals, N-1 for another, >>> and so on. >>> >>> You might *need* to use this formula if you don't know N in advance, but >>> after processing the first sample, you will know N, (right?) so I don't see >>> how that can happen. >> >> It's going to be a sort of comulative process that goes on in time, so I >> won't necessarily know N in advance. If had a strong evidence that I should >> prefer one method over the other, I could decide to keep all the temporary >> X1, X2,… and recompute everything each time. Performance and storage are not >> a strong concern in this case, but the quality of the final and intermediate >> results is. >> >>> >>> >>> When you do know N in advance, it would be better to: >>> >>> 1 >>> Y = ---- * ( X + X + ..... X ) >>> N 1 2 N >>> >>> or >>> >>> 1 1 1 >>> Y = ---- * X + --- X + ..... + --- X >>> N 1 N 2 N N >>> >>> Exactly which is better depends on your datatype (fixed vs floating point, >>> etc). If you are concerned about overflow, the latter is better. For >>> performance, the former is better. For precision, without thinking too >>> carefully about it I would think the former is better, but, obviously, not >>> in the presence of overflow. >> >> I think I will use floating points, and maybe spend some time trying to >> figure out what is the transfer function for N->+inf and seeing if something >> (thinking of a sort of dithering) could help in keeping the rounding error >> limited to a certain region of the spectrum to avoid white noise. I am not >> sure I will make it, but I could definitely give it a try. cheers, >> >> alessandro >> >>> >>> bjorn >>> >>>> Given the limited precision, intuitively something bad will happen for a >>>> large N. >>>> Is there a better method than the trivial scale and sum to minimize the >>>> effects of the loss of precision? >>>> If I reduce the bandwidth of the inputs signals in advance, do I have any >>>> chance of minimizing this (possible) artifacts? >>>> Thank you >>>> >>>> -- >>>> dupswapdrop -- the music-dsp mailing list and website: >>>> subscription info, FAQ, source code archive, list archive, book reviews, >>>> dsp links >>>> http://music.columbia.edu/cmc/music-dsp >>>> http://music.columbia.edu/mailman/listinfo/music-dsp >>> >>> ----------------------------- >>> Bjorn Roche >>> http://www.xonami.com >>> Audio Collaboration >>> http://blog.bjornroche.com >>> >>> >>> >>> >>> -- >>> dupswapdrop -- the music-dsp mailing list and website: >>> subscription info, FAQ, source code archive, list archive, book reviews, >>> dsp links >>> http://music.columbia.edu/cmc/music-dsp >>> http://music.columbia.edu/mailman/listinfo/music-dsp >> >> -- >> dupswapdrop -- the music-dsp mailing list and website: >> subscription info, FAQ, source code archive, list archive, book reviews, dsp >> links >> http://music.columbia.edu/cmc/music-dsp >> http://music.columbia.edu/mailman/listinfo/music-dsp > -- > dupswapdrop -- the music-dsp mailing list and website: > subscription info, FAQ, source code archive, list archive, book reviews, dsp > links > http://music.columbia.edu/cmc/music-dsp > http://music.columbia.edu/mailman/listinfo/music-dsp -- dupswapdrop -- the music-dsp mailing list and website: subscription info, FAQ, source code archive, list archive, book reviews, dsp links http://music.columbia.edu/cmc/music-dsp http://music.columbia.edu/mailman/listinfo/music-dsp
