大整数乘法

对于位数不超过10位的整数而言，可以直接使用运算符做乘法，但是遇到更大的整数只能使用数组来模拟运算。

这里总结了二进制表示的大整数的乘法。

假设u和v是两个二进制大整数，如果直接相乘，需要$O(n^2)$的时间复杂度，当然思路也是十分清晰的，直接把每一位相乘得到的数字加起来就好。

也可以使用分治的思想来实现乘法，并且如果能够使用移位指令的话，时间复杂度能够降低到$O(n^{1.59})$，（但我不知道怎么实现o(╥﹏╥)o）。

所以借用了算法的思想，使用数组来实现了大整数乘法，只是时间复杂度就难以估算了，在不能移位的情况下，应该也是$O(n^2)$的级别。

主要思想

要求得u乘v的结果，可以把两者拆成两半，分别求出其结果后，再根据化简公式得到uv的值。很显然，最小的解（或者说能够直接得到的解）是u ，v的长度都为1时，uv等价于u & v，又因为每个子问题之间是相互独立的，因此采用自顶向下，分而治之的方法。

• 如何划分成两半？

  需要分奇偶讨论，当u,v为奇数时，$u=w2^{(n+1)/2}+x$, $v=y2^{(n-1)/2}+z$。

  当u,v为偶数时，$u=w2^{n/2}+x$，$v=y2^{n/2}+z$。

  

• 如何通过划分得到的值计算uv?

  化简乘法公式就好，使用乘法分配律后得到：偶数时$uv = wy2^n + (wz+xy)2^{n/2}+xz$。奇数时同理。

• 如何用数组表示w,x,y,z？

  创建一个新的数组，把要保留的位赋值给它们，然后返回其引用就好。

• 当n= 1 时怎么处理？

  很明显，划分到最后所有的数组长度都为1，这时如果另一个相乘的数的数组长度不为1，可以继续划分直到两个数组的长度都为1，也可以直接进行计算后返回值，这里就继续采用分治思想，将其划分成最小的解后再进行计算。由于n=1为奇数，因此可以划分成它本身和一个0值，在处理和0相乘的数时直接返回0就好。

还有一点要注意的是，在划分的过程中可能出现很多位数组长度的0值，这时需要清除掉数组中多余的0。

代码实现

函数的详细功能见每个函数之前的注释：

package DivideConquer;

import java.util.Random;

public class BigNum {
    byte[] number;

    /**
     * Use the recursion algorithm to implement the product of two big numbers.
     * <p>
     * Assume that we have two binary numbers:u and v. And then we can seperate each
     * to the higher bits and lower bits.For example, u can be considered as two
     * parts-- w in high bits and x in low bits. The number v can be also considered
     * as y in high bits and z in low bits.
     * <p>
     * To get the product of uv, you can use this formula:
     * 
     * <pre>
     * uv = wy * 2 ^ (n) + (wz + xy) * 2 ^ (n / 2) + xz
     * </pre>
     * <p>
     * Then get the value of wy,wz,xy,xz with recursion until the length of the
     * number is 1, whose result is itself. We can implement the moveLeft function
     * to get the value of x * 2^(n).
     * 
     * @param a
     * @return the product of this and a.
     */
    public BigNum multiply(BigNum v) {
        if (this.isZero() || v.isZero()) {
            return new BigNum(1);
        }
        if (this.isOne() && v.isOne()) {
            return new BigNum("1");
        }
        BigNum u = this;
        int lenU = u.getLength();
        int lenV = v.getLength();
        // BigNum result = new BigNum(lenU + lenV);
        int hLenU, lLenU;
        int hLenV, lLenV;
        if (lenU % 2 == 1) {
            hLenU = (lenU + 1) / 2;
            lLenU = (lenU - 1) / 2;
        } else {
            hLenU = lenU / 2;
            lLenU = lenU / 2;
        }

        if (lenV % 2 == 1) {
            hLenV = (lenV + 1) / 2;
            lLenV = (lenV - 1) / 2;
        } else {
            hLenV = lenV / 2;
            lLenV = lenV / 2;
        }
        BigNum w = u.clearTail(lLenU);
        BigNum x = u.clearHead(hLenU);
        BigNum y = v.clearTail(lLenV);
        BigNum z = v.clearHead(hLenV);
        // System.out.println("u:" + u + " v:" + v);
        // System.out.println("w:" + w + " x:" + x + " y:" + y + " z:" + z);

        BigNum wy = w.multiply(y);
        BigNum wz = w.multiply(z);
        BigNum xy = x.multiply(y);
        BigNum xz = x.multiply(z);

        // System.out.println("wy:" + wy + " wz:" + wz + " xy:" + xy + " xz:" + xz);

        BigNum uv = wy.moveLeft(lLenU + lLenV).add(wz.moveLeft(lLenU)).add(xy.moveLeft(lLenV)).add(xz);

        // System.out.println("uv:" + uv + "\n");
        return uv;
    }

