0

tl;dr: How should I be dealing with numbers like 20! * 20! in Objective-C?


I'm learning Objective-C by working through Project Euler. It's been quite fun, but one problem I've been running in to is working with arbitrarily large numbers. I'm still pretty green on these things, so I don't know why something like, say, Python, handles large numbers with ease compared to Obj-C.

Take for example Problem 15:

Starting in the top left corner of a 2 x 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20 x 20 grid?

That's easy. Using combinatorics:

(20+20)! / 20!(20!)
-> 815915283247897734345611269596115894272000000000 / 5919012181389927685417441689600000000
-> 137846528820

In Python:

import math  
print math.factorial(40) / (math.factorial(20) * math.factorial(20))

In Objective-C, though? I have't yet found a way to force such a large numbers through. Using the 2 x 2 example works fine. I can get 9C4 = 126, as it should be. But how should I be dealing with numbers like 20!?

I've dallied with trying to use NSDecimalNumber, which appears to support more numerals per number, assuming you can convert it to Mantissa x Exponent and don't mind loss of precision, but that didn't prove to be too useful, as I couldn't figure out how to have Obj-C create a Mantissa from a %llu and I do mind loss of precision.

The code I have so far properly generates the factorials, as it appears unsigned long long handles values so large, but chokes up on x * y, and thus getCombinatoricOf:20 and:20 returns 1.

#import "Problem15.h"

@implementation Problem15

- (unsigned long long)factorial:(NSNumber *)number {
    unsigned long long temp = 1;
    for (int i = [number intValue]; i > 0; i--) {
        temp *= i;
    }
    return temp;
}

- (unsigned long long)getCombinatorcOf:(NSNumber *)x and:(NSNumber *)y {
    NSNumber *n = @([x intValue] + [y intValue]);
    NSNumber *n_factorial = @([self factorial:n]);
    NSNumber *x_factorial = @([self factorial:x]);
    NSNumber *y_factorial = @([self factorial:y]);
    return ([n_factorial unsignedLongLongValue] / ([x_factorial unsignedLongLongValue] * [y_factorial unsignedLongLongValue]));
}

- (NSString *)answer {
    NSNumber *x = @5;
    NSNumber *y = @4;
    unsigned long long answer = [self getCombinatoricOf:x and:y];
    return [NSString stringWithFormat:@"\n\nProblem 15: \nHow many routes are there through a 20 x 20 grid? \n%llu", answer];
}

@end

1 Answer 1

1

It's not Objective-C, but you could just use GMP just as an ordinary C library.

There are also Objective-C wrappers fo GMP, like GMPInt.

3
  • This worked wonderfully with minimal setup; thanks! It does worry me that the Wrapper hasn't been updated in 2 years (had to manually edit for ARC support) and the calls are pretty weird (e.g. to multiply two GMPInts together was: [myGMPInt multiplyWithGMP:myOtherGMPInt];. This in and of itself isn't wierd, but the fact that it returns a void, and I couldn't assign it to a new GMPInt kind of threw me off. The deeper question still stands (if you have any answer): Why doesn't Obj-C/C have support for arbitrarily large numbers like Python does? What's the difference? Nov 6, 2012 at 17:47
  • I think the ObjC GMP wrapper project, isn't looking very updated. I mostly linked to it so you could look at how he does the wrapping and the GMP C calls. Nov 6, 2012 at 20:24
  • I think the reason for Objective-C's lack of a large number class is because it's a small language—a small extension to standard ANSI C—with a different philosophy than Python, Java or C++. I think this is also carried on to the libraries. For example, look at how very few data structures Core Foundation includes—not much more than an array, a dictionary/hash and a set. Nov 6, 2012 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.