How to calculate 21! (21 factorials) in fast?

Question

I am doing a fuction that quickly calculates factorial. like this

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

this function can be calculated up to 20.

I think the factor (21) value is greater than UINT64_MAX.

then how to calculate 21! (21 factorials) in swift?

Answer 1

An unsigned 64-bit integer has a maximum value of 18,446,744,073,709,551,615. While 21! = 51,090,942,171,709,440,000. For this case, you need a Big Integer type. I found a question about Big Integer in Swift. This link has a library for Big Integer.

BigInteger equivalent in Swift?

Answer 2

Did you think about using double? Or NSDecimalNumber?

Also, a recursive call of the same function has a very bad effect on performance.

How about using a loop:

 let value = number.intValue - 1 var product = NSDecimalNumber(value: number.intValue) for i in (1...value).reversed() { product = product.multiplying(by: NSDecimalNumber(value: i)) } 

Answer 3

If you want to give up accuracy, you can use Double to approximate factorials up to 170:

 func factorial(_ n: Int) -> Double { if n == 0 { return 1 } var a: Double = 1 for i in 1...n { a *= Double(i) } return a } 

If not, use a large integer library.