大數(shù)乘法
基本思想：
輸入字符串，轉(zhuǎn)成char數(shù)組，轉(zhuǎn)成int數(shù)組。采用分治思想，每一位的相乘;

• 公式：AB*CD = AC (BC+AD) BD

=任意位數(shù)的整數(shù)相乘，最終都是可以轉(zhuǎn)化為兩位數(shù)相乘。但是，不同位的兩位數(shù)乘的結(jié)果，最后應該如何拼接呢？這需要我們來找下更深層次的規(guī)律。分析一下四位數(shù)的乘法

             1  2  3  4 
          *  5  6  7  8 
 ------------------------ 
              9  8  7  2 
          8  6  3  8 
      7  4  0  4 
 6  1  7  0 
 ------------------------ 
 7  0  0  6  6  5  2 

結(jié)果看起來沒什么特別的，如果按照我們分治的思想，轉(zhuǎn)換為兩位數(shù)相乘，之間能否有些關系呢？
1234分為 12（高位）和34（低位）；5678分為56（高位）和78（低位）
高位高位結(jié)果：1256=672
高位低位+低位高位：1278+3456=936+1094=2840
低位低位結(jié)果：3478=2652

最后，拼接。需要說明的是，剛才我們提到兩位數(shù)分解成一位數(shù)相乘的規(guī)則：超過一位數(shù)，需要進位。同理（這里就不證明了），兩位數(shù)乘以兩位數(shù)，結(jié)果超過兩位數(shù)，也要進位。
從低位開始：低兩位：2652，26進位，低位保留52；中間兩位，2840+26（低位進位）=2866,28進位，中位保留66；高位，672+28（進位）=700,7進位，高位保留00。再往上就沒有了，現(xiàn)在可以拼接起來：最高位進位7，高兩位00，中位66，低位52，最后結(jié)果：7006652。

規(guī)律

任意位數(shù)（例如N位整數(shù)相乘），都可以用這種思想實現(xiàn)：低位保留 N 位數(shù)字串，多余高位進位；高位要加上低位進位，如果超過 N 位，依然只保留 N 位，高位進位。（如果是M位整數(shù)乘以N位整數(shù)怎么辦？高位補0，湊成一樣位數(shù)的即可，不贅述。）

代碼如下：

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
 
public class  multipliers {
 
    // 規(guī)模只要在這個范圍內(nèi)可以直接計算（整型數(shù)值滿足）
    private final static int SIZE = 4;
 
    // 其中，len為X、Y的長度最大值
    private static String bigIntMultiply(String X, String Y, int len) {
        String str = "";
 
        if (len <= SIZE) { // 少于4位數(shù)，可直接計算
            return "" + (Integer.parseInt(X) * Integer.parseInt(Y));
        }
 
        if (X.length() != Y.length()) { // 長度不同，調(diào)用formatNumber方法，補齊X、Y，使之長度相同
            X = formatNumber(X, len);
            Y = formatNumber(Y, len);
        }
 
        // 將X、Y分別對半分成兩部分
        int len1 = len / 2;
        int len2 = len - len1;
        String A = X.substring(0, len1);
        String B = X.substring(len1);
        String C = Y.substring(0, len1);
        String D = Y.substring(len1);
 
        // 乘法法則，分塊處理
        int lenM = Math.max(len1, len2);
        String AC = bigIntMultiply(A, C, len1);
        String AD = bigIntMultiply(A, D, lenM);
        String BC = bigIntMultiply(B, C, lenM);
        String BD = bigIntMultiply(B, D, len2);
 
        // 注意處理進位的方法，巧妙地運用了字符串的拼接方面
        // 【1】 處理BD，得到原位及進位
        String[] sBD = dealString(BD, len2);
        // 【2】 處理AD + BC的和
        String ADBC = add(AD, BC);
        // 【3】 加上BD的進位
        if (!"0".equals(sBD[1])) {
            ADBC = add(ADBC, sBD[1]);
        }
        // 【4】 得到ADBC的進位
        String[] sADBC = dealString(ADBC, lenM);
 
        // 【5】 AC加上ADBC的進位
        AC = add(AC, sADBC[1]);
        // 【6】 最終結(jié)果
        str = AC + sADBC[0] + sBD[0];
 
        return str;
    }
 
    // 兩個數(shù)字串按位加
    private static String add(String ad, String bc) {
        // 返回的結(jié)果
        String str = "";
 
        // 兩字符串長度要相同
        int lenM = Math.max(ad.length(), bc.length());
        ad = formatNumber(ad, lenM);
        bc = formatNumber(bc, lenM);
 
        // 按位加，進位存儲在flag中
        int flag = 0;
        // 按序從后往前按位求和
        for (int i = lenM - 1; i >= 0; i--) {
            int t = flag + Integer.parseInt(ad.substring(i, i + 1))
                    + Integer.parseInt(bc.substring(i, i + 1));
            // 結(jié)果超過9，則進位當前位，保留個位數(shù)
            if (t > 9) {
                flag = 1;
                t = t - 10;
            } else {
                flag = 0;
            }
            // 拼接結(jié)果字符串
            str = "" + t + str;
        }
        if (flag != 0) {
            str = "" + flag + str;
        }
        return str;
    }
 
    // 處理數(shù)字串，分離出進位,String數(shù)組第一個為原位數(shù)字，第二個為進位
    private static String[] dealString(String ac, int lenn) {
        String[] str = { ac, "0" };
 
        if (lenn < ac.length()) {
            int t = ac.length() - lenn;
            str[0] = ac.substring(t);
            str[1] = ac.substring(0, t);
        } else {
            // 保證結(jié)果length與lenn一致，少于則高位補0
            String result = str[0];
            for (int i = result.length(); i < lenn; i++) {
                result = "0" + result;
            }
            str[0] = result;
        }
        return str;
    }
 
    // 格式化操作的數(shù)字字符串，高位補零
    private static String formatNumber(String x, int len) {
        while (len > x.length()) {
            x = "0" + x;
        }
        return x;
    }
 
    public static void main(String[] args) {
        String pat = "^[1-9]\\d*$"; // 正則表達式：不以0開頭的數(shù)字串
        Pattern p = Pattern.compile(pat); // 將給定的正則表達式編譯并賦予給Pattern類
 
        System.out.println("乘數(shù)A（不以0開頭的正整數(shù)）：");
        Scanner sc = new Scanner(System.in);
        String A = sc.next();
        Matcher m = p.matcher(A);
 
        if (!m.matches()) {
            System.out.println("數(shù)字不合法！");
            return;
        }
 
        System.out.println("乘數(shù)B（不以0開頭的正整數(shù)）：");
        String B = sc.next();
        m = p.matcher(B);
        if (!m.matches()) {
            System.out.println("數(shù)字不合法！");
            return;
        }
        // Math.max(A.length(), B.length())比較讀入的字符串的長短
        System.out.println(A + " * " + B + " = "
                + bigIntMultiply(A, B, Math.max(A.length(), B.length())));
    }
}