Sequential Algorithm

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.

C++ Version

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;
}

Key algorithmic features

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.

Complexity

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)\).

Questions

  1. Copy the program, compile and run it. Modify main to print the execution time taken to compute the integral.
  2. 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.
  3. Add another function to be integrated and the interval. Make appropriate modifications to the program. Repeat the previous question.
  4. How can this program be used to approximate the area under the curve?
  5. Use this C++ program to approximate the area under the curve for a different function.
  6. What can you say about the space complexity of this implementation?

References

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

Table Of Contents

Previous topic

Evaluating a definite integral

Next topic

Distributed parallel algorithm

This Page