Regula falsi

History

The simple false position technique is found in cuneiform tablets from ancient Babylonian mathematics, and in papyri from ancient Egyptian mathematics.

Double false position arose in late antiquity as a purely arithmetical algorithm. In the ancient Chinese mathematical text called The Nine Chapters on the Mathematical Art (九章算術), dated from 200 BC to AD 100, most of Chapter 7 was devoted to the algorithm. There, the procedure was justified by concrete arithmetical arguments, then applied creatively to a wide variety of story problems, including one involving what we would call secant lines on a conic section. A more typical example is this "joint purchase" problem involving an "excess and deficit" condition:

Now an item is purchased jointly; everyone contributes 8 [coins], the excess is 3; everyone contributes 7, the deficit is 4. Tell: The number of people, the item price, what is each? Answer: 7 people, item price 53.

Between the 9th and 10th centuries, the Egyptian mathematician Abu Kamil wrote a now-lost treatise on the use of double false position, known as the Book of the Two Errors (Kitāb al-khaṭāʾayn). The oldest surviving writing on double false position from the Middle East is that of Qusta ibn Luqa (10th century), an Arab mathematician from Baalbek, Lebanon. He justified the technique by a formal, Euclidean-style geometric proof. Within the tradition of medieval Muslim mathematics, double false position was known as hisāb al-khaṭāʾayn ("reckoning by two errors"). It was used for centuries to solve practical problems such as commercial and juridical questions (estate partitions according to rules of Quranic inheritance), as well as purely recreational problems. The algorithm was often memorized with the aid of mnemonics, such as a verse attributed to Ibn al-Yasamin and balance-scale diagrams explained by al-Hassar and Ibn al-Banna, all three being mathematicians of Moroccan origin.

Leonardo of Pisa (Fibonacci) devoted Chapter 13 of his book Liber Abaci (AD 1202) to explaining and demonstrating the uses of double false position, terming the method regulis elchatayn after the al-khaṭāʾayn method that he had learned from Arab sources. In 1494, Pacioli used the term el cataym in his book Summa de arithmetica, probably taking the term from Fibonacci. Other European writers would follow Pacioli and sometimes provided a translation into Latin or the vernacular. For instance, Tartaglia translates the Latinized version of Pacioli's term into the vernacular "false positions" in 1556. Pacioli's term nearly disappeared in the 16th century European works and the technique went by various names such as "Rule of False", "Rule of Position" and "Rule of False Position". Regula Falsi appears as the Latinized version of Rule of False as early as 1690.

Several 16th-century European authors felt the need to apologize for the name of the method in a science that seeks to find the truth. For instance, in 1568 Humphrey Baker says:

The Rule of falsehoode is so named not for that it teacheth anye deceyte or falsehoode, but that by fayned numbers taken at all aduentures, it teacheth to finde out the true number that is demaunded, and this of all the vulgar Rules which are in practise) is y^e most excellence.

Numerical analysis

The method of false position provides an exact solution for linear functions, but more direct algebraic techniques have supplanted its use for these functions. However, in numerical analysis, double false position became a root-finding algorithm used in iterative numerical approximation techniques.

Many equations, including most of the more complicated ones, can be solved only by iterative numerical approximation. This consists of trial and error, in which various values of the unknown quantity are tried. That trial-and-error may be guided by calculating, at each step of the procedure, a new estimate for the solution. There are many ways to arrive at a calculated-estimate and regula falsi provides one of these.

Given an equation, move all of its terms to one side so that it has the form, f (x) = 0, where f is some function of the unknown variable x. A value c that satisfies this equation, that is, f (c) = 0, is called a root or zero of the function f and is a solution of the original equation. If f is a continuous function and there exist two points a₀ and b₀ such that f (a₀) and f (b₀) are of opposite signs, then, by the intermediate value theorem, the function f has a root in the interval (a₀, b₀).

There are many root-finding algorithms that can be used to obtain approximations to such a root. One of the most common is Newton's method, but it can fail to find a root under certain circumstances and it may be computationally costly since it requires a computation of the function's derivative. Other methods are needed and one general class of methods are the two-point bracketing methods. These methods proceed by producing a sequence of shrinking intervals [a_k, b_k], at the kth step, such that (a_k, b_k) contains a root of f.

Two-point bracketing methods

These methods start with two x-values, initially found by trial-and-error, at which f (x) has opposite signs. Under the continuity assumption, a root of f is guaranteed to lie between these two values, that is to say, these values "bracket" the root. A point strictly between these two values is then selected and used to create a smaller interval that still brackets a root. If c is the point selected, then the smaller interval goes from c to the endpoint where f (x) has the sign opposite that of f (c). In the improbable case that f (c) = 0, a root has been found and the algorithm stops. Otherwise, the procedure is repeated as often as necessary to obtain an approximation to the root to any desired accuracy.

