|
|
|
An algorithm is any systematic mathematical procedure designed to produce an answer to a given type of problem. Two algorithms are listed below: Egyptian Multiplication and Euclidean Algorithm
Egyptian Multiplication Egyptians based their multiplication on a doubling process. The two numbers to be multiplied were written down in a 1, second number to be multiplied format. Both numbers would be doubled until just before the first number exceeded the first number being multiplied. The mathematician/scribe would then check off the lines needed to add up to the first multiplier. The numbers in the second columns of the checks lines would then be added to come with an answer. ~1 23 ~2 46 ~4 92 ~8 184 =345
Euclidean Algorithm This is used to find the greatest common divisor (GCD) of two numbers. In order to find the GCD, take the larger number and divide it by the smaller. Determine what the remainder is. Divide the smaller number by the remainder and determine if it has a remainder. If it does, continue division of the last number divided by (divisor) by the remainder until there is no remainder. When you have reached the point where there is no remainder, the last divisor is the GCD. 232=12*18+16 18=1*16+2 16=8*2+0 The last divisor was 2, therefore the GCD is 2! Gabriel Lame, a French mathematician theorized that the most steps is never greater than five times the number of digits in the first divisor. For our example, the maximum number of steps would be 2*5 or 10 steps. The method can also be used to reduce fractions. Using our example above: 18/232 has a GCD of 2 18/2 = 9 232/2 = 116 Thus the lowest reduction of this fraction is 9/116
|
|
|