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

Question

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

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

let x = factorial(20)

这个函数可以计算到20。

我认为阶乘(21)值大于 UINT64_MAX。

那么如何计算21! (21 阶乘)用 swift 表示？

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，因为我们可以使用 Double 表示比使用 Double 更大的数字整数 (https://en.wikipedia.org/wiki/Double-precision_floating-point_format)。因此，我们现在拥有了参与运算的所有数字的数组，作为 double (即:[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 步是让我们免于显式定义用于跟踪部分结果的变量。