首页 > 代码库 > 用分治法实现大数乘法，加法，减法（java实现）
用分治法实现大数乘法，加法，减法（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
由ad+bc=(a+b)(c+d)-ac-bd
原来的4次乘法和1次加法由3次乘法和2次减法代替，减少了一次乘法操作。
用同样的方法应用到abcd的乘法上。
（以上内容摘自互联网）
以下为用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,b,c,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, b, c, 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("^-", ""), y.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, x.length(), "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("1111111111", "1111111111")); }}
用分治法实现大数乘法，加法，减法（java实现）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。