首页 > 编程笔记 > Java笔记阅读：29

高精度乘法详解（Java分治法实现)

设 X 和 Y 都是 n 位十进制数，要求计算它们的乘积 XY。当 n 很大时，利用传统的计算方法求 XY 时需要的计算步骤很多，运算量较大，使用分治法求解 XY 会更高效，现要求采用分治法编写一个求两个任意长度的整数相乘的算法。

高精度乘法问题分析

设有两个大整数 X、Y，求 XY 就是把 X 与 Y 中的每一项相乘，但是这样的乘法效率较低。若采用分治法，则可将 X 拆分为 A 和 B，Y 拆分为 C 和 D，如下图所示。

图 1 大整数X和Y的分段

则：

1) 若序列 a[start…end] 中只有一个元素，则最大元素和最小元素均为 a[start]。

2) 若序列 a[start…end] 中有两个元素，则最大元素为 a[start] 和 a[end] 中的较大者，最小元素为 a[start] 和 a[end] 中的较小者。

这里取的大整数 X、Y 是在理想状态下，即 X 与 Y 的位数一致，且 n=2^m，m=1,2,3,…。计算 XY 需要进行 4 次 n/2 位整数乘法运算，即 AC、AD、BC 和 BD，以及 3 次不超过 n 位的整数加法运算，此外还要进行两次移位 2^n 和 2^(n/2) 运算，这些加法运算和移位运算的时间复杂度都为 O(n)。

根据以上分析，使用分治法求解 XY 的时间复杂度为 T(n)=4T(n/2)+O(n)，因此时间复杂度为 O(n^2)。

分治法实现高精度乘法

算法实现如下：

import java.util.Scanner;

public class BigUIntegerMul {
    void AddZero(StringBuilder s, int n, boolean pre) {
        String temp = new String();
        for (int i = 0; i < n; i++) {
            temp += "0";
        }
        if (pre) {
            s.insert(0, temp);
        } else {
            s.append(temp);
        }
    }

    void RemoveZero(StringBuilder str) {
        int i = 0;
        while (i < str.length() && str.charAt(i) == '0') {
            i++;
        }
        if (i < str.length()) {
            str.delete(0, i);
        } else {
            str = new StringBuilder("0");
        }
    }

    StringBuilder BigUIntegerAdd(StringBuilder x, StringBuilder y) {
        StringBuilder result = new StringBuilder();
        int t, m, i, size, b;
        RemoveZero(x);
        RemoveZero(y);
        x.reverse();
        y.reverse();
        m = Integer.max(x.length(), y.length());
        for (i = 0, size = 0; size != 0 || i < m; i++) {
            t = size;
            if (i < x.length()) {
                t += Integer.parseInt(String.valueOf(x.charAt(i)));
            }
            if (i < y.length()) {
                t += Integer.parseInt(String.valueOf(y.charAt(i)));
            }
            b = t % 10;
            result = new StringBuilder(String.valueOf(b) + result);
            size = t / 10;
        }
        return result;
    }

    StringBuilder BigUIntegerSub(StringBuilder x, StringBuilder y) {
        int xi, yi, i, x_size, y_size;
        int[] p;
        int count = 0;
        StringBuilder result = new StringBuilder();
        String result1 = new String();
        RemoveZero(x);
        RemoveZero(y);
        x.reverse();
        y.reverse();
        x_size = x.length();
        y_size = y.length();
        p = new int[x_size];
        for (i = 0; i < x_size; i++) {
            xi = Integer.parseInt(String.valueOf(x.charAt(i)));
            yi = i < y_size ? Integer.parseInt(String.valueOf(y.charAt(i))) : 0;
            p[count++] = xi - yi;
        }
        for (i = 0; i < x_size; i++) {
            if (p[i] < 0) {
                p[i] += 10;
                p[i + 1]--;
            }
        }
        for (i = x_size - 1; i >= 0; i--) {
            result1 += String.valueOf(p[i]);
        }
        result = new StringBuilder(result1);
        return result;
    }