The point selected in any current interval can be thought of as an estimate of the solution. The different variations of this method involve different ways of calculating this solution estimate.

Preserving the bracketing and ensuring that the solution estimates lie in the interior of the bracketing intervals guarantees that the solution estimates will converge toward the solution, a guarantee not available with other root finding methods such as Newton's method or the secant method.

The simplest variation, called the bisection method, calculates the solution estimate as the midpoint of the bracketing interval. That is, if at step k, the current bracketing interval is [a_k, b_k], then the new solution estimate c_k is obtained by,

${\displaystyle c_k=\frac{a_k+b_k}{2}.}$

This ensures that c_k is between a_k and b_k, thereby guaranteeing convergence toward the solution.

Since the bracketing interval's length is halved at each step, the bisection method's error is, on average, halved with each iteration. Hence, every 3 iterations, the method gains approximately a factor of 2³, i.e. roughly a decimal place, in accuracy. This is commonly referred to as 1st-order convergence, meaning the number of digits of precision is proportional to the number of iterations used.

The regula falsi (false position) method

The convergence rate of the bisection method could possibly be improved by using a different solution estimate.

The regula falsi method calculates the new solution estimate as the x-intercept of the line segment joining the endpoints of the function on the current bracketing interval. Essentially, the root is being approximated by replacing the actual function by a line segment on the bracketing interval and then using the classical double false position formula on that line segment.

More precisely, suppose that in the k-th iteration the bracketing interval is (a_k, b_k). Construct the line through the points (a_k, f (a_k)) and (b_k, f (b_k)), as illustrated. This line is a secant or chord of the graph of the function f. In point-slope form, its equation is given by

${\displaystyle y-f(b_k)=\frac{f(b_k)-f(a_k)}{b_k-a_k}(x-b_k).}$

Now choose c_k to be the x-intercept of this line, that is, the value of x for which y = 0, and substitute these values to obtain

${\displaystyle f(b_k)+\frac{f(b_k)-f(a_k)}{b_k-a_k}(c_k-b_k)=0.}$

Solving this equation for c_k gives:

${\displaystyle c_k=b_k-f(b_k)\frac{b_k-a_k}{f(b_k)-f(a_k)}=\frac{a_{k}f(b_k)-b_{k}f(a_k)}{f(b_k)-f(a_k)}.}$

This last symmetrical form has a computational advantage when using floating-point arithmetic: As a solution is approached, a_k and b_k will be very close together, and nearly always of the same sign. Such a subtraction can lose precision through cancellation. Because f (b_k) and f (a_k) are always of opposite sign the “subtraction” in the numerator of the improved formula is effectively an addition (as is the subtraction in the denominator too).

At iteration number k, the number c_k is calculated as above and then, if f (a_k) and f (c_k) have the same sign, set a_{k + 1} = c_k and b_{k + 1} = b_k, otherwise set a_{k + 1} = a_k and b_{k + 1} = c_k. This process is repeated until the root is approximated sufficiently well. The above formula is also used in the secant method.

For nonlinear functions, once the interval of search shrinks far enough that the second derivative has constant sign throughout the interval, one endpoint of the search becomes fixed, while the other converges to the root. Thus, the best estimate of the solution is the last calculated value of ${\displaystyle c_k}$. However, because the interval stops shrinking, regula falsi can not match the bisection method's guarantee of precision. In some cases, rate of convergence can drop below that of the bisection method. Modified versions of regula falsi are generally to be preferred because they can fix these shortcomings at minimal cost.

Analysis

