摘要：使用分治法來(lái)實(shí)現(xiàn)大整數(shù)相乘相乘的基本原理如第一步分解和和第二步分別計(jì)算首部中部尾部第三步進(jìn)位因?yàn)槭且詢晌粩?shù)字分割的，所以進(jìn)位是滿進(jìn)一位尾部留，進(jìn)，即中部，留，進(jìn)，即首部，即第四步重組首部中部尾部分治法思想將這樣的算式分解成和接下來(lái)使用遞

相乘的基本原理

如： 1234 * 567

第一步：分解
   234 -> 12 和 34;
   567 -> 5 和 67;

第二步：分別計(jì)算 
   首部: 12*5=60
   中部：12*67+34*5=974
   尾部：34*67=2278

第三步：進(jìn)位（因?yàn)槭且詢晌粩?shù)字分割的，所以進(jìn)位是滿100進(jìn)一位）
   尾部：留78，進(jìn)22，即78
   中部：974+22=996，留96，進(jìn)9，即96
   首部：60+9=69，即69

第四步：重組
   首部+中部+尾部：699678

分治法思想

將 2135415134543*4573756875685 這樣的算式分解成 2135415*4573756、2135415*875685+4573756*134543和134543*875685,接下來(lái)使用遞歸再分解即可。

數(shù)據(jù)的對(duì)象類型

    如：123
    NumberObject {
        number:"321"，
        length:3,
        sign:1
    }

注意事項(xiàng)
1、每個(gè)函數(shù)的用法源碼中有注釋
2、存貯的字符串是數(shù)字的倒序，如輸入"123"，存儲(chǔ)為"321",計(jì)算時(shí)也是用"321"
3、測(cè)試函數(shù)為test(x,y),x和y必須為字符串類型才能進(jìn)行計(jì)算大整數(shù)的相乘

