Re: C# generic containers from a "C++ perspective"

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

Jon Harrop wrote:
Ben Voigt [C++ MVP] wrote:
Jon Harrop wrote:
My explanation of why your algorithm is fundamentally broken still
stands. If you implement the floating-point and integer algorithms
properly you will see that there is nothing worth factoring out
between them.

The implementation would be:

Maintain the last N items in a ring buffer. (This consists of an
array of size N and the index of the oldest element).
Maintain the sum of all the items in an accumulator.
On arrival of a new data point, deduct the oldest datum from the sum,
overwrite it with the new one (updating the index), add the new one
to the sum, return sum / N.

That is the fundamentally-broken algorithm that I was expecting you to
describe: you have implicitly assumed that addition and subtraction
commute, which is true for integers and not floats.

Specifically, your algorithm will suffer from cumulative round-off
errors and will not handle special values (e.g. infinities) at all.

This works very well for any numeric data type as long as the
accumulator doesn't overflow,

That is not true. You only need one element 10^17x larger than any
other currently in the buffer and you lose all precision in your
accumulator from catastrophic round-off error, hundreds of orders of
magnitude before any overflow.

but the accumulator doesn't need to be the same type as each buffer
element.

I see. And what type would you recommend for the accumulator? An
arbitrary-precision rational, perhaps?

The issue you describe is theoretically valid, but not applicable to
real-world data created via analog-to-digital sampling and linear functions
thereof, which is probably somewhere upwards of 99% of all data sets. If it
is a problem, you can always recalculate the sum directly from the stored
elements.


.

Relevant Pages

  • Re: C# generic containers from a "C++ perspective"
    ... If you implement the floating-point and integer algorithms ... Maintain the sum of all the items in an accumulator. ... your algorithm will suffer from cumulative round-off errors ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Is there a polynomial algorithm for that problem?
    ... The sum over all n numbers is negative. ... Unfortunately that algorithm does not scale. ... An instance of 3-Partition consists of a list of 3m positive integers ... list can be partitioned into m lists of size 3, ...
    (sci.math)
  • Re: Choose k random lines from file
    ... > What, for the algorithm shown above, or for any algorithm? ... Yes, that is an unbiased generator, but I had thought ... >>give less of a bias using an extra float or double ... >>distribution for the sum. ...
    (comp.programming)
  • Re: standard deviation, but without the mean
    ... Suppose Xsum is the sum of the the first n numbes and that X2 is ... Just keep track if X2 and Xsum as you go. ... Actually this is not a correct algorithm, ... the error in the least 9 digits.. ...
    (sci.stat.math)
  • Re: Vernons Prime Sieve
    ... I'm pretty sure the problem was my copying error regarding dif, ... the more initial primes are not found by the algorithm (they are ... which merely keeps each prime "next" to its current multiple. ... // difference between candidate and accumulator ...
    (sci.math)