    /**
     * Add two big numbers with each bit.
     * 
     * @param a
     * @return sum
     */
    public BigNum add(BigNum a) {
        this.trimHead();
        a.trimHead();
        int lenG = a.getLength() > this.getLength() ? a.getLength() : this.getLength();
        // int lenL = a.getLength() < this.getLength() ? a.getLength() :
        // this.getLength();
        BigNum result = new BigNum(lenG + 1);
        int i, j, k;
        int cf = 0;
        i = this.getLength() - 1;
        j = a.getLength() - 1;
        k = result.getLength() - 1;
        while (i >= 0 && j >= 0) {
            int tmp = cf + this.getInt(i) + a.getInt(j);
            result.setByte(k, tmp % 2);
            cf = tmp / 2;
            i--;
            j--;
            k--;
        }
        BigNum lagerNum;
        if (i < 0) {
            lagerNum = a;
            i = j;
        } else {
            lagerNum = this;
        }
        while (i >= 0) {
            int tmp = cf + lagerNum.getInt(i);
            result.setByte(k, tmp % 2);
            cf = tmp / 2;
            i--;
            k--;
        }
        if (cf != 0) {
            result.setByte(k, 1);
        }
        return result.trimHead();
    }

    /**
     * trim the higher zero.
     * 
     * @return
     */
    public BigNum trimHead() {
        if (this.isZero()) {
            return new BigNum(1);
        }
        int k = 0;
        while (this.getInt(k) == 0) {
            k++;
        }
        int len = this.getLength() - k;
        BigNum result = new BigNum(len);
        for (int i = 0; i < result.getLength(); i++) {
            result.setByte(i, number[k]);
            k++;
        }

        return result;
    }

    /**
     * Clear the low n bits of the number.
     * 
     * @param n
     * @return
     */
    public BigNum clearTail(int n) {
        int length = this.getLength() - n;
        if (length == 0) {
            return new BigNum(1);
        }
        BigNum result = new BigNum(length);
        for (int i = 0; i < length; i++) {
            result.setByte(i, number[i]);
        }
        return result.trimHead();
    }

    /**
     * Clear the high n bits of the number.
     * 
     * @param n
     * @return
     */
    public BigNum clearHead(int n) {
        int length = this.getLength() - n;
        if (length == 0) {
            return new BigNum(1);
        }
        BigNum result = new BigNum(length);
        for (int i = n, k = 0; i < number.length; i++, k++) {
            result.setByte(k, number[i]);
        }
        return result.trimHead();
    }

    /**
     * Imitate the move left operator in binary numbers.
     * 
     * 
     * @param n digit to move
     * @return Big number having been moved left
     */
    BigNum moveLeft(int n) {
        int newLength = number.length + n;
        BigNum bigNum = new BigNum(newLength);
        int i = 0;
        for (i = newLength - 1; i >= (newLength - n); i--) {
            bigNum.setByte(i, 0);
        }
        for (int j = 0; j < number.length; j++) {
            bigNum.setByte(j, number[j]);
        }

        return bigNum.trimHead();
    }

    public BigNum(int n) {
        number = new byte[n];
        for (int i = 0; i < number.length; i++) {
            this.setByte(i, 0);
        }
    }

    /**
     * initiate object by String
     * 
     * @param s
     */
    public BigNum(String s) {
        number = new byte[s.length()];

        for (int i = 0; i < s.length(); i++) {
            number[i] = Byte.parseByte(s.substring(i, i + 1));
        }
    }

    /**
     * change number[index] to Integer
     * 
     * @param index
     * @return
     */
    public int getInt(int index) {
        return Byte.toUnsignedInt(number[index]);
    }

    public int toInteger() {
        int result = 0;
        int k = 1;
        for (int i = this.getLength() - 1; i >= 0; i--) {
            result += this.getInt(i) * k;
            k *= 2;
        }
        return result;
    }

    public int getLength() {
        return number.length;
    }

    public void setByte(int index, int x) {
        number[index] = Byte.parseByte(Integer.toString(x));
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < number.length; i++) {
            builder.append(Byte.toString(number[i]));
        }
        return builder.toString();
    }

    public boolean isZero() {
        for (int i = 0; i < number.length; i++) {
            if (this.getInt(i) == 1) {
                return false;
            }
        }
        return true;
    }

    public boolean isOne() {
        return this.getLength() == 1 && this.getInt(0) == 1;
    }

    /**
     * Get a random big binary number
     * 
     * @param n the digit of the binary number
     * @return
     */
    public static BigNum getRandomNum(int n) {
        Random random = new Random();
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            builder.append(Integer.toString(random.nextInt(2)));
        }
        BigNum result = new BigNum(builder.toString());
        return result;
    }

}