大数相乘

小咪咪 2022-08-19 15:12 184阅读 0赞

# [用分治法实现大数乘法，加法，减法（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"));
    
    
        }
    }

From: http://www.cnblogs.com/kyyblabla/p/3412257.html

[java]: http://www.cnblogs.com/kyyblabla/p/3412257.html