According to Wikipedia, an algorithm is "an unambiguous specification of how to solve a class of problems". While we think of algorithms in connection with modern computer programming, in fact algorithms have been around for millenia. (The word "algorithm" itself comes from the name of a persian scholar, Al-Kwharizmi, who lived roughly 780-850 C.E. His book on calculations using the Indian numerals - what we now call Arabic numerals - was translated into Latin in the 12th century, influencing European and world mathematics for all time.)
One of the more famous of ancient algorithms, still in use today, is Euclid's greatest common divisor (GCD) algorithm. You've played with that algorithm, more or less, if you did the ContinuedFractions APT. There are many other algorithms, however, which are either still in use today, or have been enormously influential along the way to modern algorithms. Below, we will explore four of these algorithms: Egyptian multiplication, the Babylonian method for finding square roots, the Sieve of Eratosthenes, and Archimedes' method for approximating pi.
Your task for this lab is to pick one of the described algorithms and implement it on the modern computer using C++. Of the four algorithms, Archimedes' approximation is the least accessible, so I don't recommend implementing it unless you really want to or feel especially ambitious.
Read through the sections on the different algorithms below, and choose one to implement. What you are expected to do for a given algorithm is detailed in the corresponding section. Your resulting program should be submitted on Canvas.
Variants of this approach for multiplying two integers have been discovered and rediscovered by many cultures. It was used in the building of the pyramids, yet it is still useful today in the digital logic circuits used to multiply binary numbers. It has a wonderful connection, in fact, to the binary numbering system, in that its essential mechanism is the decomposition of one multiplicand into a sum of powers of two (effectively its binary representation).
The basic method (on paper) goes as follows: create two columns; write one multiplicand (preferably the smaller) at the top of the left column, and the other multiplicand at the top of the right column. You can now fill in the left column by dividing by two repeatedly until you get to 1. On each division, you discard any remainder (i.e., when dividing an odd number), so you only have integers in that column. Meanwhile, the right column gets doubled until you have the same count of numbers in the right column.
To complete the multiplication, strike out any rows in your table for which the left-hand number is even. Add up the remaining numbers in the right column to get the answer. For example, if we want to multiply 238 x 13, our table would look like:
| 13 | 238 |
| 6 | 476 |
| 3 | 952 |
| 1 | 1904 |
Crossing out the rows with even numbers in the left column leaves us with the sum 238 + 952 + 1904 = 3094.
Why does this work? If you look at the left-hand column in binary, you may get an intuition:
| 1101 | 238 |
| 110 | 476 |
| 11 | 952 |
| 1 | 1904 |
Each time, the right-most digit of the left-hand column tells us whether or not we are going to keep the corresponding power of 2 times the right-hand multiplicand in our final sum!
If you choose to implement this algorithm, then your program should prompt the user for two (positive) integers to multiply. Display a representation of the two columns you generate, and the final answer. E.g., your program output might look like the following:
Please enter two positive integers: 238 13
13 238
6 476
3 952
1 1904
Answer: 3094
Also known as "Hero's method" after the Greek mathematician who first described it, the Babylonian method is an iterative approximation method for finding square roots. Iterative approximation algorithms can be used when closed-form solutions are not readily available, and work by repeated refinement of a solution towards the true value. These algorithms have many applications in scientific computing.
The Babylonian method is very simple. Given a number n, and a guess at its square root, x, we make the observation that if x is an overestimate of the square root of n, then n / x will be an underestimate of the square root, and vice versa (convince yourself of this with a bit of algebra). Then, it is reasonable to expect that the average of these two numbers is a better estimate of the square root than we started with.
The Babylonian method proceeds, then, by letting x be the average of x and n / x, repeating until the change in values is very small, or until a fixed number of iterations have occurred. The value x will converge on the true square root.
For this algorithm, your program should prompt the user for a number to take the square root of (you should allow floating point or integer values) and an initial guess, and apply the Babylonian method, printing out each estimate of the square root until the change in estimates is less than 1e-8. For example:
Enter a number: 7234
What is your guess? 1000
503.617
258.991
143.461
96.9429
85.7821
85.056
85.0529
85.0529
85.0529
The Sieve of Eratosthenes is an ancient method for finding prime numbers. Prime numbers are crucial in many algorithms, particularly in cryptography, so methods for finding them are quite important; sieve methods based on the Sieve of Eratosthenes are still used.
To apply the sieve, one must first specify a maximum number; the sieve will find all primes less than or equal to the specified number. On paper, the sieve is applied as follows:
For this algorithm, prompt the user for a maximum number, and print out a sequence of all the prime numbers less than the specified number, e.g.
Input a maximum number: 30
2 3 5 7 11 13 17 19 23 29
Archimedes' method is easily explained, but working out the mathematics is a bit more complicated. It is another example of an iterative approximation algorithm.
The very short explanation of Archimedes' approach is that he starts by inscribing a regular hexagon inside a circle (touching the circle at all the vertices) and another regular hexagon outside the circle (so the circle is tangent to all of the sides of the hexagon); the area of the circle must then be between the areas of the two hexagons. Now, double the number of sides of each polygon to twelve - and do it again - and again... each time, the polygons get closer and closer to the actual circle.
Technically this approach will work with any polygons, but hexagons have some useful properties as a starting point, and Archimedes' ingenuity is really in how he works out the length of the sides and the apothems of the polygons after doubling the number of sides.
A nice video that helps illustrate the mathematics can be found here. Note that in this video, only the polygon inside the circle is used, but with the power of a computer, it is possible to make a polygon with a very large number of sides, indeed, thus approximating the circle even better than Archimedes' approach would. If you implement this algorithm, you should probably use this approach.
If you choose this algorithm, then simply print out your successive approximations to pi until the change in values is very small (~1e-12).
To complete this assignment, please submit your code, along with a README, to Canvas. Your README should include your name and the names of your partner(s), and any other comments you'd like to include about the lab.