如果觉得再简述上阅读代码太困难可以点这里：大整数相乘问题
假设数字X,Y均为二进制整数，求解X*Y的值，使用分治的思想：
上图显示了递归的公式，但是上述的算法的时间复杂度仍旧是T(n) = 4 * T(n / 2) + θ(n) =O(n^2),这个和通过使用小学数学计算方法的时间复杂度是一样的，这样使用分治的思想并没有改进算法的执行效率，
这个时候，我们可以换位思考一下，将公式变形为:XY=AC2^n+[(A-B)(D-C)+AC+BD]2^n/2+BD
这个时候我们能发现:时间复杂度为：T(n) = 3 * T(n / 2) + θ(n) =O(n^1.59 )
/**
* 大整数相乘
*
*/
public class Multiplication {
public String X=Integer.toBinaryString(44444);
public String Y=Integer.toBinaryString(1151);
//大整数相乘
public int getProduct() {
String answer=muilt(X, Y);
return Integer.valueOf(answer,2);
}
//递归函数 X*Y=AC2^n+[(A-B)(D-C)+AC+BD]2^n/2+BD
public String muilt(String x,String y) {
if(x.length()>y.length()) {
x=append0(x, x.length());
y=append0(y, x.length());
}else {
x=append0(x, y.length());
y=append0(y, y.length());
}
String A=x.substring(0, x.length()/2);
String B=x.substring(x.length()/2,x.length());
String C=y.substring(0, y.length()/2);
String D=y.substring(y.length()/2,y.length());
if(A.length()==0||B.length()==0||C.length()==0||D.length()==0) {
return "0";
}
if(A.length()<=4||B.length()<=4||C.length()<=4||D.length()<=4) {
int a=Integer.valueOf(A,2);
int b=Integer.valueOf(B,2);
int c=Integer.valueOf(C,2);
int d=Integer.valueOf(D,2);
int xy=(int) (a*c*Math.pow(2, B.length()+D.length())+((a-b)*(d-c)+a*c+b*d)*Math.pow(2, D.length())+b*d);
return Integer.toBinaryString(xy);
}
String AC=muilt(A, C);
String BD=muilt(B, D);
String A_B = Integer.toBinaryString(Integer.valueOf(A,2)-Integer.valueOf(B,2));
String D_C = Integer.toBinaryString(Integer.valueOf(D,2)-Integer.valueOf(C,2));
//当A-B或D-C小于零时 使用Integer.valueOf(A_B,2);将会产生异常
try {
Integer ab = Integer.valueOf(A_B,2);
Integer dc = Integer.valueOf(D_C,2);
} catch (NumberFormatException e) {
//处理异常
int a=Integer.valueOf(A,2);
int b=Integer.valueOf(B,2);
int c=Integer.valueOf(C,2);
int d=Integer.valueOf(D,2);
int xy=(int) (a*c*Math.pow(2, B.length()+D.length())+((a-b)*(d-c)+a*c+b*d)*Math.pow(2, D.length())+b*d);
return Integer.toBinaryString(xy);
}
String coe=muilt(A_B,D_C); //(A-B)(D-C);
int XY=(int) (Integer.valueOf(AC,2)*Math.pow(2, B.length()+D.length())+(Integer.valueOf(coe,2)+Integer.valueOf(BD,2)+Integer.valueOf(AC,2))*Math.pow(2, D.length())+Integer.valueOf(BD,2));
return Integer.toBinaryString(XY);
}
public static void main(String[] args) {
Multiplication multiplication=new Multiplication();
// System.out.println(multiplication.X);
// System.out.println(multiplication.X.substring(multiplication.X.length()/2,multiplication.X.length()));
// System.out.println(multiplication.X.substring(0,multiplication.X.length()/2));
// System.out.println(multiplication.Y);
long a=4554211*1151;
System.out.println(a);
System.out.println(Integer.valueOf(multiplication.X,2)*Integer.valueOf(multiplication.Y,2));
// System.out.println(Integer.valueOf("0000110",2));
System.out.println(multiplication.getProduct());
}
public String append0(String str,int len) {
while (len%4!=0) {
len++;
}
// System.out.println(len);
String newStr=str;
for(int i=str.length();i<len;i++) {
newStr="0"+newStr;
}
return newStr;
}
}
如果代码出现问题，欢迎大家指出。
网友评论