大数相乘之Karatsuba算法

问题大数相乘

计算123×456，其实12345和6789就是大数。

思路

这是分治算法思想的典型体现。计算机只会加减不会乘除的，乘法都是通过设计的算法实现的。用的是Karatsuba乘法，它是把每个大数分成2个部分，比如说大数A前面的n位分出来变成了数字a，后面的m位分出来变成了b，其实A=a×10^m+b，同理B也被拆分成了c和d。则可以推出A×B=(a×10^m+b)(c×10ⁿ+d)=a×c×10^(m+n)+a×d×10^m+b×c×10ⁿ+b×d。可以看到中间那两项因为乘方幂次不同所以不能合并，于是再分解大数的时候拆分一定要保持幂次部分相同。现在假设幂次部分都是n，则有A×B=ac×10²ⁿ+(ad+bc)×10ⁿ+bd。因为计算ad+bc的话总共需要4个乘法运算，消耗有点多。因为(a+b)(c+d)=ac+ad+bc+db==>(a+b)(c+d)-ac-bd=ad+bc。又因为ac和bd已经计算出来了所以乘法步骤被降为3步。那么现在要做的就是把ac×10²ⁿ、(ad+bc)×10ⁿ、bd这三部分，更确切地说是把ac、bd、(a+b)(c+d)-ac-bd相加了，于是大问题就被分解为小问题了。那么如何获取每个数字的长度呢？没办法只能除以10了，不过为了增加运算速度可以把长度作为参数传递给递归体的，这样以后就不用运算了。

使用

package com.company;

public class Main {

    public static void main(String[] args) {
    // write your code here
        Solution.bigNumberMultiplication(12345,6789);
    }
}

输出

乘积是:83810205

Process finished with exit code 0

实现

package com.company;

public class Solution {
    /**
     * 两个大数相乘，这是分治算法的体现。
     * @param A
     * @param B
     */
    static public void bigNumberMultiplication(int A,int B) {
        if (A < 0 || B < 0) {
            System.out.println("输入错误!");
            return;
        }
        //首先计算A和B的长度
        int aLength = Solution.getNumberLength(A);
        int bLength = Solution.getNumberLength(B);
        if (aLength == -1 || bLength == -1) {
            System.out.println("输入错误!");
            return;
        }
        System.out.println("乘积是:" + Solution.karatsuba(A,aLength,B,bLength));
    }

    /**
     * karatsuba算法
     * @param A
     * @param ALength
     * @param B
     * @param BLength
     * @return
     */
    static private int karatsuba(int A,int ALength,int B,int BLength) {
        if (ALength < 2 || BLength < 2)return A*B;
        //应该选取较大的长度除以2，因为这样可以首先把较大的数变成较小的数。
        int middleLength = 0;
        if (ALength > BLength)middleLength = ALength / 2;
        else middleLength = BLength / 2;
        int tenPower = Solution.getTenPower(middleLength);
        int a = 0,b = 0;
        int aLength = 0,bLength = 0;
        if (ALength > middleLength) {
            a = A / tenPower;
            aLength = ALength - middleLength;
            b = A % tenPower;
            bLength = middleLength;
        } else {
            a = 0;
            aLength = 0;
            b = A;
            bLength = ALength;
        }
        int c = 0,d = 0;
        int cLength = 0,dLength = 0;
        if (BLength > middleLength) {
            c = B / tenPower;
            cLength = BLength - middleLength;
            d = B % tenPower;
            dLength = middleLength;
        } else {
            c = 0;
            cLength = 0;
            d = B;
            dLength = BLength;
        }
        int aMultiplyC = Solution.karatsuba(a,aLength,c,cLength);
        int bMultiplyd = Solution.karatsuba(b,bLength,d,dLength);
        int aPlusB = a + b;
        int cPlusD = c + d;
        int aPlusBLength = Solution.getNumberLength(aPlusB);
        int cPlusDLength = Solution.getNumberLength(cPlusD);
        int aPlusBMulitiplyCPlusD = Solution.karatsuba(aPlusB,aPlusBLength,cPlusD,cPlusDLength);
        int result = aMultiplyC * tenPower * tenPower + bMultiplyd + (aPlusBMulitiplyCPlusD - aMultiplyC - bMultiplyd) * tenPower;
        return result;
    }

    /**
     * 获取10的幂次结果
     * @param length
     * @return
     */
    static private int getTenPower(int length) {
        if (length <= 0)return 1;
        else {
            int lengthCopy = length;
            int zeroCounter = 1;
            while (lengthCopy > 0) {
                lengthCopy--;
                zeroCounter *= 10;
            }
            return zeroCounter;
        }
    }

    /**
     * 获取一个数字的长度
     * @param number
     * @return
     */
    static private int getNumberLength(int number) {
        if (number < 0)return -1;
        else {
            int numberCopy = number;
            int bitCounter = 0;
            while (numberCopy > 0) {
                numberCopy /= 10;
                bitCounter++;
            }
            return bitCounter;
        }
    }
}