1.4 Working with GMP integers

by Marko Riedel

1.4.1 Idea

Combinatorics problems often require arbitrary precision arithmetic; this is the case e.g. with the graph enumeration problem that we present in the next recipe. We need an efficient Objective C wrapper class that encapsulates the GMP integer data structure. This is what GMPInt is all about.

1.4.2 Implementation

The class GMPInt is a wrapper class whose sole instance variable holds a GMP Integer.

 
#include <Foundation/Foundation.h> 
#include <gmp.h> 
 
@interface GMPInt : NSObject 
{ 
    mpz_t value; 
}

The class knows how to manufacture objects for the values zero and one and it can compute the factorial of an unsigned long int.

 
+ (GMPInt *)zeroObj; 
+ (GMPInt *)oneObj; 
 
+ (GMPInt *)factorialUI:(unsigned long)op;

There are two initializers: we may initialize from a signed long integer or from a GMP integer.

 
- (GMPInt *)initWithSI:(signed long)lval; 
- (GMPInt *)initWithValue:(mpz_t)val;

The basic operations of arithmetic are implemented. All four use the receiver as the first operand, the argument as the second and return a GMPInt with the value of the result.

 
- (GMPInt *)add:(GMPInt *)op; 
- (GMPInt *)sub:(GMPInt *)op; 
- (GMPInt *)mul:(GMPInt *)op; 
- (GMPInt *)div:(GMPInt *)op;

GMPInt instances can raise themselves to a power given by an unsigned long integer.

 
- (GMPInt *)powUI:(unsigned long)op;

It is important that a GMPInt instance be able to represent itself as a string. This is what stringValue: does; we also implement description so that the %@ works e.g. in calls to NSLog.

 
- (NSString *)stringValue; 
- (NSString *)description;

Two commonly used predicates test for the receiver’s value being zero or one.

 
- (BOOL)isZero; 
- (BOOL)isOne;

The arithmetic methods need to get at the GMP integer value of their second argument; we provide a method for this purpose. We also implement dealloc, so that we can free GMP integers, i.e. ‘‘mpz_t’’ values, that are no longer used.

 
- (mpz_t *)valPtr; 
 
- (void)dealloc; 
 
@end

The implementation is straightforward. The methods zeroObj and oneObj simply invoke the initializer with the appropriate argument.

 
@implementation GMPInt 
 
+ (GMPInt *)zeroObj 
{ 
    return [[GMPInt alloc] initWithSI:0]; 
} 
 
+ (GMPInt *)oneObj 
{ 
    return [[GMPInt alloc] initWithSI:1]; 
}

The class method for the factorial of an unsigned long integer allocates a GMPInt, obtains a pointer to its value, initializes the value (an mpz_t), calls GMP to compute the result and returns the GMPInt.

 
+ (GMPInt *)factorialUI:(unsigned long)op 
{ 
    GMPInt *res = [[GMPInt alloc] autorelease]; 
    mpz_t *rptr = [res valPtr]; 
 
    mpz_init(*rptr); 
    mpz_fac_ui(*rptr, op); 
 
    return res; 
}

The two initializers initialize and set the instance variable value from their arguments and put the object into an autorelease pool. This is important, because a computation may temporarily allocate a lot of integers and the space they occupy will not be released if they are not put in an autorelease pool. We’ll see more about garbage collection later on.

 
- (GMPInt *)initWithSI:(signed long)lval 
{ 
    mpz_init_set_si(value, lval); 
    [self autorelease]; 
    return self; 
} 
 
- (GMPInt *)initWithValue:(mpz_t)val 
{ 
    mpz_set(value, val); 
    [self autorelease]; 
    return self; 
}

The method add allocates a GMPInt, initializes its value, stores the sum in this value and returns the GMPInt.

 
- (GMPInt *)add:(GMPInt *)op 
{ 
    GMPInt *res = [[GMPInt alloc] autorelease]; 
    mpz_t *rptr = [res valPtr]; 
 
    mpz_init(*rptr); 
    mpz_add(*rptr, value, *[op valPtr]); 
 
    return res; 
}

Subtraction only differs in the mpz method that is called.

 
- (GMPInt *)sub:(GMPInt *)op 
{ 
    GMPInt *res = [[GMPInt alloc] autorelease]; 
    mpz_t *rptr = [res valPtr]; 
 
    mpz_init(*rptr); 
    mpz_sub(*rptr, value, *[op valPtr]); 
 
    return res; 
}

The structure stays the same for multiplication.

 
- (GMPInt *)mul:(GMPInt *)op 
{ 
    GMPInt *res = [[GMPInt alloc] autorelease]; 
    mpz_t *rptr = [res valPtr]; 
 
    mpz_init(*rptr); 
    mpz_mul(*rptr, value, *[op valPtr]); 
 
    return res; 
}

Division is like multiplication, except that we must choose from several mpz calls according to the rounding style that is to be used and whether we need the quotient, the remainder or both. We choose “truncate” for our rounding style and we do not compute the remainder.

 
- (GMPInt *)div:(GMPInt *)op 
{ 
    GMPInt *res = [[GMPInt alloc] autorelease]; 
    mpz_t *rptr = [res valPtr]; 
 
    mpz_init(*rptr); 
    mpz_tdiv_q(*rptr, value, *[op valPtr]); 
 
    return res; 
}

Exponentiation differs from the preceding methods in that there is no invocation of valPtr, because we may use the argument as is.

 
- (GMPInt *)powUI:(unsigned long)op 
{ 
    GMPInt *res = [[GMPInt alloc] autorelease]; 
    mpz_t *rptr = [res valPtr]; 
 
    mpz_init(*rptr); 
    mpz_pow_ui(*rptr, value, op); 
 
    return res; 
}

The method stringValue returns a string that is a decimal representation of the receiver. It uses mpz_sizeinbase to determine the number of digits and takes a possible sign and the terminating null byte into account. It invokes mpgz_get_str to write the decimal representation into a buffer it has allocated for this purpose and then produces a NSString object from the contents of the buffer, freeing it after the string object is obtained. The method description simply returns the string value of the receiver.

 
- (NSString *)stringValue 
{ 
    NSZone *dz = NSDefaultMallocZone(); 
    char *buf; 
    NSString *res; 
 
    buf = NSZoneMalloc(dz, mpz_sizeinbase(value, 10)+2); 
    mpz_get_str(buf, 10, value); 
    res = [NSString stringWithCString:buf]; 
    NSZoneFree(dz, buf); 
 
    return res; 
} 
 
- (NSString *)description 
{ 
    return [self stringValue]; 
}

The predicates that test for zero and one, respectively, work by calling the mpz_comp_ui with the appropriate arguments.

 
- (BOOL)isZero 
{ 
    return (!mpz_cmp_ui(value, 0) ? YES : NO); 
} 
 
- (BOOL)isOne 
{ 
    return (!mpz_cmp_ui(value, 1) ? YES : NO); 
}

The method valPtr is used by the arithmetic methods and returns the address of the mpz_t value in the receiver.

 
- (mpz_t *)valPtr 
{ 
    return &value; 
}

The implementation of GMPInt concludes with the method dealloc, whose purpose is to free the space that GMP has allocated for the value of the receiver, since it is no longer needed.

 
- (void)dealloc 
{ 
    mpz_clear(value); 
    [super dealloc]; 
} 
 
@end