首页 » PHP » 用PHP实现n的阶乘--高精度算法

用PHP实现n的阶乘--高精度算法

2016-03-09 20:40:01阅读(436)

今天在IT届,最火的新闻莫过于李世石输给了alphago。看到新闻说,“围棋有361个落子点,所以下棋有10^171种可能。”然后我就突然想361的阶乘是多少呢?即

361*360*359*358*......*5*4*3*2*1 = ?

于是自己用php实现了一下算法。代码如下:

<?php
    $result = "1";
    for($i = 1; $i <= 361; $i++){
        $val = strval($i);
        $result = bigNumMulty($result, $val);
    }
    echo $result."\n";

    //两个大数相乘,$num1和$num2都是string型的
    function bigNumMulty($num1, $num2){
        $len1 = strlen($num1);
        $len2 = strlen($num2);
        $zeroNum1 = 0;
        $result = '0';
        for($i = $len1 - 1; $i >= 0; $i--){
            $zeroNum2 = 0;
            for($j = $len2 - 1; $j >= 0; $j--){
                $data = stringMulty($num1[$i], $num2[$j]);
                $data .= addZero($zeroNum1 + $zeroNum2);
                $result = bigNumAdd($result, $data);
                $zeroNum2++;
            }
            $zeroNum1++;
        }
        return $result;
    }

    //两个大数相加,$num1和$num2都是string型的
    function bigNumAdd($num1, $num2){
        $len1 = strlen($num1);
        $len2 = strlen($num2);
        $result = '';
        if($len1 > $len2){
            $big = $num1;
            $small = $num2;
            $blen = $len1;
            $slen = $len2;
        }else{
            $blen = $len2;
            $slen = $len1;
            $big = $num2;
            $small = $num1;
        }
        $ten = 0;
        for($i = 0; $i < $slen; $i++){
            $data = stringAdd($big[$blen - $i - 1], $small[$slen - $i - 1], $ten);
            $ten = intval($data / 10);
            $single = intval($data % 10);
            $result = strval($single) . $result;
        }
        for(; $i < $blen; $i++){
            $data = stringAdd($big[$blen - $i - 1], '0', $ten);
            $ten = intval($data / 10);
            $single = intval($data % 10);
            $result = strval($single) . $result;
        }
        if($ten)
            $result = '1'.$result;
        return $result;
    }

    //string型数据相加
    function stringAdd($num1, $num2, $ten){
        $int1 = intval($num1);
        $int2 = intval($num2);
        $int3 = intval($ten);
        $result = $int1 + $int2 + $int3;
        return $result;
    }

    //string型数据相乘
    function stringMulty($num1, $num2){
        $int1 = intval($num1);
        $int2 = intval($num2);
        $result = $int1 * $int2;
        return strval($result);
    }

    //为string型数据后面加0
    function addZero($num){
        $result = '';
        while($num){
            $result .= '0';
            $num--;
        }
        return $result;
    }

不过这个算法计算的时间相当久。。。35分钟。。。
最终结果如下:
1437923258884890654832362511499863354754907538644755876127282765299227795534389618856841908003141196071413794434890585968383968233304321607713808837056557879669192486182709780035899021100579450107333050792627771722750412268086775281368850575265418120435021506234663026434426736326270927646433025577722695595343233942204301825548143785112222186834487969871267194205609533306413935710635197200721473378733826980308535104317420365367377988721756551345004129106165050615449626558110282424142840662705458556231015637528928999248573883166476871652120015362189137337137682618614562954409007743375894907714439917299937133680728459000034496420337066440853337001284286412654394495050773954560000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