大数乘法

论坛看到的一个面试题，实现任意大整数字符串相乘，返回结果字符串

package org.jf.alg;

/**  
 *   
 * 大数乘法  
 * @author junfeng.chen  
 *  
 */  
public class BigIntegerMultipl    
{   
  
    /**  
     *   
     * @param s1 整型乘数字符串  
     * @param s2 整型乘数字符串  
     * @return 整型字符串结果  
     *   
     * s1=a[1]a[2]a[3]....a[n]  
     * s2=b[1]b[2]b[3]....b[n]  
     * 分别将两个字符串拆分，得到两个字符数组   
     * char[] charArray1={a[1],a[2]....a[n]}  
     * char[] charArray2={b[1],b[2]....b[n]}  
     *   
     *   
     * 乘法步骤：  
     * 1. a[1]*{b[1],b[2],b[3]...b[n]}-->得到一个字符数组  array1  
     * 2. a[1]*{b[2],b[3],b[4],...b[n]}-->得到字符数组 array2  
     * array1 与 array2 错一位按位求和   
     * array1[0] array1[1] array1[2] ...array1[n]  
     *           array2[0] array2[1] ...array2[n-1] array2[n]  
     * --->新的结果数组 array3  
     */  
    public static String multiplie(String s1,String s2)//   
    {   
  
    	
    	int prex = 1;
    	if(s1.charAt(0)>'9'||s1.charAt(0)<'0')
    	{
    		if(s1.charAt(0)=='-')
    			prex *= -1;
    		else if(s1.charAt(0)!='+')
    			throw new RuntimeException("Illeagle Argumets");
    		s1=s1.substring(1);
    			
    	}
    	
    	if(s2.charAt(0)>'9'||s2.charAt(0)<'0')
    	{
    		if(s2.charAt(0)=='-')
    			prex *= -1;
    		else if(s2.charAt(0)!='+')
    			throw new RuntimeException("Illeagle Argumets");
    		s2=s2.substring(1);	
    	}
    	
    	
      	if(!s1.matches("\\d+")||!s2.matches("\\d+"))
    		throw new RuntimeException("Illeagle Argumets");
    	
    	
        char [] array1=new char[s1.length()];   
        char [] array2= new char[s2.length()];   
        for(int i=0;i<s1.length();i++)   
        {   
            array1[i] = s1.charAt(s1.length()-i-1);   
        }   
        for(int i=0;i<s2.length();i++)   
        {   
            array2[i] = s2.charAt(s2.length()-i-1);   
        }   
           
        char [] rs1 = null;   
        for(int i=0;i<array2.length;i++)   
        {   
            char result[] = new char[array1.length+1];   
            int extr = 0;//进位   
            int m2 = Integer.parseInt(array2[i]+"");   
            int j=0;   
            for(;j<array1.length;j++)   
            {   
                int m1 = Integer.parseInt(array1[j]+"");   
                int r = m1*m2+extr;   
                result[j] = (char)(48+(r%10));   
                extr = r/10;   
            }   
            result[j] = (char)(48+extr);   
            extr = 0;   
       
           
            if(i==0)   
                rs1 = result;   
            else//rs1 与 result 错i位按位求和     
            {   
                char rs2[] = new char[result.length+i+1];   
                rs2[result.length+i]='0';   
                rs2[result.length+i-1]='0';   
                   
                for(int k=0;k<i;k++)   
                {   
                    rs2[k] = rs1[k];   
                       
                }   
                int m = i;   
                for(int n=0;n<result.length;n++,m++)   
                {   
                    int x2 = Integer.parseInt(result[n]+"");   
                    int x1 = 0;   
                    if(m<rs1.length)   
                    {   
                       x1 = Integer.parseInt(rs1[m]+"");   
                    }   
                    int r = x1+x2+extr;   
                    extr = r/10;   
                    rs2[m] = (char)(48+r%10);   
                }   
                   
                for(int l=m+1;l<rs2.length;l++)   
                {   
                    rs2[l] = (char)48;   
  
                }   
                   
                rs1 = rs2;   
            }   
                   
        }   
           
           
        String str = "";   
        int i = rs1.length-1;   
        while(rs1[i]=='0')   
        {   
            i--;   
        }   
        for(;i>=0;i--)   
        {   
           str = str+rs1[i];   
        }   
  
        if(prex==-1)
        	str='-'+str;
        return str;   
    }   
       
       
    public static void main(String args[])   
    {   
    	System.out.println(BigIntegerMultipl.multiplie("c123", "c123"));
        System.out.println(BigIntegerMultipl.multiplie("12","99"));   
        System.out.println(BigIntegerMultipl.multiplie("-345","987"));   
        System.out.println(BigIntegerMultipl.multiplie("3450","210"));   
        System.out.println(BigIntegerMultipl.multiplie("9999999999","121212121212121212121212129999999991919191929293949595959"));   
           
    }   
}  

