BLG336E - Analysis of Algorithms II
Overview
In this project you are going to implement algorithm for the following problem.
Problem:
Multiplying two polynomials efficiently is an important issue in a variety of applications, including signal processing, cryptography and coding theory. Multiplication operations are very costly for very large numbers in terms of time consumption. Especially for algorithms with high mathematical processing density, multiplication and exponent operations should be fast. Therefore, you are expected to develop an application that multiplies binary bit sequences in a way that reduces time complexity. Given two binary strings that represent value of two integers, find the product of two strings. The numbers should be 32, 64, 128, 256, 512 and 1024 bits and the result should be in decimal. For example, if the first bit string is “1000” and second bit string is “1010”, output should be “80”. You are expected to multiply two randomly generated binary numbers by classical method and given methods in algorithm1. As a result of the operations performed, you are expected to reduce the time complexity of the multiplication compared to the ordinary multiplication method. You have to show the time values in the classical method and given method. You are expected to explains which approach you see in the given algorithm.
Algortihm 1:
function multiply(x, y)
Input: Positive integers x and y, in binary
Output: Their product
n = max(size of x, size of y)
if n = 1: return xy
xL, xR = leftmost [n/2], rightmost [n/2] bits of x yL, yR = leftmost [n/2], rightmost [n/2] bits of y
P1 = multiply(xL, yL)
P2 = multiply(xR, yR)
P3 = multiply(xL + xR, yL + yR)
return P1 × 2n + (P3 − P1 − P2) × 2n/2 + P
A) Implementation (50p)
1) Formalize this problem.
You may have a look at your course slides or internet resources to find out which method you can use.
2) Reduce the result of time complexity
3) Run your algorithm and analyze the results in terms of the running time
4) Save time results (time, number of digits) and plot it in a graph for all method. (classical method vs.
given method ) (For your report)
4) Your program should compile and run using the following commands:
g++ yourStudentID.cpp –o project2
./project2 output.txt
