Multiplication and Division Algorithms
Download 39.22 Kb.
|
- Navigate this page:
- Works Cited
- Picture Bibliography
| Multiplication and Division Algorithms
Charlton Lu Mathematics of the Universe – Math 89S Professor Bray 6 December 2016 Introduction: Today, computers can be programmed to solve extremely complex problems and process large amounts of data—their speed allows them to perform many tasks in a fraction of the time that it would take a human. However, their ability to solve problems quickly stems not only from the raw computing ability of a computer, but also from the efficient algorithms that programmers write in order to optimize efficiency. For example, the computer programs that perform multiplication and division use efficient methods that far outpace our conventional methods. By maximizing efficiency at the most fundamental level of computer science, computer programmers can drastically improve the computing speed of programs that call upon these operations. This paper will discuss the algorithms computers use in multiplication and division that optimize calculation speed.
In order to measure efficiency, we introduce the idea of time complexity. The time complexity of an algorithm measures the time an algorithm takes to run as a function of the input length. The time taken to run is estimated by counting the amount of elementary operations (e.g. single digit multiplication) required to execute the algorithm. We focus on multiplications rather than additions and subtractions because their computing time will far eclipse that of addition and subtraction as input sizes increase. Then, we can produce an expression for the number of elementary operations needed as a function of the input length. For example, an algorithm may require In some cases, the number of operations an algorithm requires to solve a problem may depend on not only the length of the input, but also what the inputs are. For example, multiplying two 2-digit numbers takes fewer operations if one of the numbers is a multiple of 10. On a more complex level, Gaussian Elimination will take fewer operations in many situations such as if any row has a 0 as the leading entry, or if one row is a scalar multiple of another. In cases where the algorithm may take fewer steps, the time complexity of the algorithm is typically given by the worst-case time-complexity, which is the maximum number of operations needed to run the algorithm on an input of length Multiplication, a fundamental operation in mathematics, is pervasive in computer programs. Given how often multiplication is used, an algorithm that shortens multiplication time will also significantly speed up many programs. Recognizing this fact, mathematicians and computer scientists alike searched for a more efficient multiplication algorithm. The classic multiplication algorithm we all learned in grade school, also known as long multiplication, requires the multiplication of each digit of one number by each digit of the other number. A multiplication of two 2-digit numbers In 1960, Anatoly Karatsuba discovered an algorithm that made multiplication more efficient. His algorithm comes from the decomposition of an we can now express the product Multiplying the two compositions yields a new expression: In this expression, we have to perform four multiplications, which is no more efficient than long multiplication. However, by implementing a clever trick, we can reduce the number of necessary multiplications to three. If we calculate the value (  we yield the number  . Subtracting  and  , which we already must calculate to find the first and third terms of the product, we are left with  , the middle term of the expression 2. Thus, we can calculate all three terms of the polynomial in just three multiplications (Ofman, Karatsuba):
, ( , and .
To give a numerical example, consider the 2-digit numbers 12 and 34. Then we have:
Thus, we find that:
Then, we can plug back into expression 2 to yield: The example here is known as the base case in recursion: it can be solved using addition, subtraction, and single digit multiplication—the most fundamental operations. When larger numbers are passed onto the algorithm, more steps are required in order to reach the base case. For example, if  and  are 4-digit integers, then  ,  ,  , and  will then be 2-digit integers. As a result, the multiplications , (, and cannot be solved using single digit operations. Another recursive call of the Karatsuba multiplication must be made in order to solve the three smaller multiplications. The time complexity of the Karatsuba multiplication can be calculated using this fact (Babai). If each call of the Karatsuba multiplication algorithm  requires three further multiplications and halves the number of digits in each smaller multiplication, then we write:
If we use mathematical induction, we find that for every  where  , we have:
since the base case does not require further Karatsuba multiplication, but only three single-digit multiplications. To find the time complexity of Karatsuba multiplication, we take the log of equation 4, and simplify, leading to the equation: Thus, the time complexity of Karatsuba multiplication (  ) is more efficient than long multiplication, and takes significantly less computing time when the length of the input increases to very high numbers. Looking at the Figure 1 below, we can see that long multiplication quickly begins to require much more operations than Karatsuba multiplication; for an input length of just 10, long multiplication will already require more than double the operations as Karatsuba multiplication (Knuth).
Figure 1: Long Multiplication (Red) Karatsuba Multiplication (Blue)
Toom-Cook Algorithm The Toom-Cook algorithm is a generalization of the Karatsuba multiplication. Instead of splitting integers into two parts, the Toom-Cook algorithm allows for more complex splitting. For example, the Toom-Cook 3 Way method involves splitting an integer into three parts. These parts are written in terms of a polynomials so that integers where  is equal to  since we split each integer is split into three pieces in the Toom-Cook 3 algorithm. Multiplying these together, we obtain a new polynomial expression  :
First, we choose strategic values of  in order to make the future calculations easier. Because  is the product of  and  , we can plug the strategic values of  into and and multiply them together, which involves five multiplications. If the length of the integers being multiplied is greater than 3, these multiplications will require another recursive call of the Toom-Cook algorithm, so a large multiplication can be decomposed into five smaller ones. Each of these products will be equal to the following, respectively:
By plugging values into this polynomial, we can obtain a system of equations to solve for the polynomial coefficients. We can now see the rationale behind choosing values —they yield a system of equations that is easier to solve. These equations can be rewritten as
which can be solved for Toom-Cook Complexity The Toom Cook 3-algorithm reduces a large multiplication to 5 multiplications of smaller numbers. Thus, we can write:
This implies that the Toom Cook 3-algorithm has a complexity of  .
In general, the Toom Cook k-algorithm has a complexity of Implementation: Because the time-complexity of Karatsuba and Toom-Cook multiplication are both better than that of long multiplication, they will become faster than long multiplication as input size rises towards infinity. However, they are not necessarily more efficient than long multiplication at all input sizes. There are several factors that contribute to this nuance. For instance, both Karatsuba and Toom-Cook multiplication are slower than long multiplication at small inputs because recursive overhead—the computing power required to recursively call a function several times—will outweigh multiplicative efficiency when Division algorithm Division can be understood as a multiplication between a dividend and the reciprocal of the divisor. As a result, many division algorithms involve two steps: finding the reciprocal of the dividend, and employing a multiplication algorithm to find the quotient. To find the reciprocal of a number
Applying Newton’s method, we can iterate  to find increasingly accurate estimates of  Each iteration of the algorithm can be given by the following:
Figure 2: Newton’s Method 
Figure 2 gives a visual representation of Newton’s Method at work. Using the derivative of the function, we find increasingly precise estimates of the root. We can quantity the accuracy of each estimate using error analysis: if we define the error  to be  , the difference between the actual value of  and our estimate, we find the error after each iteration of Newton’s Method. However, using  , which is equivalent to the first expression multiplied by  , will yield the same result with much cleaner math. We then calculate the error after an iteration of Newton’s method.
This implies that each iteration of Newton’s method will result in roughly a doubling of the number of correct digits in the result. After calculating the reciprocal of Like multiplication, the implementation of division algorithms will often be slower than standard long division for small inputs due to recursive overhead. In addition, the computing power used to calculate the reciprocal of an operand for small inputs would be more efficiently utilized on simply carrying out the long division. Thus, like multiplication, the division algorithm used by computers will depend on the input length. Typically, the Newton-Raphson algorithm is only used for very large inputs (Papadimitriou).
Currently, the fastest multiplication and division algorithm for two n digit integers remains an open question in computer science. And yet, an increase in multiplication and division efficiency could lead to significantly faster computing speeds and new capabilities to process ever-increasing amounts of data. Works CitedBabai, Laszlo. "Divide and Conquer: The Karatsuba–Ofman algorithm." UChicago: Laszlo Babai. 3 Dec 2016 Bodrato, M. Zanoni. "Integer and Polynomial Multiplication: Towards Optimal Toom-Cook Matrices." Proceedings of the ISSAC 2007 Conference. New York: ACM press, 2007. Cook, Stephen A. On the Minimum Computation Time of Functions. Cambridge, 1966. Knuth, Donald. The Art of Computer Programming. Addison Wesley , 2005. Kronenburg, M.J. Toom-Cook Multiplication: Some Theoretical and Practical Aspects. 16 Feb 2016. Ofman, A. Karatsuba and Yu. "Multiplication of Many-Digital Numbers by Automatic Computers." Proceedings of the USSR Academy of Sciences. Physics-Doklady, 1963. 595–596. Papadimitriou, Christos H. Computational complexity. Reading: Addison-Wesley, 1994. Smith, Mark D. "Newton-Raphson Technique ." 1 Oct 1998. MIT 10.001. 6 Dec 2016 Picture Bibliography
Directory: ~bray -> Courses -> 89s-MOU -> 2016-Fall -> Papers 89s-MOU -> Arturo Villarreal Math89s 89s-MOU -> Asteroid impact: analyzing what it takes to detect and prevent a cosmic assualt Papers -> Professor: Dr. Hubert Bray Courses -> The Free Will Theorem Kushal Byatnal Summary Download 39.22 Kb. Share with your friends:
|
elementary operations to execute where 
is the input length. The time complexity of this algorithm is described asymptotically—as the input length goes to infinity. Thus, the time complexity of this algorithm is represented as 
—equivalent to the limit as 
CITATION Pap94 \l 1033 
and 
will require four single-digit multiplications: 
, 
, 
and 
. More generally, the product of two 
multiplications 
. While the long multiplication algorithm works very quickly for small numbers, the number of operations required increases quadratically, which translates to a quadratically increasing computing time.
where 
digits and 
If we have another 
, 
as the product of the two compositions:
and 
, (
, and 
.
.
, and if 
, then 
=
. Plugging back into our original equation, we can find that the product of the multiplication is equal to 
.
.
. It is also interesting to note that Karatsuba multiplication is actually a special case of the Toom Cook algorithm (Toom-Cook 2-algorithm) and long multiplication is simply the Toom Cook 1-algorithm (Knuth).
.
.
where 
is the number of fundamental operations needed to calculate the reciprocal to 
= 
since exponential growth will eclipse the other term’s growth as input length approaches infinity. Therefore, division will have the same asymptotic complexity as multiplication (Cook).