How to implement the factorial of n in php

php method to implement the factorial of n: 1. Implement it through ordinary recursion, with code such as "function fact(int $n): int{...}"; 2. Implement it with ordinary loops, with code such as " while ($num

The operating environment of this article: Windows 10 system, PHP version 7.2.15, DELL G3 computer

How does php realize the factorial of n?

As far as I know, the implementation methods of factorial can generally be divided into three types. Recursion and looping in the usual sense are each considered one type, and there is also a large category that uses some clever mathematical methods to reduce the number of operations ( Especially the number of multiplication operations), thereby optimizing computing efficiency.

If you want to consider the factorial of high-precision, large integers, the situation will be more complicated for the PHP language. For example, when using some methods provided by the BCMath extension, explicit number and string conversion operations are compared. frequently.

This article only considers n as an integer, and attempts to implement the above situations respectively. Available code examples are given in each case, and a comprehensive comparison of several methods is attached at the end of the article.

Ordinary recursive implementation

The first is the ordinary recursive implementation. According to the general recursive formula fact(n) = n * fact(n-1), it is easy to write the factorial calculation code. The advantage of ordinary recursive implementation is that the code is relatively concise, and the same process as the general formula makes the code easy to understand. The disadvantage is that because it needs to call itself frequently, a large number of push and pop operations are required, and the overall calculation efficiency is not high (see the table at the end of the article).

function fact(int $n): int
{
    if ($n == 0) {
        return 1;
    }
    return $n * fact($n - 1);
}

Ordinary loop implementation

Ordinary loop implementation has the flavor of "dynamic programming", but due to the low frequency of use of intermediate state variables, no additional storage space is required, so It is simpler than the general dynamic programming algorithm. The ordinary recursive method is a top-down (from n to 1) calculation process, while the ordinary loop is a bottom-up calculation.

Therefore, relatively speaking, the code is not as intuitive as the above method, but due to the lack of frequent push and pop processes, the calculation efficiency will be higher (see the table at the end of the article).

function fact(int $n): int
{
    $result = 1;
    $num = 1;
    while ($num <= $n) {
        $result = $result * $num;
        $num = $num + 1;
    }
    return $result;
}

Self-implemented large integer factorial

Due to the range limitation of the int type in PHP, the above two methods can only accurately calculate factorials up to 20. If you only consider the factorial of 20, it will be faster to use the lookup table method: calculate the factorial of 0-20 in advance and store it in an array, and query it once when needed.

In order to be able to adapt to the factorial of large numbers and obtain accurate calculation results, this article is improved based on the "ordinary loop method", using an array to store each bit in the calculation result (from low to high), and multiplying The carry method calculates the result of each bit in turn.

It goes without saying that the advantage of this method is that it can be applied to high-precision large number factorial situations. The disadvantage is that for decimal factorials, the calculation process is complicated and slow.

function fact(int $n): array
{
    $result = [1];
    $num = 1;
    while ($num <= $n) {
        $carry = 0;
        for ($index = 0; $index < count($result); $index++) {
            $tmp = $result[$index] * $num + $carry;
            $result[$index] = $tmp % 10;
            $carry = floor($tmp / 10);
        }
        while ($carry > 0) {
            $result[] = $carry % 10;
            $carry = floor($carry / 10);
        }
        $num = $num + 1;
    }
    return $result;
}

BCMath Extension Method

BCMath is a mathematical extension for PHP that handles numerical computations on numbers (of any size and precision) represented by strings. Since it is an extension implemented in C language, the calculation speed will be faster than the above self-implementation.

Recommended study: "PHP Video Tutorial"

On my laptop, I also calculate the factorial of 2000. It takes an average of 0.5-0.6 seconds to implement it by myself. Use BCMath takes 0.18-0.19 seconds. The main disadvantage of this method is that it requires the installation of corresponding extensions, which is a non-code level change. For applications where environmental management upgrades are inconvenient, the practicality is questionable.

function fact(int $n): string
{
    $result = '1';
    $num = '1';
    while ($num <= $n) {
        $result = bcmul($result, $num);
        $num = bcadd($num, &#39;1&#39;);
    }
    return $result;
}

Optimization Algorithm

As mentioned at the beginning of this article, the optimization algorithm tries to reduce the number of operations (especially the number of multiplication operations) as much as possible to achieve fast factorial. Considering that for small integer factorials, the fastest algorithm should be the table lookup method, with a time complexity of O(1), so this section mainly discusses and tests the exact factorial of large integers.

It is understood that factorial optimization is currently more common through n! = C(n, n/2) * (n/2)! * (n/2)! Complexity optimization, and The highlight of this formula mainly lies in the optimization of C(n, n/2). Considering that in the case of large integers, the efficiency of the PHP language to implement C(n, n/2) is not high, and the code readability is relatively poor (frequent explicit conversion of numbers and strings), so this article uses Another more clever method.

The calculation speed of multiplication is usually lower than that of addition and subtraction. By reducing the number of multiplication operations, the overall calculation speed can be improved. Through mathematical induction, we can find that for the factorial of n, we can successively find values ​​that are 1, 1 3, 1 3 5... smaller than (n/2)^2, and then multiply them in sequence to obtain the target value.

The advantage of this algorithm is that the calculation speed is fast, but the disadvantage is that the implementation process is not intuitive and difficult to understand. After testing, the following code calculates the factorial average time of 2000 to 0.11 seconds, which is about half the time of the ordinary loop method.

In addition to this method of optimization, we have also seen other similar ideas, such as repeatedly checking whether the numbers in 1...n are divisible by 2, recording the number of times divisible by 2 x, and trying to generalize Find the common odd number multiplication formula, and finally multiply it by 2^x to get the result.

function fact(int $n): string
{
    $middleSquare = pow(floor($n / 2), 2);
    $result = $n & 1 == 1 ? 2 * $middleSquare * $n : 2 * $middleSquare;
    $result = (string)$result;
    for ($num = 1; $num < $n - 2; $num = $num + 2) {
        $middleSquare = $middleSquare - $num;
        $result = bcmul($result, (string)$middleSquare);
    }
    return $result;
}

综合对比

本文中提到的方法是按照由劣到优的顺序，因此，下列表格中每一行中提到优劣势，主要是和其上一两种方法对比。

表格中「测试耗时」一列的测试环境为个人笔记本，硬件配置为 Dell/i5-8250U/16GB RAM/256GB SSD Disk，软件配置为 Win 10/PHP 7.2.15。

总结

虽然本文将实现方法分为三大类，但其实也可以分为循环和递归两大类，在这两类中分别使用相应的算法优化计算效率。But，总体而言，循环的效率要优于递归。

讲道理，本文中使用的优化算法并不是最优解，只是用 PHP 相对好实现，代码易读性也比较高。有兴趣的读者可以谷歌了解更多的骚操作。

The above is the detailed content of How to implement the factorial of n in php. For more information, please follow other related articles on the PHP Chinese website!