Home /
Expert Answers /
Computer Science /
integer-multiplication-is-one-of-the-cost-operations-in-computer-arithmetic-it-also-set-bases-for-d-pa802
(Solved): Integer multiplication is one of the cost operations in computer arithmetic. It also set bases for d ...
Integer multiplication is one of the cost operations in computer arithmetic. It also set bases for division, squaring and reciprocals. In addition, multiplication is a key operation in signal processing applications like correlation, filtering, frequency analysis and image processing. In this assignment, you will be asked to implement Karatsuba's algorithm in Python to demonstrate how it can be applied in computer arithmetic. For the Python implementation write a Python code to: - Implement the Karatsuba's algorithm to multiply two 64 -bit integers. Suppose we would like to accelerate the multiplication operation in LEGv8 architecture. Also assume that we have a hardware block that can perform multiplication of any 4 -bit numbers, i.e., a ()/(( 4 \times 4 /)) multiplier. Draw the hardware blocks that will speed up the multiplier unit in LEGv8 datapath by using this new multiplier based on the Karatsuba's algorithm. Integer multiplication is one of the cost operations in computer arithmetic. It also set bases for division, squaring and reciprocals. In addition, multiplication is a key operation in signal processing applications like correlation, filtering, frequency analysis and image processing. In this assignment, you will be asked to implement Karatsuba's algorithm in Python to demonstrate how it can be applied in computer arithmetic. For the Python implementation write a Python code to: - Implement the Karatsuba's algorithm to multiply two 64 -bit integers. Suppose we would like to accelerate the multiplication operation in LEGv8 architecture. Also assume that we have a hardware block that can perform multiplication of any 4 -bit numbers, i.e., a ()/(( 4 \times 4 /)) multiplier. Draw the hardware blocks that will speed up the multiplier unit in LEGv8 datapath by using this new multiplier based on the Karatsuba's algorithm.
1 Introduction
The traditional (grade-school) multiplication method multiplies two n-digit num-
bers using about n^(2) basic multiplications. As numbers grow larger (especially
in computing systems), this method becomes too slow.
Karatsuba's algorithm, discovered by Anatolii Karatsuba in 1960, is a divide-
and-conquer method that reduces the number of multiplications and speeds up
the process. It works in approximately O(n^(log_(2)3))~~O(n^(1.585)) time, which is
faster than O(n^(2)).
2 Basic Idea
Suppose we want to multiply two numbers x and Y, each having n digits.
Split each number into two halves:
x=x_(1)\times 10^(m)+x_(0)
Y=Y_(1)\times 10^(m)+Y_(0)
where:
x_(1),Y_(1)m digitsx_(0),Y_(0)m digits 5 Time Complexity
Let T(n) be the time to multiply two n-digit numbers. Recurrence relation:
T(n)=3T((n)/(2))+O(n)
Solving this gives:
T(n)=O(n^(log_(2)3))~~O(n^(1.585))
which is faster than O(n^(2)).
6 Example
Let's multiply 1234\times 5678 (conceptually):
Split:
