分治策略-大整数相乘

 

分治策略是一种设计高效算法的有力范型。该方法首先将问题划分成两个较小的子问题,每个子问题除了输入规模较小以外,其他都与原问题是一样的。然后分别解决这两子问题,最后子问题的解合并成为原问题的最终解。

 

一般地,分治算法由三步组成。

步骤1:如果问题规模较小,那么使用某种方法直接解决它;否则,划分问题成两个子问题,最好以相同的规模划分。

步骤2:对子问题使用分治算法递归地解决这两个子问题。

步骤3:合并子问题的解成为原问题的解。

 

问题描述:

按照一般方法计算大数乘法,就是按照手工算法的方式,逐位相乘,两个n位长度的数字相乘,乘法次数为O(n²)。如果减少乘法,增加加法,时间复杂度会降低,通过分治法,两个n位长度的数字相乘,乘积次数可以减少到O(nlog3)。

bignum图1

 

此时,有四次n/2长度的乘积(B*D,A*D,B*C,A*B),四次10进制位移,移动n/2位,三次加法。忽略位移,时间复杂度 T(n)。

公式1

将X*Y分解后仍然需要n²次乘法,12(logn-1)+3   次加法,忽略加法,乘积复杂度仍为O(n²)。进一步分解公式,减少乘法次数。

公式2

第二次分解之后,有三次乘积,六次加/减法,两次位移。忽略位移,时间复杂度T(n)。

公式3

这种分解方法,需要 n^log3 次乘法,3(logn-1)*6+6次加法,忽略加法,乘积复杂度降低为O(n^1.58)。

关键函数如下:
1、大整数乘法函数,输入两个字符串

public StringBuilder multi(StringBuilder x, StringBuilder y)

2、大整数加法函数

public StringBuilder addBigNums(StringBuilder n1, StringBuilder n2)

3、大整数减法函数

public StringBuilder minusBigNums(StringBuilder d, StringBuilder c)

 

运行结果如下:

运行结果

 

 

代码如下:

public class Main {
    public static void main(String[] args) {
        StringBuilder x = new StringBuilder();
        StringBuilder y = new StringBuilder();
        x.append("12345678912345678912345678989123458912345891234589123458912345");
        y.append("12345678912345891234589123458912345891234589123458912345");
        MultiplyLargeNums m = new MultiplyLargeNums();
        System.out.print(  x + " * \n" + y + "\n = \n");
        StringBuilder r = m.multiply(x, y);

        System.out.println(m.getSigh()+""+r);

 
  }
}





/**
 * Created by chris on 15/5/9.
 * devide and conquer 解决大整数相乘问题
 * AB*CD = (A*10^(n/2)+B)(C*10^(n/2)+D) =BD+10^(n/2)((A+B)(D+C) - BD-AC) +AC*10^n
 * 对每一个乘积继续分解
 */
public class MultiplyLargeNums {
    private char sigh;

    public char getSigh() {
        return sigh;
    }

    public StringBuilder multiply(StringBuilder x, StringBuilder y) {
        sigh = getSign(x, y);
        processSign(x);
        processSign(y);

        return multi(x, y);
    }


    StringBuilder multi(StringBuilder x, StringBuilder y) {


        //make sure x.length is bigger
        if (y.length() > x.length())
            return multi(y, x);

        //凑成偶数位相乘,e.g. 123*45=>0123 * 0045
        if (x.length() != 1 || y.length() != 1) {
            if (x.length() % 2 == 0 && y.length() % 2 != 0 || x.length() % 2 == 0 && y.length() % 2 == 0) {
                for (int i = 0; i < x.length() - y.length(); i++) {
                    y.insert(0, 0);
                }
            } else if (x.length() % 2 != 0 && y.length() % 2 == 0 || x.length() % 2 != 0 && y.length() % 2 != 0) {
                x.insert(0, 0);
                for (int i = 0; i < x.length() - y.length(); i++) {
                    y.insert(0, 0);
                }
            }
        } else if (x.length() != 1 && y.length() == 1) {
            if (x.length() % 2 == 0) {
                for (int i = 0; i < x.length() - y.length(); i++) {
                    y.insert(0, 0);
                }
            } else {
                x.insert(0, 0);
                for (int i = 0; i < x.length() - y.length(); i++) {
                    y.insert(0, 0);
                }
            }
        }


        StringBuilder a = new StringBuilder();
        StringBuilder b = new StringBuilder();
        StringBuilder c = new StringBuilder();
        StringBuilder d = new StringBuilder();

        if (x.length() == 1 && y.length() == 1) {
            long result = (x.charAt(0) - '0') * (y.charAt(0) - '0');
            return new StringBuilder(result + "");
        } else if (x.length() == 1 && y.length() > 1) {
            a.append(0);
            b.append(x);
            c.append(y.substring(0, y.length() / 2));
            d.append(y.substring(y.length() / 2) + 1);

        } else if (x.length() > 1 && y.length() == 1) {
            c.append(0);
            d.append(x);
            a.append(y.substring(0, x.length() / 2));
            b.append(y.substring(x.length() / 2) + 1);


        } else {
            a.append(x.substring(0, x.length() / 2));
            b.append(x.substring(x.length() / 2));
            c.append(y.substring(0, y.length() / 2));
            d.append(y.substring(y.length() / 2));

        }

        //BD+10^(n/2)((A+B)(D+C) - BD-AC) +AC*10^n
        StringBuilder ab = multi(a, b);
        StringBuilder bd = multi(b, d);
        StringBuilder ac = multi(a, c);

        StringBuilder aPlusb = addBigNums(a, b);
        StringBuilder dPlusc = addBigNums(d, c);

        StringBuilder mul = multi(aPlusb, dPlusc);

        StringBuilder r = minusBigNums(minusBigNums(mul, bd), ac);

        StringBuilder tmp = shift(r, x.length() / 2);
        StringBuilder result = addBigNums(addBigNums(tmp, shift(ac, x.length())), bd);

        return clearZero(result);
    }

