BISECTION_INTEGER Seek Integer Roots for F(X)=0

BISECTION_INTEGER is a MATLAB 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.

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 MATLAB 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 MATLAB 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 MATLAB library which defines functions which can be used to test zero finders.

Source Code:

• bisection_integer.m, uses bisection to search for the root of a function with an integer argument.
• timestamp.m, returns the YMDHMS date as a timestamp.

Examples and Tests:

You can go up one level to the MATLAB source codes.

Last revised on 21 August 2012.