Implementation of Brent's Algorithm to find roots of a polynomial

I made a program that contains a root-finding algorithm for polynomials as a function and contains 3 test polynomials. The algorithm is Brent's method and is based entirely off the pseudocode from Wikipedia. Is there anything I should change to make the code faster/easier to understand/etc?

The code does run and prints correct results for all test cases I've tried.

I'm mostly interested in writing optimized code with the priority being faster runtime, less memory usage, and fewer redundant function calls respectively, but I'm also interested in picking up better coding practices.

```
/*****
*
* Grant Williams
*
* Version 1.0.0
* August 27, 2015
*
* Test Program for Brent's Method Function.
*
* Brent's method makes use of the bisection method, the secant method, and inverse quadratic interpolation in one algorithm.
*
* To Compile Please use icc -std=c++11 if using intel or g++ -std=c++11 if using GCC.
*
/

#include
#include
#include
#include
#include
//#include "brent_fun.h"

void brents_fun(std::function f, double lower_bound, double upper_bound, double TOL, double MAX_ITER);

int main()
{
//clock stuff
std::clock_t start;
double duration;
start = std::clock();
//stop clock stuff

double a; // lower bound
double b; // upper bound
double TOL = 0.0001; // tolerance
double MAX_ITER = 1000; // maximum number of iterations

int function; // set polynomial to find roots of & boundary conditions for that polynomial

std::cout f, double lower_bound, double upper_bound, double TOL, double MAX_ITER)
{
double a = lower_bound;
double b = upper_bound;
double fa = f(a); // calculated now to save function calls
double fb = f(b); // calculated now to save function calls
double fs = 0; // initialize

if (

Comments

OK I like the first comment.

/*******************************************************************************
*
* Grant Williams
*
* Version 1.0.0
* August 27, 2015
*
* Test Program for Brent's Method Function.
*
* Brent's method makes use of the bisection method, the secant method, and inverse quadratic interpolation in one algorithm.
*
* To Compile Please use icc -std=c++11 if using intel or g++ -std=c++11 if using GCC.
*
********************************************************************************/

You may want to add a copyright notice.

It is over my head the description but I assume somebody with some maths skills could understand it. So it provides some good information.

But there are a lot of other comments in this application are useless. Comments should be used judiciously within code. Bad comments are worse than no comments. You have to maintain comments in the same way you maintain the code and the compiler will not help you with the comments.

Your comments should not explain what the code is doing (the code should be easy to read and by self explanatory). You should explain WHY the code is doing something in a comment.

Example:

fs = f(s);  // calculate fs
    d = c;      // first time d is being used (wasnt used on first iteration because mflag was set)
    c = b;      // set c equal to upper bound
    fc = fb;    // set f(c) = f(b)

These comments are all should be removed. The code should also be fixed so that it makes the comments redundant.

fs = f(s);
    c  = upper_bound;
    fc = fb;

You'll notice that I even removed a line. That's because of after much clicking I found it was never used. What?!

double a;               // lower bound
    double b;               // upper bound
    double TOL = 0.0001;    // tolerance
    double MAX_ITER = 1000; // maximum number of iterations

Much easier to write if you use names that define what they mean.

double lowerBound;
    double upperBound;
    double tolerance     = 0.0001;
    double maxIterations = 1000;

Identifier Names

Using short identifier names is fine for maths. But when you write real applications that need to be maintained for decades you need people to understand your code. You can not rely on comments (because code changes over time and comments and code will drift apart). So you must use good names that explain their meaning for both variables and functions.

Single character names should be banned. A visual inspection of your code did not reveal any use of d. But I don't trust my eyes. So I had to search your code for occurrences using tools. There were so many false positives in the search because the single character d appears a lot in the middle of other words.

Pick names that are easy to see and spot and that provide meaning to the context that they are used in.

Reserved Words.

Certain styles of identifier are reserved for different Jobs. You should understand these reservations.

Identifiers that are all upper case are traditionally reserved for use by the pre-processor.

MAX_ITER

This will get clobbered by the pre-processors if you are unlucky. Pick names that use a combination of upper and lower case characters.

Note it is allso traditional to have type names (User Defined) start with an uppercase letter and all method/variable names start with a lower case letter.

Whether you prefer camel-casing your words or using _ between words is still a very divided subject. The _ is the minority group (but it is a big minority). I am in the group of camel-casing because using _ is error prone and hard to spot when you get it wrong.

Declare and initialize in one statement.

std::clock_t start;
    start = std::clock();

    // It is best to initialize your variables on declaration.
    // It makes sure that value are always defined.

    std::clock_t start = std::clock();

Also don't declare variables until you need them. Its not much of a problem with POD types that don't run code. But objects that have a type and therefore a constructor will run the constructor at declaration.

Also for readability you want the variable declared just before use so that you can see they type of variable easily and not have to go searching to the top of the function just to find the type.

Prefer '\n' to std::endl

The std::endl places a '\n' on the stream then flushes the stream. Manually flushing the stream is usually a bad idea. The code will flush it for you at the best times. You should only manually flush the streams if there is something critical that needs to happen that the code does not understand directly (like the application could be crashing and will not flush the stream).

If you flush streams manually you are likely to find your IO very inefficient.

Declare loop variables so they are scoped correctly.

``
for (function = 1; function <= 3; function++)

// More usual to see this:
for (int function = 0; function < 3; ++function)
`

StackExchange Code Review Q#103762, answer score: 8