How to implement such a function in Objective-C? 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.

NSUInteger RRFactorial(NSUInteger n);

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

#import <RRFoundation/RRFactorial.h>

int main(int argc, char *argv[])
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    NSUInteger n;
    for (n = 0; n < 20; n++)
    {
        NSLog(@"%lu %lu", (unsigned long)n, (unsigned long)RRFactorial(n));
    }
    [pool drain];
    return 0;
}

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 look-up transformation; no calculations required. Space is not at issue. Such a look-up 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.

Design-by-contract principles will set boundaries. Give it high values of n and don’t expect sensible answers. That’s a way of saying ‘ignore it!’

#import "RRFactorial.h"

NSUInteger RRFactorial(NSUInteger n)
{
    // Cache the factorials. Use NSZoneMalloc, Realloc and Free for memory management. For initial revisions, ignore memory leaks at application exit.
    static NSUInteger *factorials = NULL;
    static NSUInteger numberOfFactorials;
    if (factorials == NULL)
    {
        factorials = NSZoneMalloc(NSDefaultMallocZone(), sizeof(NSUInteger));
        factorials[0] = 1;
        numberOfFactorials = 1;
    }
    if (n >= numberOfFactorials)
    {
        NSUInteger *newFactorials = NSZoneRealloc(NSDefaultMallocZone(), factorials, (n + 1) * sizeof(NSUInteger));
        factorials = newFactorials;
        while (numberOfFactorials <= n)
        {
            factorials[numberOfFactorials] = numberOfFactorials * factorials[numberOfFactorials - 1];
            numberOfFactorials++;
        }
    }
    return factorials[n];
}

Testing

Executing the test case produces:

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 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 32-bit platforms.

64-bit testing

Switching to pure 64-bit, 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 64-bit 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 64-bit 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

#import <Foundation/Foundation.h>

NSUInteger RRFactorial(NSUInteger n);
    // Answers the factorial of n, or NSUIntegerMax if factorial exceeds
    // NSUInteger type's upper boundary. Uses Foundation framework's NSUInteger
    // type to carry factorials.

RRFactorial.m

#import "RRFactorial.h"

NSUInteger RRFactorial(NSUInteger n)
{
    // Use preprocessor macros to determine the maximum value of n computable
    // within the limits prescribed by NSUInteger, whose bit-width depends on
    // architecture: either 64 or 32 bits.
#if __LP64__ || NS_BUILD_32_LIKE_64
#define N 20 // 20! = 2,432,902,008,176,640,000
#else
#define N 12 // 12! = 479,001,600
#endif
    if (n > N) return NSUIntegerMax;
    static NSUInteger f[N + 1];
    static NSUInteger i = 0;
    if (i == 0)
    {
        f[0] = 1;
        i = 1;
    }
    while (i <= n)
    {
        f[i] = i * f[i - 1];
        i++;
    }
    return f[n];
}

Download sources

You can download the MIT-licensed sources here.