where the amazing happens

算法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();
    
    
public void multiplyDemo(String param1,String param2){
        String result 
= operatorMultiply.calculate(param1,param2);
        System.out.println (param1
+" x "+param2+" = "+result);
    }

    
    
public static void main (String[] args) {
        Demo demo 
= new Demo();
        demo.multiplyDemo(
"12","12");
        demo.multiplyDemo(
"56","67");
        demo.multiplyDemo(
"3459398","11667278");
        demo.multiplyDemo(
"9283736253829832323432342342543654576343534564353734534534534534534553773453453453453453455377345345345345345345537734534534534534534553773453453453453453455377345345345345345345537734534534534534534553745645545",
                          
"23470926947345345345345345345537734534534534534534553773453453453453453455377345345345345345345537734534534534534534553773453453453453453455377345345345345345345537734534534534534534553773453453453453453455377345345345345345345537863053758734076407083760987207345345345345345345537693709479");
    }

    
}


--------------------Configuration: <Default>--------------------
12 x 12 = 144
56 x 67 = 3752
3459398 x 11667278 = 40361758178644
9283736253829832323432342342543654576343534564353734534534534534534553773453453453453453455377345345345345345345537734534534534534534553773453453453453453455377345345345345345345537734534534534534534553745645545 x 23470926947345345345345345345537734534534534534534553773453453453453453455377345345345345345345537734534534534534534553773453453453453453455377345345345345345345537734534534534534534553773453453453453453455377345345345345345345537863053758734076407083760987207345345345345345345537693709479 = 217897895412061538535213749538424917178427642790309526149197050342787946552594940694811082625513148107368458788645637103672066743646902872289253339664141494118086813947265391829794894470256056436951017797373234350763998817946444452982381515332165838866556971112151531240855136817304521889160157930869290050844235614446072972714978233006835557537630008993034139267140464023218920328137852716504553853724234899138660678581541565601300563516326950021051186577024411324340905167953542819936071934540621055

Process completed.

posted on 2006-09-25 20:40 where the amazing happens 阅读(1359) 评论(1)  编辑  收藏 所属分类: 算法&数据结构

评论

# re: 算法3:计算超大数字整数乘法 2006-12-26 09:33 zy

这个程序你没有给全吗?能给我个完整的程序吗,太感谢拉!   回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航:
 

公告

点击这里给我发消息

导航

<2006年9月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

统计

常用链接

留言簿(3)

随笔分类(18)

随笔档案(17)

文章分类

相册

其他我的blog

技术Blog

最新随笔

搜索

最新评论

阅读排行榜

评论排行榜