Capstone 1: the model of a numerical solver
A solver for one equation is twenty lines. A solver that is worth keeping is a model, two methods and a report, and the model has to be designed before either method is written, because it decides what a method receives and what it returns. This capstone builds a small root finder in three lessons: the equation as a value here, bisection and Newton over it next, and a formatted report at the end. Nothing is timed, nothing is large, and every line is the kind of code a numerical project writes on its first day.
The equation as a value
The model is a derived type with four things in it: a name, the function itself as a procedure pointer, the interval to search and the tolerance the caller wants. A method then takes one argument of this type and returns a result, instead of taking a function and four numbers and returning three values through dummy arguments.
The type uses real64 throughout, because a root finder that stops at a tolerance of 1.0e-8 has no reason to compute in single precision, as lesson 119 showed. The kind is imported once in the module and given the shorter name dp.
The file model.f90, the module and a program that exercises it:
module solver_model
use, intrinsic :: iso_fortran_env, only: dp => real64
implicit none
private
public :: equation, eval, bracket_ok, describe, cubic, decay
abstract interface
pure function func(x) result(y)
import :: dp
real(dp), intent(in) :: x
real(dp) :: y
end function func
end interface
type :: equation
character(len=32) :: name = ''
procedure(func), pointer, nopass :: f => null()
real(dp) :: a = 0.0_dp
real(dp) :: b = 0.0_dp
real(dp) :: tol = 1.0e-8_dp
end type equation
contains
pure function eval(eq, x) result(y)
type(equation), intent(in) :: eq
real(dp), intent(in) :: x
real(dp) :: y
y = eq%f(x)
end function eval
function bracket_ok(eq) result(ok)
type(equation), intent(in) :: eq
logical :: ok
ok = eval(eq, eq%a) * eval(eq, eq%b) < 0.0_dp
end function bracket_ok
subroutine describe(eq)
type(equation), intent(in) :: eq
print '(a,a)', 'equation: ', trim(eq%name)
print '(a,f10.6,a,f10.6,a)', 'bracket: [', eq%a, ', ', eq%b, ']'
print '(a,es10.2)', 'tolerance:', eq%tol
print '(a,es12.4,a,es12.4)', 'f(a) = ', eval(eq, eq%a), ' f(b) = ', eval(eq, eq%b)
if (bracket_ok(eq)) then
print '(a)', 'the bracket changes sign: a root is inside'
else
print '(a)', 'the bracket does not change sign'
end if
end subroutine describe
pure function cubic(x) result(y)
real(dp), intent(in) :: x
real(dp) :: y
y = x**3 - 2.0_dp * x - 5.0_dp
end function cubic
pure function decay(x) result(y)
real(dp), intent(in) :: x
real(dp) :: y
y = exp(-x) - 0.5_dp
end function decay
end module solver_model
program model_demo
use solver_model
use, intrinsic :: iso_fortran_env, only: dp => real64
implicit none
type(equation) :: eq
eq%name = 'x**3 - 2x - 5'
eq%f => cubic
eq%a = 2.0_dp
eq%b = 3.0_dp
eq%tol = 1.0e-8_dp
call describe(eq)
eq%name = 'exp(-x) - 0.5'
eq%f => decay
eq%a = 0.0_dp
eq%b = 1.0_dp
print *
call describe(eq)
end program model_demo
The two functions are module procedures rather than internal ones. That is not a style choice: an internal procedure passed as a procedure pointer makes gfortran generate a trampoline and a warning about an executable stack, as lesson 070 shows, and a module procedure has a plain interface.
The abstract interface
ABSTRACT INTERFACE names the shape of the function the type will hold: a PURE function of one real64 that returns a real64. IMPORT :: dp is what makes the kind visible inside the interface block, which is otherwise a scope of its own. Any function with that shape can be assigned to eq%f, and the compiler checks the assignment.
NOPASS says that the procedure does not take the type as its first argument, which is right for a mathematical function: cubic(x) knows nothing about the equation that holds it. A type-bound procedure that works on the equation would use PASS, the default, and lesson 073 is the tour.
F => NULL() gives the pointer a defined initial state, so a call through an unassigned eq%f fails at the call instead of jumping to an address left in memory. The design rule behind it is the one from lesson 083: a pointer that starts null and is tested before use, or a program that does not need a debugger.
Describing an equation
EVAL is the only place that calls the function pointer, so a later change, such as caching values or counting calls, has one place to go. BRACKET_OK is the precondition of every bracketing method: the product of the values at the two ends must be negative, which means the continuous function takes both signs and therefore has a zero somewhere between them.
The check multiplies the two values and compares the product with zero. The alternative, sign(1.0_dp, f(a)) /= sign(1.0_dp, f(b)), avoids the product, which can overflow when both values are large. For a capstone it is worth knowing both; the multiplication is what most textbooks print, and the sign comparison is what a library would write.
The run
gfortran -Wall -Wextra -std=f2018 model.f90 -o model
./model
equation: x**3 - 2x - 5
bracket: [ 2.000000, 3.000000]
tolerance: 1.00E-08
f(a) = -1.0000E+00 f(b) = 1.6000E+01
the bracket changes sign: a root is inside
equation: exp(-x) - 0.5
bracket: [ 0.000000, 1.000000]
tolerance: 1.00E-08
f(a) = 5.0000E-01 f(b) = -1.3212E-01
the bracket changes sign: a root is inside
Both equations pass the check, and the numbers are the ones a reader can verify by hand: the cubic is 8 - 4 - 5 = -1 at two and 27 - 6 - 5 = 16 at three, and exp(0) - 0.5 is a half while exp(-1) - 0.5 is negative.
What the methods need
The model is enough for a method to start. Bisection needs the two ends and a tolerance and can ignore everything else. Newton needs one point and a derivative, and this capstone does not store a derivative: the next lesson takes a numerical one from two values of the function, which costs one extra evaluation per step and needs no change to the type. A method that wants to report its history needs somewhere to put it, and that is the second type of the capstone.
The interface a method will have is therefore subroutine solve(eq, result), with the equation as input and one derived type as output. It is the same shape for both methods, which is what makes the report of lesson 128 a loop over a table.
Exercises
- Add a third equation with no root in its bracket, and call describe on it. Which line of the output changes?
- Make describe print the width of the bracket and the number of roots it promises. What does the width have to do with the number of bisection steps?
- Give the type a component n_evals and count the evaluations in eval. What has to change for a function that is PURE?
- Write bracket_ok with the sign comparison instead of the product. Does the output of this page change?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does the equation type hold?
Answer
A name, a procedure pointer to the function, the bracket and the tolerance
A method takes one argument instead of six.
-
What does
IMPORT :: dpdo in the abstract interface?Answer
Makes the kind of the enclosing module visible in the interface block
An interface block is a scope of its own.
-
What does NOPASS mean?
Answer
The procedure does not take the type as its first argument
A mathematical function knows nothing of the equation.
-
Why are the functions module procedures?
Answer
An internal procedure passed as a pointer needs a trampoline and a warning
The build would warn about an executable stack.
-
What does
f => null()give?Answer
A defined starting state, so an unassigned call fails at the call
A null pointer is testable.
-
What is the bracket condition for a root?
Answer
f(a) and f(b) have opposite signs
A continuous function changes sign at a zero.
-
Why is the sign comparison better than the product?
Answer
The product can overflow when both values are large
Both are shown; the library would use signs.
-
What is the value of the cubic at x = 3?
Answer
16
27 - 6 - 5.
-
What does the model lack for Newton?
Answer
A derivative, which the next lesson takes numerically
One extra evaluation per step instead of a new component.
-
Which result does a method return?
Answer
One derived type with the root, the steps and a flag
The same shape for both methods.
The programs on this page were built with GNU Fortran (Alpine 15.2.0) 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev