Factorials in Swift

Question

I need a good factorial function. The one I have written here works entirely, except when n gets far too large. This is for a calculator app, and I can return 0 / 0 for values that cannot be factorialed because I have an error checker that will declare that as impossible. However performing the function on a very large number crashes the app. I can't use a range operator because my types are doubles.

func factorial(n: Double) -> Double {
    if n >= 0 {
        return n == 0 ? 1 : n * self.factorial(n - 1)
    } else {
        return 0 / 0
    }
}

What is the best way to do this?

If you require the number to be that large, you should use something like the bignum library. Every application has its limits. The built-in calculator for Mac OS X give overflow with 100! — Code Different
– Code Different, Commented Jun 23, 2015 at 1:13
Perhaps you should look into using a different data type (more precise than Double) or make your own for large numbers with scientific notation. However, 10,000! is a bit ridiculous. — BradzTech
– BradzTech, Commented Jun 23, 2015 at 1:13
@DylanModesitt then just put a condition around that, like if n > 100 { return Double.infinity } — Code Different
– Code Different, Commented Jun 23, 2015 at 1:22
Find a Scheme interpreter. Input (/ (factorial 1000) (factorial 999)) and then smile. — GoZoner
– GoZoner, Commented Jun 23, 2015 at 3:03

Duncan C · Accepted Answer · 2015-06-23 01:39:57Z

As others have said you can use libraries that support larger numbers, or just don't allow values that are too big.

Note that if you want to handle very large values you might need to use a loop rather than a recursive algorithm because recursion can cause a Stack Overflow. Yes, that's right, an SO "eponymous crash".

To prevent numbers that are too big, figure out the largest number that doesn't crash, and do input checking and reject numbers bigger than that.

You can figure out the number that crashes it by going in the opposite direction and logging the count and the result every 10 steps:

1 * 2 * 3 * 4 * 5 * 6...

When you crash, go back to the previous largest logged value, start from there plugging in your previously logged factorial result, and step 1 at a time until you crash. Then only allow n that's 1 less than your crash value.

There is 'tail call optimization' in Swift and thus a properly tail recursive factorial algorithm will not overflow the stack, ever. See stackoverflow.com/q/24023580/1286639

Adam Freeman · Accepted Answer · 2018-02-06 01:49:27Z

1

Here is a simple non-recursive function in Swift -~`~~-^>>

public func factorial(_ N: Double) -> Double {
    var mult = N
    var retVal: Double = 1.0
    while mult > 0.0 {
        retVal *= mult
        mult -= 1.0
    }
    return retVal   
}

Caveat: this function only works for doubles >= 0.0 and zero mantissa

edited Feb 6, 2018 at 1:49

answered Feb 6, 2018 at 1:39

Adam Freeman

1,28812 silver badges22 bronze badges

Collectives™ on Stack Overflow

Factorials in Swift

2 Answers 2

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Linked

Related