Go语言视频零基础入门到精通

五菱

这是一个不借助 BigInteger 来实现大数乘法的例子，顺便做了一个阶乘。

    大数乘法的实现是基于印度的格子乘法，使用这种方法，计算 m 位数乘以 n 位数只需要创建一个 m+n 位的数组保存结果即可。

当然，这种方式效率绝不可能跟 BigInteger 比，但作为初学者的练习，是很有价值的。


public class BigMultiply {   
   
    public static void main(String[] args) {   
        System.out.println(factorial("1000"));   
    }   
   
    /**  
     * 阶乘  
     *  
     * @param n 要进行阶乘的数字  
     *  
     * @return 阶乘结果  
     */  
    private static String factorial(String n) {   
        if (Integer.parseInt(n) <= 1) {   
            return "1";   
        } else {   
            return bigMultiply(n, factorial(String.valueOf(Integer.parseInt(n) - 1)));   
        }   
    }   
   
    /**  
     * 大数字乘法  
     *  
     * @param number1 数字1  
     * @param number2 数字2  
     *  
     * @return 乘法结果  
     */  
    private static String bigMultiply(String number1, String number2) {   
        short[] numbers1 = toIntArray(number1);   
        short[] numbers2 = toIntArray(number2);   
   
        short[] result = multiply(numbers1, numbers2);   
        return toString(result);   
    }   
   
    private static short[] multiply(short[] numbers1, short[] numbers2) {   
        short[] result = new short[numbers1.length + numbers2.length];   
   
        for (int i = 0; i < numbers1.length; i++) {   
            for (int j = 0; j < numbers2.length; j++) {   
                int tenth = i + j;   
                int cellResult = numbers1 * numbers2[j];   
   
                put(result, tenth + 1, cellResult % 10);   
                put(result, tenth, cellResult / 10);   
            }   
        }   
   
        return result;   
    }   
   
    /**  
     * put number into index position of result  
     *  
     * @param result -  
     * @param index  -  
     * @param number -  
     */  
    private static void put(short[] result, int index, int number) {   
        result[index] += number;   
   
        carryFrom(result, index);   
    }   
   
    /**  
     * 进位  
     *  
     * @param result 数组  
     * @param index  开始进位的位置  
     */  
    private static void carryFrom(short[] result, int index) {   
        if (index < 0) {   
            return;   
        }   
   
        if (result[index] >= 10) {   
            result[index - 1]++;   
            result[index] = (short)(result[index] - 10);   
            carryFrom(result, index - 1);   
        }   
    }   
   
    private static short[] toIntArray(String numbers) {   
        short[] result = new short[numbers.length()];   
        for (int i = 0; i < numbers.length(); i++) {   
            result = (short)(Integer.parseInt(numbers.substring(i, i + 1)));   
        }   
        return result;   
    }   
   
    private static String toString(short[] ints) {   
        int start = 0;   
        while (ints[start] == 0) {   
            start++;   
        }   
   
        String str = "";   
        while (start < ints.length) {   
            str += ints[start];   
            start++;   
        }   
   
        return str;   
    }
}
运行结果:
C:\aaa>java BigMultiply
40238726007709377354370243392300398571937486421071463254379991042993851239862902
05920442084869694048004799886101971960586316668729948085589013238296699445909974
24504087073759918823627727188732519779505950995276120874975462497043601418278094
64649629105639388743788648733711918104582578364784997701247663288983595573543251
31853239584630755574091142624174743493475534286465766116677973966688202912073791
43853719588249808126867838374559731746136085379534524221586593201928090878297308
43139284440328123155861103697680135730421616874760967587134831202547858932076716
91324484262361314125087802080002616831510273418279777047846358681701643650241536
91398281264810213092761244896359928705114964975419909342221566832572080821333186
11681155361583654698404670897560290095053761647584772842188967964624494516076535
34081989013854424879849599533191017233555566021394503997362807501378376153071277
61926849034352625200015888535147331611702103968175921510907788019393178114194545
25722386554146106289218796022383897147608850627686296714667469756291123408243920
81601537808898939645182632436716167621791689097799119037540312746222899880051954
44414282012187361745992642956581746628302955570299024324153181617210465832036786
90611726015878352075151628422554026517048330422614397428693306169089796848259012
54583271682264580665267699586526822728070757813918581788896522081643483448259932
66043367660176999612831860788386150279465955131156552036093988180612138558600301
43569452722420634463179746059468257310379008402443243846565724501440282188525247
09351906209290231364932734975655139587205596542287497740114133469627154228458623
77387538230483865688976461927383814900140767310446640259899490222221765904339901
88601856652648506179970235619389701786004081188972991831102117122984590164192106
88843871218556461249607987229085192968193723886426148396573822911231250241866493
53143970137428531926649875337218940694281434118520158014123344828015051399694290
15348307764456909907315243327828826986460278986432113908350621709500259738986355
42771967428222487575867657523442202075736305694988250879689281627538488633969099
59826280956121450994871701244516461260379029309120889086942028510640182154399457
15680594187274899809425474217358240106367740459574178516082923013535808184009699
63725242305608559037006242712434169090041536901059339838357779394109700277534720
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000

C:\aaa>