Definition 2.2.1.
An algorithm is a precise sequence of steps to accomplish a task.
Section 2.2 Algorithms
One of the questions in Example ex:sqrt:65 asked to write down the steps to find the square root. Throughout this book and in many related fields, like computer science, reproducing results in a specific ways is immensely important. We call this an algorithm.
The next example shows that we actually use algorithm in our daily lives. This is a short cooking example, but finding directions or navigating webpages are other good examples of using algorithms.
Example 2.2.2.
Write down an algorithm to make a peanut butter and jelly sandwich.
Solution.
-
Gather all ingredients (peanut butter, jelly and two slices of bread) and a knife.
-
Place the bread on a plate. Spread peanut butter on one side of one slice, spread jelly on one side of the other slice of bread.
-
Place the peanut butter coated bread on top of the jelly side of the other slice. Make sure the peanut butter side sticks to the jelly side.
-
Serve and enjoy.
The next example is a relatively straightforward mathematical problem.
Example 2.2.3.
The next example shows the algorithm that can be used to find \(\sqrt{65}\) as in Example 2.1.1. This is called the bisection method and we will see the details of the algorithm in Chapter 3—in short it starts with an interval that always contains the answer and through a procedure, finds subintervals that still contains the answer and the length of the subinterval shrinks.
Example 2.2.4.
Solution.
In this case, we will produce a sequence of numbers \(a_{0},a_{1},a_{2},\ldots\) that are always below \(\sqrt{a}\) and \(b_{0},b_{1},b_{2}, \ldots\) that are always above \(\sqrt{a}\text{.}\) The algorithm is listed below and sentences in italics are simply comments.
Let the inputs be \(a\text{,}\) a real number greater than 0 and \(d\) be an integer greater than 1.
-
Let \(\epsilon = 10^{-d}\text{.}\) This number is the precision which we intend to reach.
-
If \(a \gt 1\text{,}\) then \(a_{0}=1\) and \(b_{0}=a\text{.}\) If \(a \lt 1\) then \(a_{0}=a\) and \(b_{0}=1\text{.}\) This ensures that \(\sqrt{a}\in [a_{0},b_{0}]\text{.}\)
-
Let \(n=0\)
-
Let \(c_{n}=(a_{n}+b_{n})/2\text{.}\) Take the midpoint of the interval as a new guess for the \(\sqrt{a}\text{.}\)
-
If \(c_{n}^{2} \gt a\) then \(a_{n+1}=a_{n}\) and \(b_{n+1}=c_{n}\text{,}\) otherwise let \(a_{n+1}=c_{n}\) and \(b_{n+1}=b_{n}\text{.}\)
-
If \(b_{n+1}-a_{n+1} \lt \epsilon\) then stop, return \(0.5(a_{n+1}+b_{n+1})\) otherwise, increment \(n\) by 1.
-
Return to step 4.
The next example shows how to employ a spreadsheet to run through the algorithm in Example 2.2.4. Computers are a great tool to automate algorithms and spreadsheets as well as other tools such as Maple, Mathematics, Matlab or programs written in other languages are how a lot of mathematics are done.
Example 2.2.5.
Use a computer program (Maple or a spreadsheet) to find \(\sqrt{65}\) to 3 decimal places using the algorithm in Example 2.2.4.
Solution.
In this case, we will use a spreadsheet to accomplish this. We will make three columns (A, B, C) for the three sequences \(a_{n}, b_{n}\) and \(c_{n}\text{.}\)
-
Since \(a=65 \gt 1\text{,}\) we will put a 1 in the first row of column A and a 65 in the first row of column B. For column C, enter =0.5*(a1+b1) and you should get 33. Also, create a column (in D) that will be the error. Enter in cell D1, =b1-a1.
-
For the next row, we enter step 4 from Example ex:sqrt in the spreadsheet. For cell A2, enter =IF(C12 > 65,A1,C1). This will fill in either the mean (in column C) or the value above it. For cell B2, enter =IF(C12>65,C1,B1).
-
For cell C2, enter =0.5*(a2+b2) and for the error in D2, enter =c2-a2.
-
To continue this, you can select the four columns in the second row, click on the lower right corner and drag down an number a places. The spreadsheet will fill in the values in a recursive manner.
You should see the following:
| \(n\) | \(A\) | \(B\) | \(C\) | \(B—A\) |
| \(1\) | \(1.00000\) | \(65.00000\) | \(33.00000\) | \(64\) |
| \(2\) | \(1.00000\) | \(33.00000\) | \(17.00000\) | \(32\) |
| \(3\) | \(1.00000\) | \(17.00000\) | \(9.00000\) | \(16\) |
| \(4\) | \(1.00000\) | \(9.00000\) | \(5.00000\) | \(8\) |
| \(5\) | \(5.00000\) | \(9.00000\) | \(7.00000\) | \(4\) |
| \(6\) | \(7.00000\) | \(9.00000\) | \(8.00000\) | \(2\) |
| \(7\) | \(8.00000\) | \(9.00000\) | \(8.50000\) | \(1\) |
| \(8\) | \(8.00000\) | \(8.50000\) | \(8.25000\) | \(0.5\) |
| \(9\) | \(8.00000\) | \(8.25000\) | \(8.12500\) | \(0.25\) |
| \(10\) | \(8.00000\) | \(8.12500\) | \(8.06250\) | \(0.125\) |
| \(11\) | \(8.00000\) | \(8.06250\) | \(8.03125\) | \(0.0625\) |
| \(12\) | \(8.03125\) | \(8.06250\) | \(8.04688\) | \(0.03125\) |
| \(13\) | \(8.04688\) | \(8.06250\) | \(8.05469\) | \(0.015625\) |
| \(14\) | \(8.05469\) | \(8.06250\) | \(8.05859\) | \(0.0078125\) |
| \(15\) | \(8.05859\) | \(8.06250\) | \(8.06055\) | \(0.00390625\) |
| \(16\) | \(8.06055\) | \(8.06250\) | \(8.06152\) | \(0.001953125\) |
| \(17\) | \(8.06152\) | \(8.06250\) | \(8.06201\) | \(0.0009765625\) |
In the 17th row, you will see that the error (in the last row) is now smaller than 0.001, so you should stop. The approximation to the \(\sqrt{65}\) is 3.06201, which is correct to 3 digits.
This method is called the bisection method and we will see it in detail in the next chapter.
Subsection 2.2.1 Newtons’ Method: A Better Square Root Algorithm
We will use Newton’s Method, that will be presented in Chapter 3 to write down an alternative square root algorithm.
-
Let \(x_{0}=a\)
-
Let \(\displaystyle x_{n+1}= \frac{x_{n}}{2}+ \frac{a}{2x_{n}}\)
-
Repeat step 2 until \(|x_{n+1}-x_{n}| \lt 10^{-d}\text{.}\)
-
Return \(x_{n+1}\text{.}\)
Example 2.2.7.
Use Newton’s Method to find \(\sqrt{65}\) to 3 digits.
Solution.
In this case, we will use a spreadsheet again. The first column will be \(n\) and the 2nd column will be \(x_{n}\text{.}\) In the first row, enter \(0\) and \(65\text{.}\) In the second row enter
=a1+1 and =b1/2+65/(2*b1). Select these two cells and in the bottom left corner, drag down a number of rows. You should see:
| \(n\) | \(x_{n}\) | \(|x_{n+1}-x_{n}|\) |
| \(0\) | \(1.00000000\) | |
| \(1\) | \(33.00000000\) | \(32.00000000\) |
| \(2\) | \(17.48484848\) | \(15.51515152\) |
| \(3\) | \(10.60117641\) | \(6.88367208\) |
| \(4\) | \(8.36628570\) | \(2.23489071\) |
| \(5\) | \(8.06778188\) | \(0.29850382\) |
| \(6\) | \(8.06225964\) | \(0.00552224\) |
| \(7\) | \(8.06225775\) | \(0.00000189\) |
Subsection 2.2.2 YASRA: Yet Another Square Root Algorithm
We will use Taylor’s series (see Section 1.6) for \(f(x)=\sqrt{x}\) to find another algorithm for the square of \(a\text{.}\) Let \(c\) be the center of the Taylor’s Series of a function \(f(x)\text{.}\) Then the function can be written
\begin{equation*}
f(x) = \sqrt{c}+ \sum_{n=1}^{\infty}(-1)^{n+1}\frac{(2n-3)!!}{2^{n} n!}c^{-(2n-1)/2}(x-c)^{n}
\end{equation*}
where \(n!!=1\cdot 3 \cdot 5 \cdot 7 \cdots n\) and this is similar to Example 1.6.11, but in that example, the center was \(0\) and for this the center of the series is \(c\text{.}\)
From this we develop another square root algorithm to find \(\sqrt{a}\text{.}\)
Algorithm 2.2.9.
-
Let \(x_{0}= \sqrt{c}\)
-
Let \(\displaystyle x_{n+1}= x_{n} + (-1)^{n+1}\frac{(2n-3)!!}{2^{n} n!}c^{-(2n-1)/2}(a-c)^{n}\) until \(|x_{n+1}-x_{n}| \lt 10^{-d}\text{.}\)
-
Repeat step 3 until \(|x_{n+1} - x_n| \lt \epsilon \)
Example 2.2.10.
Use YASRA to find \(\sqrt{65}\) to with 0.0001.
Solution.
-
The first perfect square less than 65 is 64.
-
\(\displaystyle x_{0} = 8\)
-
\begin{equation*} x_1 = x_{0} + \frac{1}{2}64^{-1/2}(65-64) = 8 + \frac{1}{2}\cdot \frac{1}{8} \end{equation*}
-
\begin{equation*} \begin{aligned} x_{2} \amp = x_{1} - \frac{1}{4\cdot 2!}64^{-3/2}(65-64)^{2} = \frac{129}{16}- \frac{1}{2}\frac{1}{4}\cdot \frac{1}{8^{3}} \\ \amp = \frac{33023}{4096} \approx 8.062255859375 \end{aligned} \end{equation*}
-
\begin{equation*} \begin{aligned} x_{3} \amp = x_{2} + \frac{3}{8\cdot 3!}64^{-5/2}(65-64)^{3} = \frac{33023}{4096}+ \frac{3}{48}\cdot \frac{1}{8^{5}}\\ \amp = \frac{4226945}{524288}\approx 8.06225776672 \end{aligned} \end{equation*}
Subsection 2.2.3 Analyzing Algorithms
In this section, we have seen three different ways to compute a square root. Each produces a sequence of points. Here are some of the questions we should ask:
-
Does the algorithm do what is intended? That is, can we prove that each algorithm generates the square root? (Does it converge to the correct answer?)
-
How fast does the sequence converge?
These are two important questions that we will examine as we analyze algorithms throughout this book.
