CODEWITHSUNDEEP
swiftmath
dialektike
dialektike

Reputation: 421

How to calculate the 21! (21 factorial) in Swift?

I am making fuction that calculates factorial in Swift. Like this:

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

let x = factorial(20)

This fuction can calculate until 20!.

I think factorial(21) is bigger than UINT64_MAX.

How to accurately calculate 21! (21 factorial) in Swift?

Upvotes: 18

Views: 20659

Answers (4)

kanobius
kanobius

Reputation: 891

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

  1. (1...n): We create an array of all the numbers that are involved in the operation (i.e: [1, 2, 3, ...]).

  2. map(Double.init): We change from Int to Double because we can represent bigger numbers with Doubles than with Ints (https://en.wikipedia.org/wiki/Double-precision_floating-point_format). So, we now have the array of all the numbers that are involved in the operation as Doubles (i.e: [1.0, 2.0, 3.0, ...]).

  3. reduce(1.0, *): We start multiplying 1.0 with the first element in the array (1.0*1.0 = 1.0), then the result of that with the next one (1.0*2.0 = 2.0), then the result of that with the next one (2.0*3.0 = 6.0), and so on.

Step 2 is to avoid the overflow issue.

Step 3 is to save us from explicitly defining a variable for keeping track of the partial results.

Upvotes: 14

Saren Inden
Saren Inden

Reputation: 3660

Did you think about using a double perhaps? Or NSDecimalNumber?

Also calling the same function recursively is really bad performance wise.

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))
}

Upvotes: 3

Luuk Berkers
Luuk Berkers

Reputation: 1

If you are willing to give up precision you can use a Double to roughly calculate 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 big integer library.

Upvotes: 0

Han
Han

Reputation: 3072

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 kind of case, you need a Big Integer type. I found a question about Big Integer in Swift. There's a library for Big Integer in that link.

BigInteger equivalent in Swift?

Upvotes: 9

Related Questions