Multiplication of large integers using Divide & Conquer technique.

Multiplication of large integers

using Divide & Conquer technique:

Description:

Large integers with over 100 decimal digits long are too long to fit in a single word of a modern computer, hence require special algorithms to treat them.

ALGORITHM using Divide & Conquer method:

Let A & B be two n-digits integers where n is a positive even number.

Let

image

C2 = a1 * b1 (product of the first halves)

C0 = a0 * b0 (product of the second halves)

C1 = (a1* b0) + (a0 * b1) – (C2 + C0 ) is the product of the sum of the a’s halves and the sum of the b’s halves minus the sum of C2 & C0

Analysis:

Input size: n - number of digits

• Basic operation:

o Multiplication

o Addition

o subtraction

• No best, worst, average case

• Let M(n) be the number of multiplication’s recurrence:

image

Comments

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

Drawing Trees:HV-Layout