bisection_integer, a C code 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.
The computer code and data files described and made available on this web page are distributed under the MIT license
bisection_integer is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.
bisection_rc, a C code 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.
test_zero, a C code which defines functions which can be used to test zero finders.