BISECTION_INTEGER
Seek Integer Roots for F(X)=0

BISECTION_INTEGER is a C++ library which seeks an integer solution to the equation F(X)=0, using bisection within a user-supplied change of sign interval [A,B].

A function F(X) confined to integer arguments is given, with an interval [A,B] over which F changes sign. An integer C is sought such that A ≤ C ≤ B and F(C) = 0.

Because we are restricted to integer arguments, it may the case that there is no such C.

This routine proceeds by a form of bisection, in which the enclosing interval is restricted to be defined by integer values.

If the user has given a true change of sign interval [A,B], and if, in the interval, there is a single integer value C for which F(C) = 0, with the additional restrictions that F(C-1) and F(C+1) are of opposite signs, then this procedure should locate and return C.

In particular, if the function F is monotone, and there is an integer solution C in the interval, then this procedure will find it.

However, in general, even if there is an integer C in the interval, such that F(C) = 0, this procedure may be unable to find it, particularly if there are also nonintegral solutions within the same interval.

While any integer function can be used with this program, the bisection approach is most useful if the integer function is monotone, or varies slowly, or can be regarded as the restriction to integer arguments of a continuous (and smoothly varying) function of a real argument. In such cases, knowing that F is negative at A and positive at B suggests that F generally increases from A to B, and might attain the value 0 at some intermediate argument C.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

BISECTION_INTEGER is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

BISECTION_RC, a C++ library which seeks a solution to the equation F(X)=0 using bisection within a user-supplied change of sign interval [A,B]. The procedure is written using reverse communication.

BRENT, a C++ library which contains Richard Brent's routines for finding the zero, local minimizer, or global minimizer of a scalar function of a scalar argument, without the use of derivative information.

TEST_ZERO, a C++ library which defines functions which can be used to test zero finders.

Source Code:

• bisection_integer.cpp, the source code.
• bisection_integer.hpp, the include file.
• bisection_integer.sh, BASH commands to compile the source code.

Examples and Tests:

• bisection_integer_prb.cpp, a sample calling program.
• bisection_integer_prb.sh, BASH commands to compile and run the sample program.
• bisection_integer_prb_output.txt, the output file.

List of Routines:

• BISECTION_INTEGER seeks an integer root using bisection.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C++ source codes.