1
$\begingroup$

Sedgewick and Wayne talk about how sorting algorithms and, specifically, priority queues are used in devising ways to improve accuracy in floating-point calculations: https://algs4.cs.princeton.edu/25applications/

Scientific computing is often concerned with accuracy (how close are we to the true answer?). Accuracy is extremely important when we are performing millions of computations with estimated values such as the floating-point representation of real numbers that we commonly use on computers. Some numerical algorithms use priority queues and sorting to control accuracy in calculations.

What "numerical algorithms" use priority queues and sorting like this?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I'll give you a simple example.

Suppose you have some floating-point numbers to add together. We'll assume they're all non-negative so that cancellation isn't an issue.

For the purpose of this example, I'm going to use decimal with four significant digits of precision just to illustrate the point.

The numbers are:

1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e+0

That is, ten copies of 1e-4 and one copy of 1.

This sum can be perfectly represented in our toy floating-point format:

1.001e+0

But the answer that you get depends on what order you do the additions! If you start at the top of the list and work your way down, the partial sums are:

1.000e-4
2.000e-4
3.000e-4
4.000e-4
5.000e-4
6.000e-4
7.000e-4
8.000e-4
9.000e-4
1.000e-3
1.001e+0

But if you start at the bottom and work your way to the top, the partial sums are:

1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0

Clearly, you need to add the small numbers first. So here are two possible algorithms.

  • Sort the numbers into ascending order, then sum them in that order.
  • Insert the numbers into a priority queue. Remove the two smallest numbers, add them, and insert the sum back into the priority queue. Repeat until there is one number left.

Exercises:

  1. Is there a set of numbers for which these two algorithms return different answers?
  2. Is one of these algorithms better than the other, in the sense of always returning a more accurate final answer?
  3. Can we do even better?
Improve this answer
$\endgroup$
2
  • $\begingroup$ A trivial situation is numerically solving differential equations. You usually have values like x, y at time t, and calculate some small terms that need to be added to get a solution at time t+h. It is much better to add the small terms and at them to a large value, rather than adding them individually. Much smaller rounding error at zero cost. $\endgroup$ Commented Feb 25, 2020 at 8:54
  • $\begingroup$ 3. With IEEE 754 floating point arithmetic, we can after adding x+y calculate the exact rounding error in the result. This is a consequence of the fact that x-y is calculated without any rounding error if y/2 <= x <= 2y. $\endgroup$ Commented Feb 25, 2020 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.