评论

7 楼 cjf068 2012-02-13  

这个算法的基本思路，是小学3年级的 算法，就是简单的把乘法运算转换成多次的加法运算。

简单来说，假设第一个数是m位，第二个数是n位，最后计算出来就需要m*n次的乘法，然后再相加。
这个算法是相当粗糙的。

对于这个问题，实际上可以做这样的分解。
就是讲两个大数的乘法，转换成几个相对小数的乘法，然后再相加。但这里的小数是相对的小数，不能直接拆分到一个字符一个字符来计算，这样的算法效率太低了。

举个例子来说吧。假设我们已经可以计算出所有5位数的乘法结果，得到一个相当于99乘法表的乘法计算结果。

这时如果要计算两个10位数的乘法，就可以将两个10位数的乘法计算，转换成4个5位数的乘法计算，以及3次相加结果。那么在这种情况下，因为5位数的乘法已经计算出来了，不需要重新计算，查找一下结果就可以了。整个计算的效率才能得到提升。

liujunsong 写道

这个算法的基本思路，是小学3年级的 算法，就是简单的把乘法运算转换成多次的加法运算。

简单来说，假设第一个数是m位，第二个数是n位，最后计算出来就需要m*n次的乘法，然后再相加。
这个算法是相当粗糙的。

对于这个问题，实际上可以做这样的分解。
就是讲两个大数的乘法，转换成几个相对小数的乘法，然后再相加。但这里的小数是相对的小数，不能直接拆分到一个字符一个字符来计算，这样的算法效率太低了。

举个例子来说吧。假设我们已经可以计算出所有5位数的乘法结果，得到一个相当于99乘法表的乘法计算结果。

这时如果要计算两个10位数的乘法，就可以将两个10位数的乘法计算，转换成4个5位数的乘法计算，以及3次相加结果。那么在这种情况下，因为5位数的乘法已经计算出来了，不需要重新计算，查找一下结果就可以了。整个计算的效率才能得到提升。

明白你的意思，谢谢，我之前想过，这里只是简单实现了一下，没考虑性能问题，有时间再优化一下，事实上，存储也可以用链表做

6 楼 liujunsong 2012-02-12  

这个算法的基本思路，是小学3年级的 算法，就是简单的把乘法运算转换成多次的加法运算。

简单来说，假设第一个数是m位，第二个数是n位，最后计算出来就需要m*n次的乘法，然后再相加。
这个算法是相当粗糙的。

对于这个问题，实际上可以做这样的分解。
就是讲两个大数的乘法，转换成几个相对小数的乘法，然后再相加。但这里的小数是相对的小数，不能直接拆分到一个字符一个字符来计算，这样的算法效率太低了。

举个例子来说吧。假设我们已经可以计算出所有5位数的乘法结果，得到一个相当于99乘法表的乘法计算结果。

这时如果要计算两个10位数的乘法，就可以将两个10位数的乘法计算，转换成4个5位数的乘法计算，以及3次相加结果。那么在这种情况下，因为5位数的乘法已经计算出来了，不需要重新计算，查找一下结果就可以了。整个计算的效率才能得到提升。

5 楼 shuidexiongdi 2012-02-08  

去年我也写了一个
http://shuidexiongdi.iteye.com/admin/blogs/1144176

4 楼 cjf068 2012-02-07  

wait10000y 写道

要严谨,先判断字符串是否符合要求,结尾还要验证结果是否正确的,最后再分析一下可行性...

如何验证？这个还真不知道，字符串检查到时必须

3 楼 chansman 2012-02-07  

大学的时候我也弄过,但是除法没弄出来.

2 楼 wait10000y 2012-02-07  

要严谨,先判断字符串是否符合要求,结尾还要验证结果是否正确的,最后再分析一下可行性...

1 楼 chasingdeer 2012-02-07  

直接用BigDecimal不就行了