Previous page Next page Navigation bar

Programs

Mathematics Programs

Zeroes Through Bisection

Summary

Programs:

BISECT, 1BISECT

Version:

3.0, 5 May 2002

Description:

This programs finds a real zero (root) of a real-valued 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:

Is compatible CFX-9850G

Compatible with CFX-9850G

Is compatible FX-7400G

Compatible with FX-7400G

Other programs
required:

VRPRE, VRSAVFJ, VRSAVKO, VRRESFJ, VRRESKO

Detailed Description

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 x1 differs from its sign at a point x2. Then somewhere between x1 and x2 is at least one point where the value of f is zero: the interval [x1, x2] 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 x3 half way between x1 and x2. If the sign of the function at x3 is the same as at x1, then replace the interval endpoint x1 with x3; if the sign of the function at x3 is the same as at x2, then replace the interval endpoint x2 with x3. The method continues bisecting the interval until a true zero is found, or until the interval [xn, xm] 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.

Other Programs

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.

Usage

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 x1 and a value x2 such that f(x1) has sign opposite from f(x2). If the sign of f is the same at x1 and x2, BISECT displays the message:

No sign change

Otherwise, BISECT finds a zero of f and reports it with the label

Zero at

Program Source

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:
;   A-E 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]
;   D-E 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+(G-F)/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 ]

Previous page Top of page Next page Navigation bar

Copyright © 2001 Brian Hetrick
Page last updated 5 May 2002.

Brian’s Casio Calculator Corner

Home

Programs

Index

Linkage Conventions

Mathematics

Index

Factorization

Bisection

Newton’s Method

Complex Zeroes

Best Fraction Approximation

Pseudorandom Numbers

Romberg Integration

First Degree ODE

Rounding

Permutations

Finance

Physics

Utility

Tutorial

Puzzles

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data