-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKaratsuba.java
More file actions
42 lines (35 loc) · 1.01 KB
/
Karatsuba.java
File metadata and controls
42 lines (35 loc) · 1.01 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.math.BigInteger;
import java.util.Arrays;
public class Karatsuba {
// x = 10^(n/2) a + b
// y = 10^(n/2) c + d
// x * y = 10^n ac + 10^(n/2)(ad + bc) + bd
// Note that:
// sumMul - ac - bd = ad + bc
// where sumMul = (a+b)(c+d)
public static int mul(int x, int y){
if( x <= 10 && y <= 10 ){
return x*y;
}
// digits : longer length of x, y
int digits = numlength(x) > numlength(y) ? numlength(x) : numlength(y);
int sub = digits / 2;
int sub10 = (int) Math.pow(10, sub);
int a = x / sub10; int b = x % sub10;
int c = y / sub10; int d = y % sub10;
int ac = mul(a,c);
int bd = mul(b,d);
int sumMul = mul(a+b,c+d);
int mid = sumMul - ac - bd;
return ac*sub10*sub10 + mid*sub10 + bd;
}
private static int numlength(int n)
{
if (n == 0) return 1;
int l;
n=Math.abs(n);
for (l=0;n>0;++l)
n/=10;
return l;
}
}