5
\$\begingroup\$

I have written the following function in order to normalize a container of double, so that it sums up to 1.0:

/**
 * @brief This function normalizes a container so that it sums to 1.0.
 *
 * @param begin The beginning of the range to normalize.
 * @param end The end of the range to normalize.
 * @param out The beginning of the output range (can be the same as begin).
 */
template <typename InputIterator, typename OutputIterator>
void normalizeProbability(InputIterator begin, InputIterator end, OutputIterator out) {
    double norm = static_cast<double>(std::accumulate(begin, end, 0.0));
    std::transform(begin, end, out, [norm](decltype(*begin) t){ return t/norm; });
}

Is it possible to do better, or having a more precise result?

\$\endgroup\$
6
\$\begingroup\$

It looks pretty good as it is but I can offer the following:

template <typename InputIterator, typename OutputIterator>
void normalizeProbability(InputIterator begin, InputIterator end, OutputIterator out) {
    typedef typename std::iterator_traits<InputIterator>::reference ref_t;
    double norm = std::accumulate(begin, end, 0.0);
    std::transform(begin, end, out, [norm](const ref_t t){ return t/norm; });
}

I have removed the cast to double, which isn't necessary. The double return type is deduced by the 0.0 argument. I also changed to use std::iterator_traits instead of decltype which I think is a bit cleaner.

The biggest source of error you have is in the summation of norm. Adding a small floating point (FP) number (the dereferenced value) to a large floating point number (the current sum) will cause a truncation error. For example 1.0 + 1E-18 == 1.0 will return true due to the limited precision of FP-numbers. What you want to do is to add the numbers from the smallest to the biggest. But simply sorting isn't good enough, consider 10^20 entries (yeah I know fat chance but it's just for illustration) each with value 1E-18 you expect the norm to be 10^2, but in fact it will be close to 1.0 or less. Because after about 1E18 iterations the running sum will be so big that any remaining elements will truncate. So you need to have a heap, take the two smallest numbers, add them and put the result back into the heap. Then repeat until only one number is left, which will be the sum. This guarantees that you will always minimize the truncation error.

However I have no idea if this level of accuracy is necessary for you, but you stated precision as a question so I went for it. :)

\$\endgroup\$
  • \$\begingroup\$ Using an heap for the sum would require O(N) memory and O(Nlog(N)) time right? \$\endgroup\$ – Svalorzen Oct 16 '14 at 17:44
  • \$\begingroup\$ Sounds about right unless you can use the input range for the storage. But that's kind of ugly :) \$\endgroup\$ – Emily L. Oct 16 '14 at 17:49
  • \$\begingroup\$ My guess is that you can't, or you won't be able to perform the transform later. Or is there an actual way? \$\endgroup\$ – Svalorzen Oct 16 '14 at 17:51
  • \$\begingroup\$ Yeah didn't think of that. If you use the input range as the heap then whatever container that was backing the input will have been reduced to a single element and no longer contains the data you want to normalize. So throw that idea out of the window :) You need \$\mathcal{O}(n)\$ memory. \$\endgroup\$ – Emily L. Oct 16 '14 at 17:53
  • \$\begingroup\$ Or you can settle for sorting the input container before calling normalize and hope that the precision is good enough. If the number of elements is relatively small, you should be OK, depending on your application of course. The worst case is if the input is sorted in descending order... \$\endgroup\$ – Emily L. Oct 16 '14 at 17:58
0
\$\begingroup\$

As an additional note, which I just realized, I should check that norm is not equal to 0.0, or the normalization will break.

\$\endgroup\$
  • \$\begingroup\$ That is actually a question of definition. Assuming that no probability can be negative (what would that even mean?), if the sequence is empty then there will be no division by zero. The only other case where a division by zero can happen is if all the elements are zero. But then, if all events are impossible (zero probability), how do you normalize? Because that implies that they must be turned into possible events (non-zero probability) which doesn't make sense to me. The only possible recluse is to throw an exception if (norm == 0.0 && begin != end). \$\endgroup\$ – Emily L. Oct 17 '14 at 13:25
  • \$\begingroup\$ @EmilyL. Yeah, it is a question of definition, but only in the sense of the result of the operation. Checking for spurious inputs still makes sense, I guess. Whether I throw an exception or anything else I am going to document (in particular in my case I'll just set *out = 1.0). \$\endgroup\$ – Svalorzen Oct 17 '14 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.