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?

You need to provide significantly more details. Use the debugger. Step through it one at a time. — nhgrif, Jun 23 '15 at 01:06
Please don't keep adding the [tag:iOS] tag. This has nothing to do with [tag:iOS]. — nhgrif, Jun 23 '15 at 01:06
@DylanModesitt You can still step through one level at a time and get some more information... — nhgrif, Jun 23 '15 at 01:09
Anything in the tens of thousands seemingly because the calculation is too large — modesitt, Jun 23 '15 at 01:10
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, Jun 23 '15 at 01: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, Jun 23 '15 at 01:13
It is ridiculous, I just don't want the app to crash when the user tries to do an idiotically large factorial. — modesitt, Jun 23 '15 at 01:14
@DylanModesitt then just put a condition around that, like `if n > 100 { return Double.infinity }` — Code Different, Jun 23 '15 at 01:22
Find a Scheme interpreter. Input `(/ (factorial 1000) (factorial 999))` and then smile. — GoZoner, Jun 23 '15 at 03:03

Duncan C · Accepted Answer · 2015-06-23T01:39:57.840

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 http://stackoverflow.com/q/24023580/1286639 — GoZoner, Jun 23 '15 at 03:04

Adam Freeman · Answer 2 · 2018-02-06T01:49:27.657

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 06 '18 at 01:49

answered Feb 06 '18 at 01:39

Adam Freeman

1,271
12
20

Factorials in Swift

2 Answers2

Linked