算法3:计算超大数字整数乘法

还不能处理负数和小数点

package s1;

import java.util.Stack;
import java.util.Vector;


/** *//**
 * A multiply simulation
 * for example : 
 * 56 X 67 = 
 *
 *     56
 *   x 67
 * ----------
 *    392
 *   336
 *------------
 *   3752
 *
 * So ,in this way,We can calculation very very big number,for example: 299^133 etc. 
 * 
 * @author Urashima 
 *
 */
public class BigNumberMultiply extends BaseNumberOperation{
    
    //each array indicates a param
    private Integer[] paramFirst,paramSecond;
    
    //main method    
    public String calculate(String param1,String param2){
        paramFirst  = convert(param1);
        paramSecond = convert(param2);
        //multiply each bit,from low to high
        int indexFirst = paramFirst.length - 1;
        int indexSecond = paramSecond.length - 1;
        //multiply results for each bit
        Vector<Integer[]> branchResults = new Vector<Integer[]>();
        for(;indexSecond > -1;indexSecond--){
            branchResults.add(branchMultiply(paramFirst,paramSecond[indexSecond]));
        }
        String finalResult = branchAddTogether(branchResults);
        return finalResult;
    }
    
    private Integer[] branchMultiply(Integer[] upper,Integer down){
        Stack<Integer> results = new Stack<Integer>();
        //todo : all core gose here
        int carryFlag = 0;
        for(int index = upper.length-1 ;index > -1;index--){
            int r1 = down;
            int r2 = upper[index];
            int r0 = r1 * r2 + carryFlag;
            carryFlag = (int)(r0/10);
            int r3 = r0 - ( 10 * carryFlag );
            if(index!=0)
                results.push(r3);
            else
                  results.push(r0);    
        }
        //sorts out and return
        Integer[] branchResult = new Integer[results.size()];
        results.toArray(branchResult);
        //System.out.println (branchResult.toString());
        return branchResult;
    }    
        
    private String branchAddTogether(Vector<Integer[]> v){
        Vector<String> params = new Vector<String>();
        //TODO: fix bug#001
        int bi = 0;
        for(Integer[] pps : v){
            //revers pps
            Integer[] rpps = new Integer[pps.length];
            System.arraycopy(pps,0,rpps,0,pps.length);
            for(int k = pps.length-1 ; k > -1 ; k-- ){
                rpps[pps.length-1-k] = pps[k];
            }
            v.set(bi++,rpps);
        }
        //sort out data,add increamental 0 to each bit
        for(Integer[] ii : v){
            String pa = "";
            for(Integer i : ii){
                pa += i;
            }
            params.add(pa);
        }     
        int incr = 0;
        for(int idx = 0 ; idx < params.size(); idx ++){
            String s = params.get(idx);
            for(int i = 0 ; i < incr ; i ++){
                s += "0";
            }
            params.set(idx,s);
            //System.out.println (s);
            incr++;
        }
        //convert back to int[]
        for(int i = 0 ; i < params.size();i++){
            String ctt = params.get(i);
            //System.out.println (ctt);
            v.set(i,convert(ctt));
        }
        //add them together    
        Stack<Integer> result;
        //trim right and add
        result = trimRightAdd(v);
        StringBuffer sb = new StringBuffer();
        try{
         while(true)
             sb.append(result.pop());
        }catch(Exception e){
            //pass,ignore.
        }
        return sb.toString();    
    }    
        
    private Stack<Integer> trimRightAdd(Vector<Integer[]> params){    
        Stack<Integer> result = new Stack<Integer>();
        int carry = 0;
        int maxBit = 0;
        
        //todo:maxbit
        for(Integer[] i : params){
            int il = i.length;
            maxBit = il > maxBit?il:maxBit;
        }
        //bit moving , from low to higth
        int indexDecreaseCount = 1;
        int columnValue = 0;
        int bitValue = 0;    
        for(int k = 0 ; k < maxBit; k++){
         if(k > 0){
             result.push(bitValue);
             columnValue = 0;
             bitValue = 0;
         }
         //value of each column,including carry    
         int num = 0;
         for(Integer[] param : params){
               int index = param.length - indexDecreaseCount;
             try{
                 num = param[index];
             }catch(Exception e){
                 num = 0;
             }
             //TODO: may be simulation calculate is better here
             columnValue += num;
         }
         //first bit
         if(k != maxBit-1 ){
             columnValue += carry;
             carry = (int)(columnValue/10);
             bitValue = columnValue - ( 10 * carry );
             indexDecreaseCount ++;
         }else{
             columnValue += carry;
             result.push(columnValue);
         }
       }
       return result;
    }    
    
}

测试计算结果

package s1;

public class Demo{
    
    private TwoNumberOperation operatorMultiply = new BigNumberMultiply();
    

评论

1 楼 清风车影 2009-10-29  

convert方法呢?程序跑不起来.