Numerical Algorithms in C++
Generalized numerical algorithms such as accumulate work on every standard library sequence and let you supply the operation as an argument.
Predicting a Sum Before Running It
A common task in numerical programming is adding up a sequence of numbers. In C++ you can ask the standard library to do this work for you. The numeric header provides numerical algorithms that work with sequences of numbers, and accumulate is the best-known example. Instead of writing a loop yourself, you describe the sequence and a starting value, and the library walks through the sequence and combines each element with a running total.
Before reading the mechanics, try a prediction. Imagine a sequence holding the three values 1.5, 2.5, and 3.0. Now imagine the starting value is the integer 0 instead of the floating-point value 0.0. The question to ask is whether the total you get back will match the hand sum of 7.0 or will come out different. Make a guess, then look at the reveal below.
What do you think happens?
Given the values 1.5, 2.5, and 3.0 and a starting value of the integer 0, what does std::accumulate return?
Reveal answer
6, a whole number with the fractional parts lost
The type of the starting value controls the arithmetic. Because the starting value is an int, the running total is an int at every step, so each intermediate result loses its fractional part. The sections below trace this step by step.
Generalized Algorithms Versus Fixed Sum Calculations
A fixed sum calculation is one where the loop is written for one specific job. A hand-written loop that always adds each element is tied to addition, and every change in behavior means editing the loop. A generalized numerical algorithm separates two things: the traversal of the sequence, which the library handles, and the operation that combines each element with the running total, which you can supply.
The same pattern works on any sequence in the standard library, not only a list of doubles. The algorithm is also not locked to addition. Its general version accepts the operation as a parameter, and a version with the most common operator is provided alongside it for convenience. For accumulate, that common operator is addition, so calling accumulate with only the range and a starting value adds the elements.
Tracing the Running Total
The following program builds a vector of three doubles and asks accumulate to add them. The call takes three arguments: the start position, the end position, and the starting value. Notice that there is no loop in the program. The traversal is done inside the algorithm.
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<double> values{1.5, 2.5, 3.0};
double total = std::accumulate(values.begin(), values.end(), 0.0);
std::cout << total << "\n";
return 0;
}- 1The vector holds three doubles, so every element is a double.
- 2accumulate receives the start position, the end position, and the starting value 0.0.
- 3The algorithm starts its running total at 0.0 and visits each element in order.
- 4At each visit it combines the running total with the element, and the final total is returned.
- 5The returned value is stored in total and printed.
values.begin()is the start position of the rangevalues.end()is the end position, one past the last element- 0.0 is the starting value, a double
7Following the running total with a 0.0 start
Trace accumulate over the values 1.5, 2.5, and 3.0 with the starting value 0.0.
- 1Set the running total
The starting value 0.0 becomes the running total before any element is visited.
- 2Visit the first element
Combine 0.0 with 1.5 using addition. The running total becomes 1.5.
- 3Visit the second element
Combine 1.5 with 2.5. The running total becomes 4.0.
- 4Visit the third element
Combine 4.0 with 3.0. The running total becomes 7.0.
- 5Return the value
The traversal has ended, so the running total 7.0 is the value the call returns.
The call returns 7.0, which matches the hand sum.
Replacing Addition with Another Operation
The name generalized comes from the fact that you can change the operation while keeping the same traversal. The next example multiplies the elements instead of adding them. Two things change: the starting value becomes 1.0, because 1 is the neutral starting point for a product, and the operation is passed as the fourth argument. The operation here is std::multiplies, which is a function object from the functional header.
11.25- 1.0 is the neutral starting value for a product
- std::multiplies<double>() is the operation passed as the fourth argument
Where Results Go Wrong
Because every element passes through one running value, a wrong result can be traced to a specific place in the chain. When the output differs from what you expected, check three stages in order: the starting value, the range given by begin and end, and the operation. Each is a separate place where the calculation can diverge. The first-visit trace below shows a case where the starting value is the problem.
The running value has the type of the starting value. When the starting value is the int 0, each intermediate sum is stored back as an int, so the fractional part is discarded at the first step. The first element, 1.5, becomes 1, and the second step adds 2.5 to that 1 rather than to 1.5. The truncation then carries forward, and the final result is 6 instead of 7.0. The fault is in the starting value, not in the sequence, which is exactly why checking the starting value comes first.
Common mistake Using an int starting value when the elements are doubles
What it looks likestd::accumulate(values.begin(), values.end(), 0) on the values 1.5, 2.5, and 3.0Why it failsThe running total is an int, so each intermediate sum loses its fractional part.
Do this insteadStart with 0.0, a double, so the running total keeps its fractional part.
Common mistake Forgetting that the starting value sets the neutral point of the operation
What it looks likeUsing 0.0 as the starting value when multiplying the elements
Why it failsMultiplying by 0.0 at the start keeps the running total at zero, so the product is always zero.
Do this insteadUse 1.0 as the starting value for a product, because 1 is the neutral value for multiplication.
Common mistake Assuming the end argument is the last element
What it looks likePassing values.back() as the end positionWhy it failsThe end position is one past the last element, so the final element is skipped.
Do this insteadPass values.end() as the end position.
Complex Numbers and Scalar Types
The second topic in this section is complex numbers. The standard library supports a family of complex number types, all modeled on the same complex class. Complex is a template, which means one definition produces a whole family of types, each built around a different scalar type. The scalar is the type used to store the real and imaginary parts. You choose a complex type by choosing the scalar you give the template.
1 1 1- std::complex<float> stores its parts as float
- std::complex<double> stores its parts as double
- std::complex<long double> stores its parts as long double
| Scalar type | Role in complex | Precision relative to the others | When to consider it |
|---|---|---|---|
| float | Stores the real and imaginary parts as single-precision values | Lowest of the three | When memory is tight and the calculation tolerates limited precision |
| double | Stores the parts as double-precision values | Middle of the three | A common default when accuracy matters |
| long double | Stores the parts as extended-precision values | At least as precise as double | When a calculation depends on the most accuracy available |
The scalar types that the standard library complex template supports for floating-point parts
When a calculation depends on accuracy, check the scalar type first, just as you checked the starting value and the range in the accumulate example. Choosing between the complex types comes down to which scalar you give the template, and that choice decides the precision of the stored parts.
Practicing the Trace
A program calls std::accumulate on the vector {2.5, 2.5, 2.5} with the starting value 0 (an int). Trace the running total after each element and state the value returned. Then explain which of the three stages (starting value, range, operation) is responsible for any difference from the hand sum of 7.5.
Hints
- Write down the running total before the first element, then after each visit.
- Each intermediate sum is stored back in the type of the starting value.
- The expected hand sum is 7.5, so compare the returned value with it.
Change the call from the previous practice so that it multiplies the elements instead of adding them. Name the starting value you would use, explain why it is the neutral choice, and state which argument carries the operation.
Hints
- The neutral starting value for a product is the one that leaves the running value unchanged.
- The operation is the fourth argument to accumulate.
Key Takeaways
- accumulate combines a starting value with each element in turn, so the library handles the traversal and you describe the sequence, the starting value, and optionally the operation.
- The starting value sets the type of the running total; an int starting value with double elements truncates the fractional part at each step.
- A wrong result can be located at the starting value, the range given by begin and end, or the operation, and those stages should be checked in that order.
- complex is a template, so the scalar type you supply (float, double, or long double) decides the precision of the stored real and imaginary parts.