Factorial, denoted by n! and defined as the product of all positive integers less than or equal to n.
How to implement such a function in ObjectiveC? It needs to be fast and, of course, accurate. Needless to say it will have limitations. Factorials very quickly become large. The implementation will use NSUInteger
as the numeric type. This type’s size depends on architecture, 32 or 64 bit. Hence its ability to carry factorials will vary. Whatever the case, whatever architectural limitations and capabilities, the implementation will reside within them. No other choice!
Interface
The requirement is purely functional. No class required.
1


So very simple. One NSUInteger
in, another out. Factorials deal with positive integers only. Hence U for unsigned integer.
Test case
The test case iterates all the integers n
between 0 and 19 inclusive and logs the value of n
and RRFactorial(n)
.
1 2 3 4 5 6 7 8 9 10 11 12 13 

At first, the test fails successfully! It even fails to link because no implementation for the function currently exists.
Implementation
General factorial implementation is extremely simple: given n, just multiply together every integer between 1 and n inclusive. Nothing difficult there.
However, the implementation herein will aim for speed by caching the results dynamically. So having already computed the factorial for any given integer, the answer just becomes a lookup transformation; no calculations required. Space is not at issue. Such a lookup implementation will not usually exceed say 20. After that, answers become silly numbers; e.g. 50! approximately equals 3*pow(10,64)
. That’s a pretty big number and bigger even than DBL_MAX
.
Designbycontract principles will set boundaries. Give it high values of n and don’t expect sensible answers. That’s a way of saying ‘ignore it!’
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 

Testing
Executing the test case produces:
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 39916800
12 479001600
13 1932053504
14 1278945280
15 2004310016
16 2004189184
17 4006445056
18 3396534272
19 109641728
Compare this to the factorial tableau at Wikipedia. It’s a match!
Or is it? Note deviations starting at n=13. That’s because 13! exceeds unsigned integer maximum of about 4,000 million on 32bit platforms.
64bit testing
Switching to pure 64bit, by making architectures (ARCHS
) equal to ppc64
plus x86_64
, and rerunning the test produces a different result.
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 39916800
12 479001600
13 6227020800
14 87178291200
15 1307674368000
16 20922789888000
17 355687428096000
18 6402373705728000
19 121645100408832000
Much better. Or should I say less limited. Better is just a point of view in this case because even the 64bit version will eventually find its limitations. Man’s got to know his limitations! (“Dirty” Harry Callahan, Magnum Force, 1973)
Failing gracefully
At present, nothing gracefully happens when n and n! reach limits of the host machine. That’s not very satisfying. Should it not stop after overflow? Nor is the fact that the function remains insensitive to memory allocation failures a source of satisfaction. Should it throw exceptions? That’s messy.
There’s another approach.
Since the factorial cache has limited size under normal conditions, why not make the cache static; its size depending on the compiler’s NSUInteger
width. Once the cache is full, answer NSUIntegerMax
indicating factorial out of integer range. That would solve two problems at the same time; two birds, one stone.
Compiler manifest constant __LP64__
signals 64bit architecture. However, there is also a special NS_BUILD_32_LIKE_64
macro for making NSUInteger
64 bits wide regardless.
Updated version below. It eliminates dependence on memory allocation and obviates exception handling for allocation failure and boundary overflow. All in one fell swoop. I’ve also obfuscated variable names to make it more mathematical in nature: i for the index of the last computed factorial, f for the factorials, N for the upper inclusive boundary of n. Is that bad?
Listings
RRFactorial.h
1 2 3 4 5 6 

RRFactorial.m
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 

Download sources
You can download the MITlicensed sources here.