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
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:
Comments
Post a Comment