Programs: 
BISECT, 1BISECT 

Version: 
3.0, 5 May 2002 

Description: 
This programs finds a real zero (root) of a realvalued function through repeatedly halving an interval in which a zero is known to be located. One program is callable from any program; the other is a main program which may be used by a calculator user. 

Compatibility: 


Other programs 
A zero of a function f is a value x at which f(x)=0.
Suppose a function f is continuous, and its sign at a point x_{1} differs from its sign at a point x_{2}. Then somewhere between x_{1} and x_{2} is at least one point where the value of f is zero: the interval [x_{1}, x_{2}] contains a zero of the function f. One method of finding such a zero is the bisection method. This method is to check a point x_{3} half way between x_{1} and x_{2}. If the sign of the function at x_{3} is the same as at x_{1}, then replace the interval endpoint x_{1} with x_{3}; if the sign of the function at x_{3} is the same as at x_{2}, then replace the interval endpoint x_{2} with x_{3}. The method continues bisecting the interval until a true zero is found, or until the interval [x_{n}, x_{m}] is small enough.
The program 1BISECT goes through this process for a function f programmed in program F0. It continued bisecting the original interval until a true zero is found, or until the midpoint computed is the same as one of the endpoints through roundoff error. The program BISECT is a user interface wrapper around 1BISECT so the initial endpoints can be input from the keyboard.
Most program collections — including this one — have a Newton’s method zero finder. Newton’s method requires a differentiable function. The bisection method used here requires only a continuous function.
Under the best of circumstances, Newton’s method has quadratic convergence, but can have substantially slower convergence — or even fail to converge at all — in less than the best of circumstances. The bisection method always has linear convergence.
Load the programs BISECT, 1BISECT, VRPRE, VRSAVFJ, VRSAVKO, VRRESFJ, and VRRESKO.
Program the function f into the program F0. The program F0 must take its argument from the variable A, and leave its result in the variable B. It must not change any variable other than variable B. (The variable save/restore routines may be used if the program requires work variables.)
Run the program BISECT. BISECT displays the prompts:
Min? Max?
Enter a value x_{1} and a value x_{2} such that f(x_{1}) has sign opposite from f(x_{2}). If the sign of f is the same at x_{1} and x_{2}, BISECT displays the message:
No sign change
Otherwise, BISECT finds a zero of f and reports it with the label
Zero at
The programs are available as a text file with .CAT contents, or may be entered as shown below. A semicolon (“;”) marks the beginning of a comment, and is not to be entered into the calculator. Remember that these programs are copyrighted; see the copyright issues page for limitations on redistribution.
Program BISECT (189 bytes):
; Program BISECT ; ; Description: ; Calls 1BISECT to find a zero of a continuous function ; ; Variables: ; AE are used for subroutine communication ; F is the lower endpoint ; G is the upper endpoint ; H is the F0 value at the lower endpoint ; I is the F0 value at the upper endpoint ; J is the product of the signs of H and I ; ; Calling sequence: ; None; main program ; ; Implicit inputs: ; None. ; ; Implicit outputs: ; List 6: the variable save stack. ; Z: the stack pointer for the variable save stack. ; ; Side effects: ; None. ; ; Symbols used: ; > is assignment arrow ; => is conditional jump ; () is unary negation ; _ is display triangle Prog "VRPRE" ; Set up variable save stack Lbl 0 ; Infinite loop asking for endpoints "Min"?>F ; Get lower endpoint "Max"?>G ; Get upper endpoint F>A ; Get the function Prog "F0" ; value at the B>H ; lower endpoint F>A ; Prepare for possible early termination H=0=>Goto 3 ; If a true zero found, report it G>A ; Get the function Prog "F0" ; value at the B>I ; upper endpoint G>A ; Prepare for possible early termination I=0=>Goto 3 ; If a true zero found, report it 1>J ; Initialize sign product H<0=>()J>J ; If f(lower)<0, reverse sign product I<0=>()J>J ; If f(upper)<0, reverse sign product J<0=>Goto 2 ; Ensure signs at endpoints differ "No sign change" ; If not, report that Goto 0 ; and get other endpoints Lbl 2 ; [End of signs at endpoints differ] F>A ; Pass the upper endpoint G>B ; and the lower endpoint Prog "1BISECT" ; to 1BISECT C>A ; Retrieve the zero found Lbl 3 ; Report a zero "Zero at" ; Label the zero A_ ; Report it Goto 0 ; [End of infinite loop]
Program 1BISECT (219 bytes):
; Program 1BISECT ; ; Description: ; Find a zero of a continuous function through bisection ; ; Variables: ; A is the lower endpoint of the interval [input] ; B is the upper endpoint of the interval [input] ; C is the zero found [output] ; DE are unused ; F is the lower endpoint ; G is the upper endpoint ; H is the F0 value at the lower endpoint ; I is the F0 value at the upper endpoint ; J is the midpoint ; K is the F0 value at the midpoint ; L is the product of the signs of H and K ; M is the saved value of A ; N is the saved value of B ; ; Calling sequence: ; {lower endpoint}>A ; {upper endpoint}>B ; Prog "1BISECT" ; C>{zero} ; ; Implicit inputs: ; List 6: the variable save stack. ; Z: the stack pointer for the variable save stack. ; ; Implicit outputs: ; List 6: the variable save stack. ; Z: the stack pointer for the variable save stack. ; ; Side effects: ; None. ; ; Symbols used: ; > is assignment arrow ; / is the division operator ; => is conditional jump ; () is unary negation Prog "VRSAVFJ" ; Save variables Prog "VRSAVKO" ; F through O A>M ; Save arguments B>N ; into M and N A>F ; Get lower endpoint into F B>G ; Get upper endpoint into G Prog "F0" ; Call f with lower endpoint B>H ; Put f(lower) into H G>A ; Get upper endpoint Prog "F0" ; Call f with upper endpoint B>I ; Put f(upper) into I Lbl 0 ; Bisection loop F+(GF)/2>J ; Get midpoint into J J=F=>Goto 2 ; If the midpoint is an endpoint, due to round J=G=>Goto 2 ; off, we are done J>A ; Get midpoint Prog "F0" ; Call f with midpoint B>K ; Put f(midpoint) into K K=0=>Goto 2 ; If it is a true zero, we are done 1>L ; Get product of signs H<0=>()L>L ; of f(lower) and f(midpoint) K<0=>()L>L ; into L L<0=>Goto 1 ; If sign change in lower half, go to 1 J>F ; Replace the lower endpoint with K>H ; the midpoint; f() too Goto 0 ; Repeat the bisection Lbl 1 ; J>G ; Replace the upper endpoint with K>I ; the midpoint; f() too Goto 0 ; Repeat the bisection Lbl 2 ; [End of bisection loop] J>C ; Place result into C N>B ; Restore arguments into M>A ; A and B Prog "VRRESKO" ; Restore variables Prog "VRRESFJ" ; F through O
Sample program F0 (25 bytes):
; Program F0 ; ; Description: ; ***SAMPLE*** ; Function encoding a function for which a zero is to be found. The ; function is ln(x)  1, which has a zero at e, Euler's number. A ; reasonable range in which the zero might be sought is [1,3]. ; ; Variables: ; A is the x value at which the function is to be evaluated [input] ; B is the function value for the x value given in A [output] ; ; Calling sequence: ; {x value}>A ; Prog "F0" ; B>{function value} ; ; Implicit inputs: ; List 6: the variable save stack. ; Z: the stack pointer for the variable save stack. ; [These are available for functions that need them.] ; ; Implicit outputs: ; List 6: the variable save stack. ; Z: the stack pointer for the variable save stack. ; [These are available for functions that need them.] ; ; Side effects: ; None. ; ; Symbols used: ; > is assignment arrow (ln A)1>B
[ Previous page  Top of page  Next page ]
Copyright © 2001 Brian Hetrick
Page last updated 5 May 2002.