    StringBuilder GetBigIntegerMul(StringBuilder X, StringBuilder Y) {
        String A, B, C, D;
        StringBuilder result, v0, v1, v2;
        int n = 2, iValue;
        if (X.length() > 2 || Y.length() > 2) {
            n = 4;
            while (n < X.length() || n < Y.length()) {
                n *= 2;
            }
            AddZero(X, n - X.length(), true);
            AddZero(Y, n - Y.length(), true);
        }
        if (X.length() == 1) {
            AddZero(X, 1, true);
        }
        if (Y.length() == 1) {
            AddZero(Y, 1, true);
        }
        if (n == 2) {
            iValue = Integer.parseInt(X.toString()) * Integer.parseInt(Y.toString());
            result = new StringBuilder(String.valueOf(iValue));
        } else {
            A = X.substring(0, n / 2);
            B = X.substring(n / 2);
            C = Y.substring(0, n / 2);
            D = Y.substring(n / 2);
            v2 = GetBigIntegerMul(new StringBuilder(A), new StringBuilder(C));
            v0 = GetBigIntegerMul(new StringBuilder(B), new StringBuilder(D));
            StringBuilder BA = BigUIntegerAdd(new StringBuilder(B), new StringBuilder(A));
            StringBuilder DC = BigUIntegerAdd(new StringBuilder(D), new StringBuilder(C));
            StringBuilder v2v0 = BigUIntegerAdd(new StringBuilder(v2), new StringBuilder(v0));
            v1 = BigUIntegerSub(GetBigIntegerMul(BA, DC), v2v0);
            AddZero(v2, n, false);
            AddZero(v1, n / 2, false);
            result = BigUIntegerAdd(BigUIntegerAdd(v2, v1), v0);
        }
        return result;
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        BigUIntegerMul BM = new BigUIntegerMul();
        System.out.println("要计算两个大整数相乘吗(y/n)？");
        String ch = sc.next();
        while (ch.equals("y") || ch.equals("Y")) {
            System.out.println("计算两个大整数相乘:");
            System.out.println("请输入第1个整数:");
            StringBuilder a = new StringBuilder(sc.next());
            System.out.println("请输入第2个整数:");
            StringBuilder b = new StringBuilder(sc.next());
            System.out.println(a + "*" + b + "=" + BM.GetBigIntegerMul(a, b));
            System.out.println("要继续计算两个大整数相乘吗(y/n)？");
            ch = sc.next();
        }
    }
}

程序运行结果如下：

要计算两个大整数相乘吗(y/n)？
y
计算两个大整数相乘：
请输入第1个整数：
123
请输入第2个整数：
456
123*456=56088
要继续计算两个大整数相乘吗(y/n)？
y
计算两个大整数相乘：
请输入第1个整数：
12345678
请输入第2个整数：
987654321
12345678*987654321=12193262222374638
要继续计算两个大整数相乘吗(y/n)？
n

在计算两个整数相乘时，需要考虑数据的存储是否超过了系统提供的整数所能表达的范围。为了求任意长度的两个整数的乘积，并在调用方法中得到被修改的数据，这里采用 StringBuilder 存储用户的输入数据。首先将整数字符串划分为长度较短的字符串，然后将其转换为整数进行运算，最后将所有划分的整数组合在一起输出。

为了方便划分，当两个整数中有一个长度大于 2 时，将整数的长度扩充为 4。

if (X.length() > 2 || Y.length() > 2) {
    n = 4;
    while (n < X.length() || n < Y.length()) {
        n *= 2;
    }
}

为扩充长度后的字符串添加字符 0：

AddZero(X, n - (int)X.length(),true);
AddZero(Y, n - (int)Y.length(),true);

当字符串长度为 2 时，结束划分，将数字字符串转换为整数进行计算：

if (n == 2) // 递归出口
{
    iValue = Integer.parseInt(X.toString()) * Integer.parseInt(Y.toString());
    result = new StringBuilder(String.valueOf(iValue));
}

将原来的整数 X 和 Y 分别划分为 A 和 B、C 和 D：

A = X.substring(0, n / 2);
B = X.substring(n / 2);
C = Y.substring(0, n / 2);
D = Y.substring(n / 2);

求解 AC、BD、(A+B)(C+D)-(AC+BD)：

v2 = GetBigIntegerMul(new StringBuilder(A), new StringBuilder(C));
v0 = GetBigIntegerMul(new StringBuilder(B), new StringBuilder(D));
StringBuilder BA = BigIntegerAdd(new StringBuilder(B), new StringBuilder(A));
StringBuilder DC = BigIntegerAdd(new StringBuilder(D), new StringBuilder(C));
StringBuilder v2v0 = BigIntegerAdd(new StringBuilder(v2), new StringBuilder(v0));
v1 = BigIntegerSub(GetBigIntegerMul(BA, DC), v2v0);

在 AC 后插入 n 个 0，即乘以 10^n：

AddZero(v2, n, false);

在 (A+B)(C+D)-(AC+BD) 后插入 n/2 个 0，即乘以 10^(n/2)：

AddZero(v1, n / 2, false);

求解 X*Y 并返回：

result = BigIntegerAdd(BigIntegerAdd(v2, v1), v0);

高精度乘法详解（Java分治法实现)

高精度乘法问题分析

分治法实现高精度乘法

相关文章