如何计算21!(21阶乘)快速？

Question

我正在制作快速计算阶乘的函数.像这样

func factorial(factorialNumber: UInt64) -> UInt64 {
    if factorialNumber == 0 {
        return 1
    } else {
        return factorialNumber * factorial(factorialNumber - 1)
    }
}

let x = factorial(20)

这个功能可以计算直到20.

我认为factorial(21)的值大于UINT64_MAX.

然后如何计算21!(21阶乘)快速？

Answer 1

func factorial(_ n: Int) -> Double {
  return (1...n).map(Double.init).reduce(1.0, *)
}

1. (1...n)：我们创建了一个包含操作中涉及的所有数字的数组（即：）[1, 2, 3, ...]。

2. map(Double.init)：我们从Int改为Double因为我们可以用双精度表示比整数更大的数字（https://en.wikipedia.org/wiki/Double-precision_floating-point_format）。因此，我们现在将操作中涉及的所有数字的数组作为Doubles（即：）[1.0, 2.0, 3.0, ...]。

3. reduce(1.0, *)：我们开始繁殖1.0与阵列（在第一元件1.0*1.0 = 1.0），那么那与下一个的（结果1.0*2.0 = 2.0），则其与所述下一个（结果2.0*3.0 = 6.0），依此类推。

第 2 步是避免溢出问题。

第 3 步是避免我们显式定义用于跟踪部分结果的变量。

Answer 2

无符号64位整数的最大值为18,446,744,073,709,551,615。虽然21！= 51,090,942,171,709,440,000。对于这种情况，您需要一个Big Integer类型。我在Swift中发现了一个关于Big Integer的问题。该链接中有一个用于Big Integer的库。

相当于Swift中的BigInteger吗？