Integer Multiplication

Question 1

Different Integer Multiplication Algorithms

Answer 1

Regular

Divide Conquer

Karatsuba Algo

Question 2

Regular Algorithm For Integer Multiplication Input

Answer 2

Input will be two numbers in the form of an array each value corresponding to its 10th power, the Same as output

This reduces operations by multiplying by single digits and shifting resulting in the possibility of around n operations.

Question 3

Time Complexity and Space Complexity of Regular Algorithm For Integer Mul

Answer 3

Time Complex ; Theta(n^2)
Space; Theta(n)

For a long time, scientists thought it was the fastest.

Question 4

Regular Algorithm For Integer Multiplication : General

Answer 4

Grade School Multiplication

Question 5

Divide Conquer Integer Multiplication Input

Answer 5

Input: X, Y, n

Let X,Y be n-digit numbers

Question 6

Divide Conquer Integer Multiplication Time Complexity

Answer 6

Omega(n^2)

Not any better than the regular algorithm, but it is the intermediate between the fastest, Karatsuba where we use a portion of this algorithm

Question 7

Divide Conquer Integer Multiplication Algorithm

Answer 7

Function SplitMul(x, y, n)
1: if n = 1 then
2: return x · y
3: else
4: m ← ⌈n/2⌉
5: a ← ⌊x/10m⌋; b ← x mod 10m
7: c ← ⌊y/10m⌋; d ← y mod 10m
8: e ← SplitMul(a, c, m)
9: f ← SplitMul(b, d, m)
10: g ← SplitMul(b, c, m)
11: h ← SplitMul(a, d, m)
12: return 10^(2m) e + 10^m *(g + h) + f

REASON:
■ Denote m = ⌈n/2⌉,
■ Let x = (10^m · a + b) and y = (10^m · c + d),
■ Then, xy = 10^(2m)ac + 10^m(bc + ad) + bd.

Question 8

Karatsuba Algorithm Input

Answer 8

Input: X, Y, n

Let X,Y be n-digit numbers

Question 9

Karatsuba Time Complexity

Answer 9

FASTEST:
O(n^1.58)

T(n) = 3T(⌈n/2⌉) + Θ(n)
Because 1 less recursion call

Question 10

Karatsuba Algorithm

Answer 10

From Divide and Conquer we know we need xy = 10^(2m)ac + 10^m(bc + ad) + bd. To get bc + ad we do ac+bd −(a−b)(c−d) = bc+ad.
HERE IS ALGO:

Function FastMul(x, y, n)
1: if n = 1 then
2: return x · y
3: else
4: m ← ⌈n/2⌉
5: a ← ⌊x/10m⌋; b ← x mod 10m
7: c ← ⌊y/10m⌋; d ← y mod 10m
8: e ← SplitMul(a, c, m)
9: f ← SplitMul(b, d, m)
10: g ← SplitMul(a-b, c-d, m)
12: return 10^(2m) e + 10^m *(e+f-g) + f