What is FiboSearch?

FiboSearch is a C++ implementation of the Fibonacci Search, an integer analog of the Golden Section search. Given a function of non-negative integers (specifically, the set {0, 1, 2, ..., n}) that returns a real number, and has a single minimum and no local minima, FiboSearch will efficiently locate that minimum in log (n) time. More specifically, if n > 3, the function will be evaluated Fn times, where Fn is the smallest Fibonacci number greater than or equal to n.

Why FiboSearch?

The implementations of the Fibonacci search I could identify would all locate the minimum element in an array, but not the minimum of a function of an integer. I am doing research that involves locating the minimum of a function of an integer; no array was available, and populating it would obviate the need for the search (evaluation of the function would stop after noting the first increase in the function's value) and be less efficient, because many unnecessary function evaluations would be used.

How to use FiboSearch

FiboSearch has two required arguments: a function or a function object of an unsigned integer, and the upper bound of the search region. (The lower bound is zero.) It returns a structure that contains the location of the minimum, the function's value at the minimum, and the number of times the function was evaluated. An example call is:

FiboResult result = FiboSearch (fcn, 42);

The output stream insertion operator "<<" is overloaded to allow the result to be printed easily. Continuing the example above, the code

std::cout << result << std::endl;

will cause output similar to the following:

                 Location of Minimum, x: 9
                    Value at Minimum, f: 2.1
Number of Function evaluations, n_feval: 10

The function prototype for this example is:

double fcn (unsigned int);

Were a function object used, its function prototype would be:

double fcn::operator() (unsigned int);

How to use FiboSearch with functions having additional arguments:

FiboSearch is implemented as a variadic template, allowing you to easily use functions that have additional arguments, such as data, parameters, etc., as shown in the source file FiboSearchDemoUsingFunction.cc. Suppose your objective function had, in addition to its unsigned integer argument (the value at which to evaluate the function) a parameter of type double, and data of type std::vector<double>. You then have a function with prototype:

double fcn2 (unsigned int, double, std::vector<double> &);

(Note that the unsigned int argument, the value for which the function is to be evaluated, must come first! You should use a reference for the vector to avoid a copy being made for every function evaluation.)

your call to FiboSearch would look like (assuming the search was to be from 0 to 77, and dbl_vec was an STL vector of doubles):

FiboResult result2 = FiboSearch (77, 14.4, dbl_vec);

The arguments that come after the mandatory unsigned int are referred to as the "parameter pack."

You may wish to apply the const qualifier to each mutable parameter, thus:

double fcn2 (unsigned int, double, const std::vector<double> &);

(You can also use the parameter pack approach when passing FiboSearch a function object, but, because function objects can contain their own data, it shouldn't be necessary.)

The FiboResult structure

FiboSearch.hh defines FiboResult, a structure used to pass results back to the caller. It contains three attributes:

• x (unsigned int): Location of the minimum
• f (double): Value of the function at the minimum
• n_feval (int): Number of function evaluations

For convenience, the output stream's insertion operator "<<" is overloaded to allow near-effortless printout of the search results. If you use this, the attribute names will be printed as part of the output, right after their description, as in the following example:

FiboResult result = FiboSearch (fcn, 77);
std::cout << result << std::endl;

will result in output similar to the following:

                 Location of Minimum, x: 9
                    Value at Minimum, f: 2.1
Number of Function evaluations, n_feval: 10

How to build FiboSearch

I built the FiboSearch object file and the two executable demo files using the following commands in GNU/Linux:

g++ -c FiboSearch.cc
g++ FiboSearchDemoUsingFunction.cc FiboSearch.o -o FiboSearchDemoUsingFunction
g++ FiboSearchDemoUsingFunctionObject.cc FiboSearch.o -o FiboSearchDemoUsingFunctionObject

When you build your application, be sure to include the FiboSearch header file, FiboSearch.hh, in file that calls FiboSearch (and any files that send a FiboResult object to an output stream), and link your application against the FiboSearch object file, FiboSearch.o.

Other potentially useful information

Some constants and a utility function are defined under the namespace FiboSearch. You can see them in the source files FiboSearch.hh and FiboSearch.cc if you're interested.

Limitations

The upper bound of the search region is the largest Fibonacci number that can be stored in an unsigned int in GNU g++ 4.9.3 (2'971'215'073, not quite 3 billion) or whatever the largest Fibonacci number you can fit into an unsigned int on your build platform, whichever is smaller. If this turns out to be a serious limitation for enough users, I'll consider making a version using unsigned long, which would impose a much larger limit on most platforms.

The lower bound of the search region must be zero. If you want it to start somewhere else, just introduce a shift of the argument in your function.

---

Author

J A Stephen Viggiano, PhD
Acolyte Color Research

License

FiboSearch is licensed under the GNU Public License, version 3.