Since the initial end-points a₀ and b₀ are chosen such that f (a₀) and f (b₀) are of opposite signs, at each step, one of the end-points will get closer to a root of f. If the second derivative of f is of constant sign (so there is no inflection point) in the interval, then one endpoint (the one where f also has the same sign) will remain fixed for all subsequent iterations while the converging endpoint becomes updated. As a result, unlike the bisection method, the width of the bracket does not tend to zero (unless the zero is at an inflection point around which sign(f ) = −sign(f")). As a consequence, the linear approximation to f (x), which is used to pick the false position, does not improve as rapidly as possible.

One example of this phenomenon is the function

${\displaystyle f(x)=2x^3-4x^2+3x}$

on the initial bracket [−1,1]. The left end, −1, is never replaced (it does not change at first and after the first three iterations, f" is negative on the interval) and thus the width of the bracket never falls below 1. Hence, the right endpoint approaches 0 at a linear rate (the number of accurate digits grows linearly, with a rate of convergence of 2/3).

For discontinuous functions, this method can only be expected to find a point where the function changes sign (for example at x = 0 for 1/x or the sign function). In addition to sign changes, it is also possible for the method to converge to a point where the limit of the function is zero, even if the function is undefined (or has another value) at that point (for example at x = 0 for the function given by f (x) = abs(x) − x² when x ≠ 0 and by f (0) = 5, starting with the interval [-0.5, 3.0]). It is mathematically possible with discontinuous functions for the method to fail to converge to a zero limit or sign change, but this is not a problem in practice since it would require an infinite sequence of coincidences for both endpoints to get stuck converging to discontinuities where the sign does not change, for example at x = ±1 in

${\displaystyle f(x)=\frac{1}{(x-1{)}^2}+\frac{1}{(x+1{)}^2}.}$

The method of bisection avoids this hypothetical convergence problem.

Improvements in regula falsi

Though regula falsi always converges, usually considerably faster than bisection, there are situations that can slow its convergence – sometimes to a prohibitive degree. That problem isn't unique to regula falsi: Other than bisection, all of the numerical equation-solving methods can have a slow-convergence or no-convergence problem under some conditions. Sometimes, Newton's method and the secant method diverge instead of converging – and often do so under the same conditions that slow regula falsi's convergence.

But, though regula falsi is one of the best methods, and even in its original un-improved version would often be the best choice; for example, when Newton's isn't used because the derivative is prohibitively time-consuming to evaluate, or when Newton's and Successive-Substitutions have failed to converge.

Regula falsi's failure mode is easy to detect: The same end-point is retained twice in a row. The problem is easily remedied by picking instead a modified false position, chosen to avoid slowdowns due to those relatively unusual unfavorable situations. A number of such improvements to regula falsi have been proposed; two of them, the Illinois algorithm and the Anderson–Björk algorithm, are described below.

The Illinois algorithm

The Illinois algorithm halves the y-value of the retained end point in the next estimate computation when the new y-value (that is, f (c_k)) has the same sign as the previous one (f (c_{k − 1})), meaning that the end point of the previous step will be retained. Hence:

${\displaystyle c_k=\frac{\frac{1}{2}f(b_k)a_k-f(a_k)b_k}{\frac{1}{2}f(b_k)-f(a_k)}}$

or

${\displaystyle c_k=\frac{f(b_k)a_k-\frac{1}{2}f(a_k)b_k}{f(b_k)-\frac{1}{2}f(a_k)},}$

down-weighting one of the endpoint values to force the next c_k to occur on that side of the function. The factor ⁠1/2⁠ used above may look arbitrary, but it guarantees superlinear convergence (asymptotically, the algorithm will perform two regular steps after any modified step, and has order of convergence 1.442). There are other ways to pick the rescaling which give even better superlinear convergence rates.

The above adjustment to regula falsi is called the Illinois algorithm by some scholars. Ford (1995) summarizes and analyzes this and other similar superlinear variants of the method of false position.

Anderson–Björck algorithm

Suppose that in the k-th iteration the bracketing interval is [a_k, b_k] and that the functional value of the new calculated estimate c_k has the same sign as f (b_k). In this case, the new bracketing interval [a_{k + 1}, b_{k + 1}] = [a_k, c_k] and the left-hand endpoint has been retained. (So far, that's the same as ordinary Regula Falsi and the Illinois algorithm.)

But, whereas the Illinois algorithm would multiply f (a_k) by ⁠1/2⁠, Anderson–Björck algorithm multiplies it by m, where m has one of the two following values:

$${\displaystyle \begin{array}{cc}{m}^{\prime }& =1-\frac{f(c_k)}{f(b_k)},\\ m& =\{\begin{array}{ll}{m}^{\prime }& \text{if }{m}^{\prime }>0,\\ \frac{1}{2}& \text{otherwise.}\end{array}\end{array}}$$

For simple roots, Anderson–Björck performs very well in practice.

ITP method

Given ${\displaystyle {\kappa }_1\in (0,\mathrm{\infty }),{\kappa }_2\in \left[1,1+\varphi \right)}$, ${\displaystyle n_{1/2}\equiv \lceil (b_0-a_0)/2ϵ\rceil }$ and ${\displaystyle n_0\in [0,\mathrm{\infty })}$ where ${\displaystyle \varphi }$ is the golden ration ${\displaystyle \frac{1}{2}(1+\sqrt{5})}$, in each iteration ${\displaystyle j=0,1,\mathrm{2...}}$ the ITP method calculates the point ${\displaystyle x_{\text{ITP}}}$ following three steps:

1. [Interpolation Step] Calculate the bisection and the regula falsi points: ${\displaystyle x_{1/2}\equiv \frac{a+b}{2}}$ and ${\displaystyle x_f\equiv \frac{bf(a)-af(b)}{f(a)-f(b)}}$ ;
2. [Truncation Step] Perturb the estimator towards the center: ${\displaystyle x_t\equiv x_f+\sigma \delta }$ where ${\displaystyle \sigma \equiv \text{sign}(x_{1/2}-x_f)}$ and ${\displaystyle \delta \equiv min\{{\kappa }_1|b-a{|}^{{\kappa }_2},|x_{1/2}-x_f|\}}$ ;
3. [Projection Step] Project the estimator to minmax interval: ${\displaystyle x_{\text{ITP}}\equiv x_{1/2}-\sigma {\rho }_k}$ where ${\displaystyle {\rho }_k\equiv min\left\{ϵ2^{n_{1/2}+n_0-j}-\frac{b-a}{2},|x_t-x_{1/2}|\right\}}$.

The value of the function ${\displaystyle f(x_{\text{ITP}})}$ on this point is queried, and the interval is then reduced to bracket the root by keeping the sub-interval with function values of opposite sign on each end. This three step procedure guarantees that the minmax properties of the bisection method are enjoyed by the estimate as well as the superlinear convergence of the secant method. And, is observed to outperform both bisection and interpolation based methods under smooth and non-smooth functions.

Practical considerations

When solving one equation, or just a few, using a computer, the bisection method is an adequate choice. Although bisection isn't as fast as the other methods—when they're at their best and don't have a problem—bisection nevertheless is guaranteed to converge at a useful rate, roughly halving the error with each iteration – gaining roughly a decimal place of accuracy with every 3 iterations.

For manual calculation, by calculator, one tends to want to use faster methods, and they usually, but not always, converge faster than bisection. But a computer, even using bisection, will solve an equation, to the desired accuracy, so rapidly that there's no need to try to save time by using a less reliable method—and every method is less reliable than bisection.

An exception would be if the computer program had to solve equations very many times during its run. Then the time saved by the faster methods could be significant.

Then, a program could start with Newton's method, and, if Newton's isn't converging, switch to regula falsi, maybe in one of its improved versions, such as the Illinois or Anderson–Björck versions. Or, if even that isn't converging as well as bisection would, switch to bisection, which always converges at a useful, if not spectacular, rate.

When the change in y has become very small, and x is also changing very little, then Newton's method most likely will not run into trouble, and will converge. So, under those favorable conditions, one could switch to Newton's method if one wanted the error to be very small and wanted very fast convergence.

Example: Growth of a bulrush

In chapter 7 of The Nine Chapters, a root finding problem can be translated to modern language as follows:

Excess And Deficit Problem #11:

• A bulrush grew 3 units on its first day. At the end of each day, the plant is observed to have grown by ⁠ 1 /2⁠ of the previous day's growth.
• A club-rush grew 1 unit on its first day. At the end of each day, the plant has grown by 2 times as much as the previous day's growth.
• Find the time [in fractional days] that the club-rush becomes as tall as the bulrush.

Answer: ${\displaystyle \left(2+\frac{6}{13}\right)}$ days; the height is ${\displaystyle \left(4+\frac{8}{10}+\frac{6}{130}\right)}$ units.

Explanation:

• Suppose it is day 2. The club-rush is shorter than the bulrush by 1.5 units.
• Suppose it is day 3. The club-rush is taller than the bulrush by 1.75 units. ∎

To understand this, we shall model the heights of the plants on day n (n = 1, 2, 3...) after a geometric series.

${\displaystyle B(n)=\sum _{i=1}^{n}3\cdot \frac{1}{2^{i-1}}}$Bulrush

${\displaystyle C(n)=\sum _{i=1}^{n}1\cdot 2^{i-1}}$Club-rush

For the sake of better notations, let ${\displaystyle k=i-1.}$ Rewrite the plant height series ${\displaystyle B(n),C(n)}$ in terms of k and invoke the formula for a geometric series.

${\displaystyle B(n)=\sum _{k=0}^{n-1}3\cdot \frac{1}{2^k}=3\left(\frac{1-(\frac{1}{2}{)}^{n-1+1}}{1-\frac{1}{2}}\right)=6\left(1-\frac{1}{2^n}\right)}$

${\displaystyle C(n)=\sum _{k=0}^{n-1}{2}^k=\frac{1-2^n}{1-2}=2^n-1}$

Now, use regula falsi to find the root of ${\displaystyle (C(n)-B(n))}$

${\displaystyle F(n):=C(n)-B(n)=\frac{6}{2^n}+2^n-7}$

• Set ${\displaystyle x_1=2}$ and compute ${\displaystyle F(x_1)=F(2)}$ which equals −1.5 (the "deficit").
• Set ${\displaystyle x_2=3}$ and compute ${\displaystyle F(x_2)=F(3)}$ which equals 1.75 (the "excess").

Estimated root (1st iteration):

${\displaystyle \hat{x}=\frac{x_{1}F(x_2)-x_{2}F(x_1)}{F(x_2)-F(x_1)}=\frac{2\times 1.75+3\times 1.5}{1.75+1.5}=\frac{32}{13}\approx 2.4615}$

To find the exact root, let ${\displaystyle y=2^n}$so that we seek to solve ${\displaystyle 6/y+y-7=0}$. Multiply by ${\displaystyle y}$ to get the quadratic equation ${\displaystyle y^2-7y+6=0}$ which has roots ${\displaystyle y=0}$ (which is spurious here) and ${\displaystyle y=6}$ (the root we want). Thus ${\displaystyle n={\log }_2(6)\approx 2.5849625}$ and our estimation has an error of 4.78%.

Example code

This example program, written in the C programming language, is an example of the Illinois algorithm. To find the positive number x where cos(x) = x³, the equation is transformed into a root-finding form f (x) = cos(x) − x³ = 0.

<span id="mwAjg"></span><span class="cp" id="mwAjk">#include</span><span class="w" id="mwAjo"> </span><span class="cpf" id="mwAjs"><stdio.h></span> <span class="cp" id="mwAjw">#include</span><span class="w" id="mwAj0"> </span><span class="cpf" id="mwAj4"><math.h></span> <span class="kt" id="mwAj8">double</span><span class="w" id="mwAkA"> </span><span class="nf" id="mwAkE">f</span><span class="p" id="mwAkI">(</span><span class="kt" id="mwAkM">double</span><span class="w" id="mwAkQ"> </span><span class="n" id="mwAkU">x</span><span class="p" id="mwAkY">)</span><span class="w" id="mwAkc"> </span><span class="p" id="mwAkg">{</span> <span class="w" id="mwAkk"> </span><span class="k" id="mwAko">return</span><span class="w" id="mwAks"> </span><span class="n" id="mwAkw">cos</span><span class="p" id="mwAk0">(</span><span class="n" id="mwAk4">x</span><span class="p" id="mwAk8">)</span><span class="w" id="mwAlA"> </span><span class="o" id="mwAlE">-</span><span class="w" id="mwAlI"> </span><span class="n" id="mwAlM">x</span><span class="w" id="mwAlQ"> </span><span class="o" id="mwAlU">*</span><span class="w" id="mwAlY"> </span><span class="n" id="mwAlc">x</span><span class="w" id="mwAlg"> </span><span class="o" id="mwAlk">*</span><span class="w" id="mwAlo"> </span><span class="n" id="mwAls">x</span><span class="p" id="mwAlw">;</span> <span class="p" id="mwAl0">}</span> <span class="cm" id="mwAl4">/* a,b: endpoints of an interval where we search</span> <span class="cm" id="mwAl8"> e: half of upper bound for relative error</span> <span class="cm" id="mwAmA"> m: maximal number of iteration</span> <span class="cm" id="mwAmE">*/</span> <span class="kt" id="mwAmI">double</span><span class="w" id="mwAmM"> </span><span class="nf" id="mwAmQ">falsi_method</span><span class="p" id="mwAmU">(</span><span class="kt" id="mwAmY">double</span><span class="w" id="mwAmc"> </span><span class="p" id="mwAmg">(</span><span class="o" id="mwAmk">*</span><span class="n" id="mwAmo">f</span><span class="p" id="mwAms">)(</span><span class="kt" id="mwAmw">double</span><span class="p" id="mwAm0">),</span><span class="w" id="mwAm4"> </span><span class="kt" id="mwAm8">double</span><span class="w" id="mwAnA"> </span><span class="n" id="mwAnE">a</span><span class="p" id="mwAnI">,</span><span class="w" id="mwAnM"> </span><span class="kt" id="mwAnQ">double</span><span class="w" id="mwAnU"> </span><span class="n" id="mwAnY">b</span><span class="p" id="mwAnc">,</span><span class="w" id="mwAng"> </span><span class="kt" id="mwAnk">double</span><span class="w" id="mwAno"> </span><span class="n" id="mwAns">e</span><span class="p" id="mwAnw">,</span><span class="w" id="mwAn0"> </span><span class="kt" id="mwAn4">int</span><span class="w" id="mwAn8"> </span><span class="n" id="mwAoA">m</span><span class="p" id="mwAoE">)</span><span class="w" id="mwAoI"> </span><span class="p" id="mwAoM">{</span> <span class="w" id="mwAoQ"> </span><span class="kt" id="mwAoU">double</span><span class="w" id="mwAoY"> </span><span class="n" id="mwAoc">c</span><span class="p" id="mwAog">,</span><span class="w" id="mwAok"> </span><span class="n" id="mwAoo">fc</span><span class="p" id="mwAos">;</span> <span class="w" id="mwAow"> </span><span class="kt" id="mwAo0">int</span><span class="w" id="mwAo4"> </span><span class="n" id="mwAo8">n</span><span class="p" id="mwApA">,</span><span class="w" id="mwApE"> </span><span class="n" id="mwApI">side</span><span class="w" id="mwApM"> </span><span class="o" id="mwApQ">=</span><span class="w" id="mwApU"> </span><span class="mi" id="mwApY">0</span><span class="p" id="mwApc">;</span> <span class="w" id="mwApg"> </span><span class="cm" id="mwApk">/* starting values at endpoints of interval */</span> <span class="w" id="mwApo"> </span><span class="kt" id="mwAps">double</span><span class="w" id="mwApw"> </span><span class="n" id="mwAp0">fa</span><span class="w" id="mwAp4"> </span><span class="o" id="mwAp8">=</span><span class="w" id="mwAqA"> </span><span class="n" id="mwAqE">f</span><span class="p" id="mwAqI">(</span><span class="n" id="mwAqM">a</span><span class="p" id="mwAqQ">);</span> <span class="w" id="mwAqU"> </span><span class="kt" id="mwAqY">double</span><span class="w" id="mwAqc"> </span><span class="n" id="mwAqg">fb</span><span class="w" id="mwAqk"> </span><span class="o" id="mwAqo">=</span><span class="w" id="mwAqs"> </span><span class="n" id="mwAqw">f</span><span class="p" id="mwAq0">(</span><span class="n" id="mwAq4">b</span><span class="p" id="mwAq8">);</span> <span class="w" id="mwArA"> </span><span class="k" id="mwArE">for</span><span class="w" id="mwArI"> </span><span class="p" id="mwArM">(</span><span class="n" id="mwArQ">n</span><span class="w" id="mwArU"> </span><span class="o" id="mwArY">=</span><span class="w" id="mwArc"> </span><span class="mi" id="mwArg">0</span><span class="p" id="mwArk">;</span><span class="w" id="mwAro"> </span><span class="n" id="mwArs">n</span><span class="w" id="mwArw"> </span><span class="o" id="mwAr0"><</span><span class="w" id="mwAr4"> </span><span class="n" id="mwAr8">m</span><span class="p" id="mwAsA">;</span><span class="w" id="mwAsE"> </span><span class="n" id="mwAsI">n</span><span class="o" id="mwAsM">++</span><span class="p" id="mwAsQ">)</span><span class="w" id="mwAsU"> </span><span class="p" id="mwAsY">{</span> <span class="w" id="mwAsc"> </span><span class="n" id="mwAsg">c</span><span class="w" id="mwAsk"> </span><span class="o" id="mwAso">=</span><span class="w" id="mwAss"> </span><span class="p" id="mwAsw">(</span><span class="n" id="mwAs0">fa</span><span class="w" id="mwAs4"> </span><span class="o" id="mwAs8">*</span><span class="w" id="mwAtA"> </span><span class="n" id="mwAtE">b</span><span class="w" id="mwAtI"> </span><span class="o" id="mwAtM">-</span><span class="w" id="mwAtQ"> </span><span class="n" id="mwAtU">fb</span><span class="w" id="mwAtY"> </span><span class="o" id="mwAtc">*</span><span class="w" id="mwAtg"> </span><span class="n" id="mwAtk">a</span><span class="p" id="mwAto">)</span><span class="w" id="mwAts"> </span><span class="o" id="mwAtw">/</span><span class="w" id="mwAt0"> </span><span class="p" id="mwAt4">(</span><span class="n" id="mwAt8">fa</span><span class="w" id="mwAuA"> </span><span class="o" id="mwAuE">-</span><span class="w" id="mwAuI"> </span><span class="n" id="mwAuM">fb</span><span class="p" id="mwAuQ">);</span> <span class="w" id="mwAuU"> </span><span class="k" id="mwAuY">if</span><span class="w" id="mwAuc"> </span><span class="p" id="mwAug">(</span><span class="n" id="mwAuk">fabs</span><span class="p" id="mwAuo">(</span><span class="n" id="mwAus">b</span><span class="w" id="mwAuw"> </span><span class="o" id="mwAu0">-</span><span class="w" id="mwAu4"> </span><span class="n" id="mwAu8">a</span><span class="p" id="mwAvA">)</span><span class="w" id="mwAvE"> </span><span class="o" id="mwAvI"><</span><span class="w" id="mwAvM"> </span><span class="n" id="mwAvQ">e</span><span class="w" id="mwAvU"> </span><span class="o" id="mwAvY">*</span><span class="w" id="mwAvc"> </span><span class="n" id="mwAvg">fabs</span><span class="p" id="mwAvk">(</span><span class="n" id="mwAvo">b</span><span class="w" id="mwAvs"> </span><span class="o" id="mwAvw">+</span><span class="w" id="mwAv0"> </span><span class="n" id="mwAv4">a</span><span class="p" id="mwAv8">))</span> <span class="w" id="mwAwA"> </span><span class="k" id="mwAwE">break</span><span class="p" id="mwAwI">;</span> <span class="w" id="mwAwM"> </span><span class="n" id="mwAwQ">fc</span><span class="w" id="mwAwU"> </span><span class="o" id="mwAwY">=</span><span class="w" id="mwAwc"> </span><span class="n" id="mwAwg">f</span><span class="p" id="mwAwk">(</span><span class="n" id="mwAwo">c</span><span class="p" id="mwAws">);</span> <span class="w" id="mwAww"> </span><span class="k" id="mwAw0">if</span><span class="w" id="mwAw4"> </span><span class="p" id="mwAw8">(</span><span class="n" id="mwAxA">fc</span><span class="w" id="mwAxE"> </span><span class="o" id="mwAxI">*</span><span class="w" id="mwAxM"> </span><span class="n" id="mwAxQ">fb</span><span class="w" id="mwAxU"> </span><span class="o" id="mwAxY">></span><span class="w" id="mwAxc"> </span><span class="mi" id="mwAxg">0</span><span class="p" id="mwAxk">)</span><span class="w" id="mwAxo"> </span><span class="p" id="mwAxs">{</span> <span class="w" id="mwAxw"> </span><span class="cm" id="mwAx0">/* fc and fb have same sign, copy c to b */</span> <span class="w" id="mwAx4"> </span><span class="n" id="mwAx8">b</span><span class="w" id="mwAyA"> </span><span class="o" id="mwAyE">=</span><span class="w" id="mwAyI"> </span><span class="n" id="mwAyM">c</span><span class="p" id="mwAyQ">;</span><span class="w" id="mwAyU"> </span><span class="n" id="mwAyY">fb</span><span class="w" id="mwAyc"> </span><span class="o" id="mwAyg">=</span><span class="w" id="mwAyk"> </span><span class="n" id="mwAyo">fc</span><span class="p" id="mwAys">;</span> <span class="w" id="mwAyw"> </span><span class="k" id="mwAy0">if</span><span class="w" id="mwAy4"> </span><span class="p" id="mwAy8">(</span><span class="n" id="mwAzA">side</span><span class="w" id="mwAzE"> </span><span class="o" id="mwAzI">==</span><span class="w" id="mwAzM"> </span><span class="mi" id="mwAzQ">-1</span><span class="p" id="mwAzU">)</span> <span class="w" id="mwAzY"> </span><span class="n" id="mwAzc">fa</span><span class="w" id="mwAzg"> </span><span class="o" id="mwAzk">/=</span><span class="w" id="mwAzo"> </span><span class="mi" id="mwAzs">2</span><span class="p" id="mwAzw">;</span> <span class="w" id="mwAz0"> </span><span class="n" id="mwAz4">side</span><span class="w" id="mwAz8"> </span><span class="o" id="mwA0A">=</span><span class="w" id="mwA0E"> </span><span class="mi" id="mwA0I">-1</span><span class="p" id="mwA0M">;</span> <span class="w" id="mwA0Q"> </span><span class="p" id="mwA0U">}</span><span class="w" id="mwA0Y"> </span><span class="k" id="mwA0c">else</span><span class="w" id="mwA0g"> </span><span class="k" id="mwA0k">if</span><span class="w" id="mwA0o"> </span><span class="p" id="mwA0s">(</span><span class="n" id="mwA0w">fa</span><span class="w" id="mwA00"> </span><span class="o" id="mwA04">*</span><span class="w" id="mwA08"> </span><span class="n" id="mwA1A">fc</span><span class="w" id="mwA1E"> </span><span class="o" id="mwA1I">></span><span class="w" id="mwA1M"> </span><span class="mi" id="mwA1Q">0</span><span class="p" id="mwA1U">)</span><span class="w" id="mwA1Y"> </span><span class="p" id="mwA1c">{</span> <span class="w" id="mwA1g"> </span><span class="cm" id="mwA1k">/* fc and fa have same sign, copy c to a */</span> <span class="w" id="mwA1o"> </span><span class="n" id="mwA1s">a</span><span class="w" id="mwA1w"> </span><span class="o" id="mwA10">=</span><span class="w" id="mwA14"> </span><span class="n" id="mwA18">c</span><span class="p" id="mwA2A">;</span><span class="w" id="mwA2E"> </span><span class="n" id="mwA2I">fa</span><span class="w" id="mwA2M"> </span><span class="o" id="mwA2Q">=</span><span class="w" id="mwA2U"> </span><span class="n" id="mwA2Y">fc</span><span class="p" id="mwA2c">;</span> <span class="w" id="mwA2g"> </span><span class="k" id="mwA2k">if</span><span class="w" id="mwA2o"> </span><span class="p" id="mwA2s">(</span><span class="n" id="mwA2w">side</span><span class="w" id="mwA20"> </span><span class="o" id="mwA24">==</span><span class="w" id="mwA28"> </span><span class="o" id="mwA3A">+</span><span class="mi" id="mwA3E">1</span><span class="p" id="mwA3I">)</span> <span class="w" id="mwA3M"> </span><span class="n" id="mwA3Q">fb</span><span class="w" id="mwA3U"> </span><span class="o" id="mwA3Y">/=</span><span class="w" id="mwA3c"> </span><span class="mi" id="mwA3g">2</span><span class="p" id="mwA3k">;</span> <span class="w" id="mwA3o"> </span><span class="n" id="mwA3s">side</span><span class="w" id="mwA3w"> </span><span class="o" id="mwA30">=</span><span class="w" id="mwA34"> </span><span class="o" id="mwA38">+</span><span class="mi" id="mwA4A">1</span><span class="p" id="mwA4E">;</span> <span class="w" id="mwA4I"> </span><span class="p" id="mwA4M">}</span><span class="w" id="mwA4Q"> </span><span class="k" id="mwA4U">else</span><span class="w" id="mwA4Y"> </span><span class="p" id="mwA4c">{</span> <span class="w" id="mwA4g"> </span><span class="cm" id="mwA4k">/* fc * f_ very small (looks like zero) */</span> <span class="w" id="mwA4o"> </span><span class="k" id="mwA4s">break</span><span class="p" id="mwA4w">;</span> <span class="w" id="mwA40"> </span><span class="p" id="mwA44">}</span> <span class="w" id="mwA48"> </span><span class="p" id="mwA5A">}</span> <span class="w" id="mwA5E"> </span><span class="k" id="mwA5I">return</span><span class="w" id="mwA5M"> </span><span class="n" id="mwA5Q">c</span><span class="p" id="mwA5U">;</span> <span class="p" id="mwA5Y">}</span> <span class="kt" id="mwA5c">int</span><span class="w" id="mwA5g"> </span><span class="nf" id="mwA5k">main</span><span class="p" id="mwA5o">(</span><span class="kt" id="mwA5s">void</span><span class="p" id="mwA5w">)</span><span class="w" id="mwA50"> </span><span class="p" id="mwA54">{</span> <span class="w" id="mwA58"> </span><span class="n" id="mwA6A">printf</span><span class="p" id="mwA6E">(</span><span class="s" id="mwA6I">"%0.15f</span><span class="se" id="mwA6M">\n</span><span class="s" id="mwA6Q">"</span><span class="p" id="mwA6U">,</span><span class="w" id="mwA6Y"> </span><span class="n" id="mwA6c">falsi_method</span><span class="p" id="mwA6g">(</span><span class="o" id="mwA6k">&</span><span class="n" id="mwA6o">f</span><span class="p" id="mwA6s">,</span><span class="w" id="mwA6w"> </span><span class="mi" id="mwA60">0</span><span class="p" id="mwA64">,</span><span class="w" id="mwA68"> </span><span class="mi" id="mwA7A">1</span><span class="p" id="mwA7E">,</span><span class="w" id="mwA7I"> </span><span class="mf" id="mwA7M">5E-15</span><span class="p" id="mwA7Q">,</span><span class="w" id="mwA7U"> </span><span class="mi" id="mwA7Y">100</span><span class="p" id="mwA7c">));</span> <span class="w" id="mwA7g"> </span><span class="k" id="mwA7k">return</span><span class="w" id="mwA7o"> </span><span class="mi" id="mwA7s">0</span><span class="p" id="mwA7w">;</span> <span class="p" id="mwA70">}</span>

After running this code, the final answer is approximately 0.865474033101614.