    /**
     * delete sign
     */
    private int processSign(StringBuilder x) {
        if (x == null || x.length() == 0)
            return -1;
        if (x.charAt(0) == '+' || x.charAt(0) == '-')
            x.deleteCharAt(0);
        return 0;

    }
    /**
     * add 0 to simulate multiply 10
     * */
    private StringBuilder shift(StringBuilder r, int i) {

        for (int j = 0; j < i; j++) {
            r.append(0);
        }
        return r;
    }


    /**
     * 大数相加
     */

    public StringBuilder addBigNums(StringBuilder n1, StringBuilder n2) {
        if (n1.length() < n2.length())
            return addBigNums(n2, n1);

        int length1 = n1.length();
        int length2 = n2.length();
        int carry = 0;
        StringBuilder result = new StringBuilder();
        while (length1 >= 1 && length2 >= 1) {
            int out = (n1.charAt(--length1) - '0') + (n2.charAt(--length2) - '0') + carry;
            carry = out / 10;
            result.insert(0, out % 10);

        }
        while (length1 >= 1) {
            int out = carry + n1.charAt(--length1) - '0';
            carry = out / 10;
            result.insert(0, out % 10);
        }
        if (length1 <= 0 && carry != 0) {
            result.insert(0, carry);
        }

        return result;
    }

    /**
     * 大数相减法,d-c
     */
    public StringBuilder minusBigNums(StringBuilder d, StringBuilder c) {
        d = clearZero(d);
        c = clearZero(c);

        int larger = compare(d, c);
        char sign = larger == 1   '+' : '-';
        if (larger == 0)
            return new StringBuilder(0);

        else if (larger > 0) {
            return minus(d, c);
        } else {
            return minus(c, d).insert(0, sign);
        }


    }

    /**
     * delete all  prefix zero like 000123=>123
     */
    private StringBuilder clearZero(StringBuilder c) {
        int i = 0;
        while (i < c.length() && c.charAt(i) == '0') {
            i++;
        }
        return new StringBuilder(c.substring(i));

    }

    /**
     * 大整数减法,大减小
     */
    private StringBuilder minus(StringBuilder big, StringBuilder little) {

        StringBuilder result = new StringBuilder();
        int j = little.length() - 1;
        for (int i = big.length() - 1; i >= 0; i--) {
            if (j >= 0 && big.charAt(i) >= little.charAt(j)) {
                result.append(big.charAt(i) - little.charAt(j));
                j--;
            } else if (j >= 0 && big.charAt(i) < little.charAt(j)) {
                result.append(big.charAt(i) + 10 - little.charAt(j));

                if (i - 1 >= 0 && big.charAt(i - 1) > '0') {
                    int replace = big.charAt(i - 1) - 1;
                    big.setCharAt(i - 1, (char) replace);
                } else {
                    int k = 1;
                    while (i - k >= 0 && big.charAt(i - k) == '0') {
                        big.setCharAt(i - k, '9');
                        k++;
                    }
                    if (i - k >= 0 && big.charAt(i - k) != '0')
                        big.setCharAt(i - k, (char) (big.charAt(i - k) - 1));
                }
                j--;
            } else {
                result.append(big.charAt(i));
            }


        }
        return clearZero(result.reverse());

    }

    /**
     * 比较数字串d,c的大小,
     * d > c return 1; d==c return 0 ;d < c return -1
     */
    private int compare(StringBuilder d, StringBuilder c) {
        if (d.length() > c.length())
            return 1;
        else if (d.length() < c.length())
            return -1;
        else {
            int index = 0;
            while (index < d.length() && d.charAt(index) == c.charAt(index))
                index++;
            if (index == d.length())
                return 0;
            else {
                return d.charAt(index) > c.charAt(index)   1 : -1;
            }
        }
    }

    /**
     * 两数字乘积结果正负性
     */
    private char getSign(StringBuilder x, StringBuilder y) {
        String a = x.toString().trim();
        String b = y.toString().trim();
        int signA = (a.charAt(0) > '0' && a.charAt(0) < '9' || a.charAt(0) == '+')   1 : -1;
        int signB = b.charAt(0) == '-'   -1 : 1;

        return signA * signB == -1   '-' : '+';
    }
}

Tagged on:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>