Find the product of two numbers X1 = 732912 and X2 = 1026732 by using Karatsuba's Method.
Answers
Answered by
0
x = 1026732
y = 0732912.
n = 7
n/2 = 3
x = 1026 × 10³ + 732 = a × 10³ + by = 0732 × 10³ + 912 = c 10³ + d
where a = 1026
b = 732c = 0732
d = 912
Thenx × y = (1026 × 0732) 10²×³ + 732 × 912+ [(1026 + 732) × (732 + 912)- (1026 × 0732) ─ (732 × 912)]10³
= (1026 × 0732) 10⁶ + 732 × 912 +[(1758 × 1644) ─ (1026 × 0732) ─ (732 × 912)]10³
compute the products:
U = 1026 × 732V = 732 × 912P = 1758 × 1644
Let us consider only the product 1026 × 732 and other involved products may be computed similarly and substituted in (A).
U = 1026 × 732 = (10 × 10² + 26) (07 × 10² + 32)= (10 × 7) 104 + 26 × 32 + [(10 + 7) (26 + 32) -10 × 7 ─ 26 × 32)] 10²= 17 × 10⁴ + 26 × 32 + (17 × 58 ─ 70 ─ 26 × 32) 10²
At this stage, we do not apply Karatsuba’s algorithm
y = 0732912.
n = 7
n/2 = 3
x = 1026 × 10³ + 732 = a × 10³ + by = 0732 × 10³ + 912 = c 10³ + d
where a = 1026
b = 732c = 0732
d = 912
Thenx × y = (1026 × 0732) 10²×³ + 732 × 912+ [(1026 + 732) × (732 + 912)- (1026 × 0732) ─ (732 × 912)]10³
= (1026 × 0732) 10⁶ + 732 × 912 +[(1758 × 1644) ─ (1026 × 0732) ─ (732 × 912)]10³
compute the products:
U = 1026 × 732V = 732 × 912P = 1758 × 1644
Let us consider only the product 1026 × 732 and other involved products may be computed similarly and substituted in (A).
U = 1026 × 732 = (10 × 10² + 26) (07 × 10² + 32)= (10 × 7) 104 + 26 × 32 + [(10 + 7) (26 + 32) -10 × 7 ─ 26 × 32)] 10²= 17 × 10⁴ + 26 × 32 + (17 × 58 ─ 70 ─ 26 × 32) 10²
At this stage, we do not apply Karatsuba’s algorithm
Similar questions