查找大量阶乘的快速方法 [英] Quick way to find a factorial of a large number

问题描述

这是我的程序，但是对于10万这样的大数字，它的运行速度非常慢，是否有优化的选择?

This is my program, but for really large numbers like 100,000, it works very slowly, is there any option to optimize?

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        BigInteger sum = BigInteger.valueOf(1);

        for (BigInteger i = BigInteger.valueOf(n);
             i.compareTo(BigInteger.ZERO) > 0;
             i = i.subtract(BigInteger.ONE)) {

            sum = sum.multiply(i);
        }

        System.out.println(sum);    
    }

}

推荐答案

只是为了说明有时为操纵表达式而付出的代价，我修改了计算1 * 2 * 3 * ... * n的标准乘法循环来打破它它分为两部分:一部分将奇数整数相乘(1 * 3 * 5 * ...)，另一部分将偶数相乘(2 * 4 * 6 * ...).通过乘以0 mod 2但 not 0 mod 4(例如2 * 6 * 10 * ...)的偶数，再乘以0 mod 4的偶数，可进一步细分偶数乘积 not 0 mod 8(例如4 * 12 * 20 * 28 * ...)，依此类推，但是2的幂首先移出该数字.乘以2的幂，然后乘积最后一次向左移.这充分利用了Java 8 BigInteger的实现方式，以使大型左移相当有效.

Just to illustrate that it sometimes pays to manipulate the expression, I modified the standard multiplication loop that computes 1*2*3*...*n to break it into two parts: one part multiplies the odd integers together (1*3*5*...) and the other multiplies the evens together (2*4*6*...). The evens product is further broken down by multiplying the evens that are 0 mod 2 but not 0 mod 4 (e.g. 2*6*10*...), then the evens that are 0 mod 4 but not 0 mod 8 (e.g. 4*12*20*28*...) and so on, but the power of 2 is shifted out of the number first. The powers of two are counted up, and the product is then shifted left all at once at the end. This takes advantage of the how the Java 8 BigInteger is implemented to make large left shifts fairly efficient.

private static BigInteger fac4(int n) {

    BigInteger evens = multiplyEvens(n);
    BigInteger odds = multiplyOdds(n);
    BigInteger product = evens.multiply(odds);
    return product;
}

private static BigInteger multiplyOdds(int n) {
    BigInteger odds = BigInteger.ONE;
    for (long i=1; i<=n; i+=2) {
        odds = odds.multiply(BigInteger.valueOf(i));
    }
    return odds;
}

private static BigInteger multiplyEvens(int n) {
    BigInteger evens = BigInteger.ONE;
    long pow2 = 1;
    int shiftAmount = 0;
    while ((1 << pow2) <= n) {
        for (long i = (1<<pow2); i <= n; i += (1 << (pow2 + 1))) {
            shiftAmount += pow2;
            evens = evens.multiply(BigInteger.valueOf(i >> pow2));
        }
        ++pow2;
    }
    return evens.shiftLeft(shiftAmount);
}


public static void main(String[] args) {
    // Print out some small factorials to verify things are working
    for (int i = 0; i < 10; i++) {
        System.out.printf("%d! = %d%n", i, fac4(i));
    }

    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    long start = System.currentTimeMillis();
    BigInteger fac = fac4(n);
    long end = System.currentTimeMillis();
    float total = end - start;

    System.out.printf("%d! is %d bits long, took %f seconds to compute", n, fac.bitLength(), total / 1000);
}

这是一次n = 100000的输入/输出日志:

Here is the input/output log for one run of n=100000:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
100000
100000! is 1516705 bits long, took 1.758000 seconds to compute

为进行比较，我实现直接多循环的过程大约花费了3秒钟.

For comparison, my implementation of the straightforward multiple loop took about 3 seconds.

这是我尝试过的另一个实现，它甚至更快.这个想法是要利用这样一个事实，即当乘法的操作数足够大以提供优势时，Java 8+ BigInteger包含渐近地比O(n ² )算法快的事实.但是，幼稚的方法总是将单个肢体"整数乘以快速增长的累积乘积.这种方法不适用于更快的算法.但是，如果我们乘以近似相等的操作数，则可以使用更快的算法.

Here is another implementation I tried that was even faster. The idea is to take advantage of the fact that Java 8+ BigInteger includes asymptotically faster than O(n²) algorithms when the operands of multiply get big enough to provide an advantage. However, the naive method always multiplies a single 'limb' integer by a rapidly growing accumulated product. This approach is not amenable to the faster algorithms. However, if we multiply approximately equal operands then the faster algorithms are possible.

private static final int SIMPLE_THRESHOLD = 10;
private static BigInteger fac6(int n) {
    return subfac(1, n);
}

/**
 * compute a * (a+1) * ... *(b-1) * b
 * The interval [a,b] includes the endpoints a and b.
 *
 * @param a the interval start.
 * @param b the interval end, inclusive.
 * @return the product.
 */
private static BigInteger subfac(int a, int b) {
    if ((b-a) < SIMPLE_THRESHOLD) {
        BigInteger result = BigInteger.ONE;
        for (int i=a; i<=b; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    } else {
        int mid = a + (b-a) / 2;
        return subfac(a, mid).multiply(subfac(mid+1, b));
    }

}

使用与上述相同的main()方法的输出为:

And the output using the same main() method as above was:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
100000
100000! is 1516705 bits long, took 0.243000 seconds to compute

所以fac6()几乎是fac4()的10倍.一些实验表明，SIMPLE_THRESHOLD的值对速度几乎没有影响，这大概是因为函数调用的开销与BigInteger乘法的开销相形见

So fac6() is almost 10 times faster than fac4(). A few experiments suggest that the value of SIMPLE_THRESHOLD has very little effect on the speed, presumably because the overhead of function call is dwarfed by the cost of the BigInteger multiplication.

所有这些实验都是使用JDK 1.8.0_181在Mac OS X High Sierra笔记本电脑上运行的.

All these experiments were run on a Mac OS X High Sierra laptop using JDK 1.8.0_181.

这篇关于查找大量阶乘的快速方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！