How much will this accumulate floating point errors?

Question

I have a random process that, when called, returns a random number between 0 and K-1, where K may be decently high. I want to keep track of the number of times any outcome occurs, and normalize all the counts into a probability distribution. I want to do this every time I call the random process so that my distribution estimate of the random process is as up-to-date as possible.

A naive approach could be the following:

while ( true ) {
    int n = randomProcess();

    ++totalCount;
    ++count[n];
    update();

    do_work_with_updated_prob_vector();
}

void update() {
    for ( int i = 0; i < K; ++i )
        prob[i] = count[i] / static_cast<double>(totalCount);
}

However when K starts to become big this approach needs to read the whole count vector at every probability update, which is undesirable due to cache misses and memory access cost. I have devised another solution which is on my limited tests around 30% faster with K~1000. The new update function needs to know the index of the last updated element:

void fastUpdate(int id) {
    if ( totalCount == 1 ) {
        prob[id] = 1.0;
        return;
    }
    double newProb = count[id] / static_cast<double>(totalCount - 1);
    double newProbSum = 1.0 + ( newProb - prob[id] );

    prob[id] = newProb;
    for ( int i = 0; i < K; ++i )
        prob[i] /= newProbSum
}

This approach works in theory, however I am worried about floating point precision errors that will be accumulating due to the imperfect normalizations that get performed. Should I still call the basic update function once in a while to get rid of them? If so, how often? How big can this error become? I have little experience with this sort of problems, and I know that I do not need to underestimate them.

EDIT: Since this seems to be a big deal, I'm going to explain better what I'm doing here so that we may focus more on the problem I stated. I have also updated my first algorithm at the top so that it shows what I am doing better.

I am writing a series of AI algorithms that need to learn an environment that is initially unknown. In this case, the environment is learned by approximating what is seen into a distribution. At each iteration, the algorithm will revise its decisions based on the new data (which not only includes the updated prob vector, but also other things). Since these values are not only used, but may also be used multiple times within a single iteration, I would guess that it is better to compute the result once and then use it, which is what I am doing with the update function.

In addition I would like to add that whether I need or not to update the prob vector at every iteration or not is truly a non-issue here. The contract of the function fastUpdate is that it will do a fast update, and that is where my issue stems from. If I will not need to update so often, I will do that by NOT calling that function at every iteration. Since at the moment I DO need to call it, I am doing it. I hope this clarifies.

Answer 1

Just as a for instance, take this python example:

for i in range(1000000):
    x = rnd.randrange(0,10)
    intar.append(x)
    dblar.append(x/100.0)
intsum = 0
for i in intar:
    intsum += i
dblsum = 0.0
for d in dblar:
    dblsum += d
print("int: %f, dbl: %f, diff: %f" % ((intsum/100.0), dblsum, ((intsum/100.0)-dblsum)))

yields:

int: 45012.230000, dbl: 45012.200000, diff: 0.030000

Now, I forced a divisor to be sure that there would be consistent rounding errors. I'm guessing that the nature of your input data distribution would be critical to determining how much errors will accumulate; though I never new or have forgotten the maths necessary to derive an answer. With the exact behavior of the floating point math being known based on compiler options, it should be possible to derive the range of errors given an idea of the input data.

Answer 2

Rather than update prob when you add items, update it when you need to read the probabilities. Use a boolean flag to indicate whether or not prob needs updating before you read from it.

while ( true ) {
    int n = randomProcess();

    ++totalCount;
    ++count[n];
    dirty = true;
}

void updateBeforeRead() {
    if(dirty) {
        for ( int i = 0; i < K; ++i )
            prob[i] = count[i] / static_cast<double>(totalCount);
        }
        dirty = false;
    }
}

If your usage flips between a large number of samples followed by a large number of calculations based on the probabilities then this should be efficient whilst limiting rounding issues.