源代碼

    // 整數(shù)的構(gòu)造函數(shù)
    function NumberObject( string , sign ) {
        if( sign === -1){
    
            this.number = reverseString( string.slice(1) );
            this.length = string.length - 1;
        }    
        else if ( sign === 1){
    
            this.number = reverseString( string );
            this.length = string.length;
    
        }else{
    
            alert("The sign of the number is wrong!");
            // 程序停止
            // stop();
        }
        this.sign = sign;
    }
    
    // 字符串顛倒 (傳入字符串， 傳出字符串)
    function reverseString(string){
        return string.split("").reverse().join("");
    }
    
    // 補(bǔ)零 (傳入字符串， 傳出字符串)
    function addFrontZero( string , length ){
        for(let i = 0; i < length; i++){
            if(i > string.length - 1){
                string += "0";
            }
        }
        return string;
    }
    
    
    // 去零 (傳入字符串，傳出字符串)
    function deleteFrontZero( string ){
        
        let arr = string.split("");
    
        let end = arr.length - 1;
    
        while( arr[end--] === "0" ){
            arr.pop();
        }
    
        if(arr.length === 0){
            arr.push("0");
        }
        
        return arr.join("");
    }
    
    // 將參數(shù)統(tǒng)一轉(zhuǎn)換為字符串
    function numberTransform(number) {
    
        switch(typeof number){
            case "number":
                return String(number);
            case "object":
                return number.reverse().join("");
            case "undefined":
                alert("you didn"t input the number.");
            default:
                return number;
        }
    
    }
    
    // 分析元素
    function numberAnalysis( number ) {
    
        let raw = numberTransform( number );
        
        if( raw[0] != "-" && raw[0] < "0" || raw[0] >"9"){
            alert("The number you input is wrong.");
        }
    
        for(let i = 1; i < raw.length; i++){
            if(raw[i] < "0" || raw[0] > "9"){
                alert("The number you input is wrong.");
            }
        }
    
        if( raw[0] === "-" ){
            return new NumberObject( raw ,  -1);
        }else{
            return new NumberObject( raw , 1 );
        }
    
    }
    
    
    // 數(shù)字相加，（傳入字符串，傳出字符串）
    function addString( first, second ) {
    
        let carry = 0,
             rst = [];
        let length = first.length > second.length ? first.length : second.length;
        
        // 第一個(gè)加數(shù)
        let fst = addFrontZero(first, length);
        // 第二個(gè)加數(shù)
        let scd = addFrontZero(second, length);
    
        for(let i = 0; i < length || carry === 1; i++){
    
            if( fst[i] && scd[i] ){
    
                rst[i]   = ( (fst[i] - 0)  +  (scd[i] - 0)  + carry ) % 10;
                carry  = ( (fst[i] - 0)  +  (scd[i] - 0)  + carry ) / 10;
    
            }else if( !fst[i] && scd[i] ){
    
                rst[i]   = ( (scd[i] - 0) + carry ) % 10;
                carry  = ( (scd[i] - 0) + carry ) / 10;
    
            }else if( fst[i] && !scd[i] ){
    
                rst[i]   = ( (fst[i] - 0) + carry ) % 10;
                carry  = ( (fst[i] - 0) + carry ) / 10;
    
            }else if( !fst[i] && !scd[i] && carry === 1){
                
                rst[i]   = carry;
                carry  = 0;
            }else{
                alert("The logic of your addition is wrong.");
            }
    
            // JS 的商一般都為小數(shù)，需要取整
            carry = Math.floor( carry );
        }
        return rst.join("");
    }
    
    function multiply( first , second ) {
        
        // 返回的字符串結(jié)果和判斷符號(hào)
        let firstNumber = first.number;
        let secondNumber = second.number;
    
    
        let rst = pieceOfMultiplication( firstNumber , secondNumber ).split("");
    
        // 判斷正負(fù)號(hào)
        if(first.sign * second.sign === -1){
            rst.push("-");
        }
    
        return new numberAnalysis( rst );
    
    }
    
    // 實(shí)現(xiàn)分治法
    function pieceOfMultiplication( first, second ) {
        
        let length = first.length > second.length ? first.length : second.length;
        
        // 補(bǔ)零，使得位數(shù)相同
        for(let i = 0; i < length; i++){
            if(i > first.length - 1){
                first.number += "0";
            }
            if(i > second.length - 1){
                second.number += "0";
            }
        }
    
        let half = Math.floor( length / 2 );
        
        // 分割數(shù)字
        let firstLeft = first.slice(0, half);
        let firstRight = first.slice( half );
        let secondLeft = second.slice(0, half);
        let secondRight = second.slice( half );
        
    
        // 遞歸長(zhǎng)度大于2的數(shù)相乘
        if( half >= 2 ) {
            
            // 分解
            let leftRst = pieceOfMultiplication( firstLeft , secondLeft );
            let centerRst = addString( pieceOfMultiplication( firstLeft , secondRight ) , pieceOfMultiplication( firstRight , secondLeft ) );
            let rightRst = pieceOfMultiplication( firstRight , secondRight );
    
            leftRst = deleteFrontZero(String(leftRst));
            centerRst = deleteFrontZero(String(centerRst));
            rightRst = deleteFrontZero(String(rightRst));
    
    
            // 重組
            let left = leftRst.slice(0, half);
            let leftCarry = leftRst.slice(half);
    
    
            centerRst = addString(centerRst , leftCarry);
    
            let center = centerRst.slice(0, half);
            let centerCarry = centerRst.slice(half);
            
    
    
            let right = addString(rightRst , centerCarry);
    
    
            return deleteFrontZero(left + center + right);
    
        }
        // 兩位數(shù)相乘
        else if( half === 1) {
            // 一位或兩位的字符串轉(zhuǎn)數(shù)字
            let firstLeftNumber = Number(reverseString( firstLeft ));
            let firstRightNumber = Number(reverseString( firstRight ));
            let secondLeftNumber = Number(reverseString( secondLeft ));
            let secondRightNumber = Number(reverseString( secondRight ));
            
    
            // 相乘
            let leftRstNumber = firstLeftNumber * secondLeftNumber;
            let centerRstNumber = firstLeftNumber * secondRightNumber + secondLeftNumber * firstRightNumber;
            let rightRstNumber = firstRightNumber * secondRightNumber;
    
            
            // 重組
            let left = leftRstNumber % 10;
            let centerRst = Math.floor(leftRstNumber / 10) + centerRstNumber;
            let center = centerRst % 10;
            let right = Math.floor(centerRst / 10) + rightRstNumber;
    
    
            left = deleteFrontZero(reverseString( String(left) ));
            center = deleteFrontZero(reverseString( String(center) ));
            right = deleteFrontZero(reverseString( String(right) ));
            return deleteFrontZero( left + center + right );
    
        }
    
        else {
            alert("The multiplication is wrong");
        }
    
    }
    
    // 規(guī)定： 傳入的x 和 y 數(shù)據(jù)類型必須為字符型，因?yàn)榇笳麛?shù)為默認(rèn)判定為數(shù)字上限
    function test(x, y) {
    
        let elem1 = numberAnalysis( x );
        let elem2 = numberAnalysis( y );
    
        let rst = multiply( elem1 , elem2 )
        
        if(rst.sign === -1){
            return "-" + reverseString( rst.number );
        }
        else if(rst.sign === 1){
            return reverseString( rst.number );
        }
    
    }