The previous mathematical development leads to a very simple sequential algorithm implemented in *c++*. A version of the program is shown below and a discussion of that implementation follows. An analysis of the runtime requirements of the implementation is also presented.

Below is a basic *c++* program that implements function integration using the trapezoidal rule. This implementation consists of three functions, *trapezoid()*, *myfunction()* and *main()*. In the next several paragraphs, these three functions will be briefly discussed from a syntactic point of view.

The signature of function *trapezoid()*, line 6, consists of four arguments, all passed by value: the first two define the interval [a,b], the third specifies the number of subdivisions used of the interval [a,b], and the fourth is a pointer to a function whose signature is float f(float x). In the function definition of *trapezoid()*, on line 16 the (argument) function *f()* is called with its argument. Please note that the *c++* specification for calling the argument function (*f)() is f().

The function *myfunction()*, line 30, is the user defined function that will be integrated over \([a,b]\), note that the signatures of *myfunction()* and the *trapezoid()* function parameter *f()*, line 6, are identical.

The function *main()*, line 38, is a straightforward illustration of a call to the function *trapezoid()* with *myfunction()*, notice the actual fourth argument of the call of *trapezoid()* on line 42 is *&myfunction*, the address of *myfunction()*, which is passed to the function pointer argument.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | ```
#include <cmath>
#include <iostream>
using namespace std;
// Function to implement integration of f(x) over the interval
// [a,b] using the trapezoid rule with nsub subdivisions.
float trapezoid(float a, float b, int nsub, float (*f)(float) )
{
// initialize the partial sum to be f(a)+f(b) and
// deltaX to be the step size using nsub subdivisions
float psum = f(a)+f(b);
float deltaX = (b-a)/nsub;
// increment the partial sum
for(int index=1;index<nsub;index++)
{
psum = psum + 2.0*f(a+index*deltaX);
}
// multiply the sum by the constant deltaX/2.0
psum = (deltaX/2.0)*psum;
// return approximation
return psum;
}
// Function definition, must be defined over [a,b]
float myfunction(float x)
{
return x*x-2*x+1;
}
// Simple main program to call and test
int main()
{
// Integral of myfunction(x0 over [1.0,2.0]
cout << trapezoid(1.0,2.0,100000,&myfunction) << endl;
return 0;
}
``` |

The function *trapezoid()*, lines 6-26, is the implementation of the trapezoidal rule previously mathematically developed. The variable used to accumulate the partial sum, *psum*, is initialized to *f(a)+f(b)*, and the variable *deltaX* is appropriately initialized. The *for* loop, lines 14-17, accumulate the sums given by the middle terms in the mathematical summation. On line 20, the sum is multiplied by the constant.

In terms of time complexity, this function must compute the sum of the terms and there are *n* of these, so the overall computation complexity is \(\Theta(n) * \left[\mbox{complexity of $f()$}\right]\). In the program above, the complexity of *myfunction()* is constant; hence, the overall computational complexity of is linear, \(\Theta(n)\).

There are only three variables in *trapezoid()*, *psum*, *deltaX* and *index*. Hence the space required for the computation is constant, \(\Theta(1)\).

- Copy the program, compile and run it. Modify
*main*to print the execution time taken to compute the integral. - Make a chart of these times for 10 significantly different values of
*n*. Does this chart agree with the time complexity analysis given above? Justify you answer. - Add another function to be integrated and the interval. Make appropriate modifications to the program. Repeat the previous question.
- How can this program be used to approximate the
*area under the curve*? - Use this C++ program to approximate the
*area under the curve*for a different function. - What can you say about the
*space*complexity of this implementation?

[Deitel] | Deitel & Deitel, C++: How to Program. |