大数相乘
发布时间：2020-12-14 02:06:18 所属栏目：大数据 来源：网络整理
导读：用分治法实现大数乘法，加法，减法（java实现） 大数乘法即多项式乘法问题，求A(x)与B(x)的乘积C(x)，朴素解法的复杂度O(n^2)，基本思想是把多项式A(x)与B(x)写成 A(x)=a*x^m+b B(x)=c*x^m+d 其中a,b,c,d为x的多项式。 则A(x)*B(x)=(ac)*x^2m+(ad+bc)*x^m+bd
用分治法实现大数乘法，加法，减法（java实现）大数乘法即多项式乘法问题，求A(x)与B(x)的乘积C(x)，朴素解法的复杂度O(n^2)，基本思想是把多项式A(x)与B(x)写成 A(x)=a*x^m+b 其中a,b,c,d为x的多项式。 （以上内容摘自互联网） 以下为用java实现的代码：
package com.kyy.sf;
public class BigInteger {
public BigInteger() {
}
// 基本思想是把多项式A(x)与B(x)写成
// A(x)=a*x^m+b
// B(x)=c*x^m+d
// 其中a,d为x的多项式。
// 则A(x)*B(x)=(ac)*x^2m+(ad+bc)*x^m+bd
// 由ad+bc=(a+b)(c+d)-ac-bd
// 字符串模拟乘法操作
public static String mut(String x,String y) {
// deep++;// Console.WriteLine("-" + deep + "-");
String negative = "";
// x,y同为正或者同为负
if ((x.startsWith("-") && y.startsWith("-"))
|| (!x.startsWith("-") && !y.startsWith("-"))) {
x = x.replaceAll("-","");
y = y.replaceAll("-","");
negative = "";
}// x,y一正一负
else if ((x.startsWith("-") && !y.startsWith("-"))
|| (!x.startsWith("-") && y.startsWith("-"))) {
x = x.replace("-","");
y = y.replace("-","");
negative = "-";
}
// 如果长度都等于于9，直接相乘，返回就行了。
if (x.length() == 1 && y.length() == 1) {
// 计算乘积
int tmp = (Integer.parseInt(x) * Integer.parseInt(y));
if (tmp == 0) {
return tmp + "";
} else {
return negative + tmp;
}
}
// 公式里的abcd
String a,d;
if (x.length() == 1) {
a = "0";
b = x;
} else {
if (x.length() % 2 != 0) {
x = "0" + x;
}
a = x.substring(0,x.length() / 2);
b = x.substring(x.length() / 2);
}
if (y.length() == 1) {
c = "0";
d = y;
} else {
if (y.length() % 2 != 0) {
y = "0" + y;
}
c = y.substring(0,y.length() / 2);
d = y.substring(y.length() / 2);
}
// 按最大位数取值，以确定补零数目
int n = x.length() >= y.length() ? x.length() : y.length();
String t1,t2,t3;
// 递归调用，根据公式计算出值。
String ac = mut(a,c);
String bd = mut(b,d);
t1 = mut(sub(a,b),sub(d,c));
t2 = add(add(t1,ac),bd);
t3 = add(add(Power10(ac,n),Power10(t2,n / 2)),bd).replaceAll("^0+","");
if (t3 == "")
return "0";
return negative + t3;
}
private static String add(String x,String y) {
if (x.startsWith("-") && !y.startsWith("-")) {
return sub(y,x.replaceAll("^-",""));
} else if (!x.startsWith("-") && y.startsWith("-")) {
return sub(x,y.replaceAll("^-",""));
} else if (x.startsWith("-") && y.startsWith("-")) {
return "-" + add(x.replaceAll("^-",""),""));
}
if (x.length() > y.length()) {
y = format(y,x.length(),"0");
} else {
x = format(x,y.length(),"0");
}
int[] sum = new int[x.length() + 1];
for (int i = x.length() - 1; i >= 0; i--) {
int tmpsum = Integer.parseInt(x.charAt(i) + "")
+ Integer.parseInt(y.charAt(i) + "") + sum[i + 1];
if (tmpsum >= 10) {
sum[i + 1] = tmpsum - 10;
sum[i] = 1;// 表示进位
} else {
sum[i + 1] = tmpsum;
}
}
StringBuilder returnvalue = new StringBuilder();
for (int i : sum) {
returnvalue.append(i);
}
if (sum[0] == 1) {
return returnvalue.toString();
} else {
return returnvalue.replace(0,1,"").toString();
}
}
// 字符串模拟减法操作
private static String sub(String x,String y) {
// x是正数，y也是正数
int flag = checkBigger(x,y);
if (flag == 0) {
return "0";
} else if (flag == -1) {
String tmp = y;
y = x;
x = tmp;
}
// 保证了x>=y
y = format(y,"0");// y补0与x对齐
int[] difference = new int[x.length()];
for (int i = x.length() - 1; i >= 0; i--) {
int tmpdifference;
tmpdifference = Integer.parseInt(x.charAt(i) + "")
- Integer.parseInt(y.charAt(i) + "") + difference[i];
if (tmpdifference < 0) {
tmpdifference += 10;
difference[i - 1] = -1;// 表示进位
}
difference[i] = tmpdifference;
}
StringBuilder returnvalue = new StringBuilder();
for (int i : difference) {
returnvalue.append(i);
}
String rv = returnvalue.toString().replaceAll("^0+","");
if ("".equals(rv)) {
return "0";
}
if (flag == -1) {
rv = "-" + rv;
}
return rv;
}
// 比较大小
private static int checkBigger(String x,String y) {
if (x.length() > y.length()) {
return 1;
} else if (x.length() < y.length()) {
return -1;
} else {
for (int i = 0; i < x.length(); i++) {
if (x.charAt(i) > y.charAt(i)) {
return 1;
} else if (x.charAt(i) < y.charAt(i)) {
return -1;
}
}
return 0;
}
}
//数据前补零
private static String format(String str,int len,String fu) {
len = len - str.length();
for (int i = 0; i < len; i++) {
str = fu + str;
}
return str;
}
// 模拟移位
public static String Power10(String num,int n) {
for (int i = 0; i < n; i++) {
num += "0";
}
return num;
}
public static void main(String[] args) {
String x = "93859048059849086850986804750894758903278473894578397598475984784857487584758094875890475984955624146039530798877974";
String y = "224343444859408590475847538946";
System.out.println(mut(x,y));
System.out.println(mut("2222222222","2222222222"));
}
}
From: http://www.cnblogs.com/kyyblabla/p/3412257.html （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |