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\times10^{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.

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

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?

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

#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];
}