WikiGalaxy
Karatsuba Multiplication
Introduction:
Karatsuba multiplication is an algorithm that multiplies two n-digit numbers in less than O(n2) time. It uses a divide-and-conquer approach to break down the problem into smaller sub-problems, which are then solved recursively.
Example 1: Basic Multiplication
Problem:
Multiply 1234 by 5678 using Karatsuba's method.
Solution:
1. Split each number into two halves:
- 1234 -> a = 12, b = 34
- 5678 -> c = 56, d = 78
2. Compute the three products:
- ac = 12 * 56
- bd = 34 * 78
- (a+b)(c+d) = (12+34)(56+78)
3. Use the formula:
- Result = ac * 104 + ((a+b)(c+d) - ac - bd) * 102 + bd
public class KaratsubaExample {
public static void main(String[] args) {
long x = 1234;
long y = 5678;
System.out.println(karatsuba(x, y));
}
public static long karatsuba(long x, long y) {
if (x < 10 || y < 10) return x * y;
int n = Math.max(Long.toString(x).length(), Long.toString(y).length());
int m = n / 2;
long a = x / (long) Math.pow(10, m);
long b = x % (long) Math.pow(10, m);
long c = y / (long) Math.pow(10, m);
long d = y % (long) Math.pow(10, m);
long ac = karatsuba(a, c);
long bd = karatsuba(b, d);
long abcd = karatsuba(a + b, c + d);
return ac * (long) Math.pow(10, 2 * m) + (abcd - ac - bd) * (long) Math.pow(10, m) + bd;
}
}
Console Output:
7006652
Example 2: Larger Numbers
Problem:
Multiply 123456 by 789012 using Karatsuba's method.
Solution:
1. Split each number into two halves:
- 123456 -> a = 123, b = 456
- 789012 -> c = 789, d = 12
2. Compute the three products:
- ac = 123 * 789
- bd = 456 * 12
- (a+b)(c+d) = (123+456)(789+12)
3. Use the formula:
- Result = ac * 106 + ((a+b)(c+d) - ac - bd) * 103 + bd
public class KaratsubaExample {
public static void main(String[] args) {
long x = 123456;
long y = 789012;
System.out.println(karatsuba(x, y));
}
public static long karatsuba(long x, long y) {
if (x < 10 || y < 10) return x * y;
int n = Math.max(Long.toString(x).length(), Long.toString(y).length());
int m = n / 2;
long a = x / (long) Math.pow(10, m);
long b = x % (long) Math.pow(10, m);
long c = y / (long) Math.pow(10, m);
long d = y % (long) Math.pow(10, m);
long ac = karatsuba(a, c);
long bd = karatsuba(b, d);
long abcd = karatsuba(a + b, c + d);
return ac * (long) Math.pow(10, 2 * m) + (abcd - ac - bd) * (long) Math.pow(10, m) + bd;
}
}
Console Output:
97408265472
Example 3: Uneven Lengths
Problem:
Multiply 12345 by 678901 using Karatsuba's method.
Solution:
1. Split each number into two halves:
- 12345 -> a = 123, b = 45
- 678901 -> c = 6789, d = 01
2. Compute the three products:
- ac = 123 * 6789
- bd = 45 * 01
- (a+b)(c+d) = (123+45)(6789+01)
3. Use the formula:
- Result = ac * 106 + ((a+b)(c+d) - ac - bd) * 103 + bd
public class KaratsubaExample {
public static void main(String[] args) {
long x = 12345;
long y = 678901;
System.out.println(karatsuba(x, y));
}
public static long karatsuba(long x, long y) {
if (x < 10 || y < 10) return x * y;
int n = Math.max(Long.toString(x).length(), Long.toString(y).length());
int m = n / 2;
long a = x / (long) Math.pow(10, m);
long b = x % (long) Math.pow(10, m);
long c = y / (long) Math.pow(10, m);
long d = y % (long) Math.pow(10, m);
long ac = karatsuba(a, c);
long bd = karatsuba(b, d);
long abcd = karatsuba(a + b, c + d);
return ac * (long) Math.pow(10, 2 * m) + (abcd - ac - bd) * (long) Math.pow(10, m) + bd;
}
}
Console Output:
838102845
Example 4: Small Numbers
Problem:
Multiply 12 by 34 using Karatsuba's method.
Solution:
1. Since both numbers are less than 10, use direct multiplication.
public class KaratsubaExample {
public static void main(String[] args) {
long x = 12;
long y = 34;
System.out.println(karatsuba(x, y));
}
public static long karatsuba(long x, long y) {
if (x < 10 || y < 10) return x * y;
int n = Math.max(Long.toString(x).length(), Long.toString(y).length());
int m = n / 2;
long a = x / (long) Math.pow(10, m);
long b = x % (long) Math.pow(10, m);
long c = y / (long) Math.pow(10, m);
long d = y % (long) Math.pow(10, m);
long ac = karatsuba(a, c);
long bd = karatsuba(b, d);
long abcd = karatsuba(a + b, c + d);
return ac * (long) Math.pow(10, 2 * m) + (abcd - ac - bd) * (long) Math.pow(10, m) + bd;
}
}
Console Output:
408
Example 5: Edge Case
Problem:
Multiply 0 by 123456 using Karatsuba's method.
Solution:
1. Any number multiplied by 0 is 0. The algorithm handles this by returning 0 when either input is less than 10 and equals 0.
public class KaratsubaExample {
public static void main(String[] args) {
long x = 0;
long y = 123456;
System.out.println(karatsuba(x, y));
}
public static long karatsuba(long x, long y) {
if (x < 10 || y < 10) return x * y;
int n = Math.max(Long.toString(x).length(), Long.toString(y).length());
int m = n / 2;
long a = x / (long) Math.pow(10, m);
long b = x % (long) Math.pow(10, m);
long c = y / (long) Math.pow(10, m);
long d = y % (long) Math.pow(10, m);
long ac = karatsuba(a, c);
long bd = karatsuba(b, d);
long abcd = karatsuba(a + b, c + d);
return ac * (long) Math.pow(10, 2 * m) + (abcd - ac - bd) * (long) Math.pow(10, m) + bd;
}
}
Console Output:
0
