May 2000 Programmer's Challenge

BigNum Math

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm ET, Monday, 1 May 2000

Back in September, 1995, we conducted an RSA Challenge that involved raising large integers to integral powers, modulo a third integer. The representation we used for those large integers was a BigNum type, where each digit of the large integer was stored in a byte. That representation and the operations on it were not particularly efficient, and this month we will belatedly recitfy that situation. Your Challenge is to implement a new BigNum type, of your own design, along with a number of arithmetic operations on these BigNums..

The prototype for the code you should write is:

typedef struct BigNum {  
  long lengthInDigits;    /* length of the BigNum in digits */
  void *bigNumData;       /* pointer to BigNum data */
} BigNum;

BigNum NewBigNum (        /* create a BigNum */
  char sign,              /* +1 or -1 */
  char digits[],          /* digits to be made into a BigNum */
  long numDigits          /* number of digits */
);

void DisposeBigNum (      /* dispose of a BigNum */
  BigNum theBigNum        /* the BigNum to be disposed of */
);

BigNum AddBigNums (       /* sum two BigNums, returning a new one */
  BigNum bigNumA,         /* return the sum A+B */
  BigNum bigNumB  
);

BigNum SubtractBigNums (  /* subtract two BigNums, returning a new one */
  BigNum bigNumA,         /* return the difference A-B */
  BigNum bigNumB  
);

BigNum MultiplyBigNums (  /* multiply two BigNums, returning a new one */
  BigNum bigNumA,         /* return the product A*B */
  BigNum bigNumB  
);

BigNum DivideBigNums (    /* divide two BigNums, returning a new one */
  BigNum bigNumA,         /* return the quotient A/B, discarding the remainder */
  BigNum bigNumB  
);

BigNum ModBigNums (       /* divide two BigNums, returning a new one */
  BigNum bigNumA,         /* return the remainder A%B, discarding the quotient */
  BigNum bigNumB  
);

BigNum PowerBigNums (     /* calculate one Bignum to the power of another, returning a new one */
  BigNum bigNumA,         /* return A raised to the power B*/
  BigNum bigNumB  
);

BigNum SqrtBigNum (       /* find the sqrt of a BigNum, returning a new one */
  BigNum bigNumA          /* return the square root of A */
);

long /* numDigits */ BigNumToDigits( /* convert a bigNum to decimal digits */
  BigNum bigNumA,         /* bigNum to be converted to decimal digits 0-9 */
  char *sign,             /* return +1 or -1 */
  char digits[]           /* decimal digits of bigNumA, preceeded by '-' if negative */
                          /* storage for digits preallocated based on bigNumA.lengthInDigits */
);

The first thing you need to do is decide on an internal representation for BigNums. Then you need to write a NewBigNum routine that will create a BigNum from a sequence of numDigits digits and a sign value. Your NewBigNum code is responsible for allocating memory for the BigNumData. The DisposeBigNum routine is responsible for deallocating that memory. The caller of your code is responsible for pairing every NewBigNum call with a DisposeBigNum call, and the two routines should be implemented so as not to create any memory leaks.

In addition to these allocation and deallocation routines, you need to write code to perform addition (AddBigNums), subtraction (SubtractBigNums), multiplication (MultiplyBigNums), division (DivideBigNums), remainders (ModBigNums), and exponentiation (PowerBigNums). Each of these routines takes two arguments, calculates the result, and returns the result in a new BigNum allocated by your code. Each of these returned BigNums will also be disposed of by a call to DisposeBigNum before the test is over, although they might be used for calculations in the interim.

Just to spice things up, you also need to provide a SqrtBigNum routine that calculates and returns the integer square root of a BigNum, the largest BigNum whose square is no larger than the original number.

And finally, to help me decipher your BigNums, you need to provide a BigNumToDigits conversion routine that converts your private BigNum data structure into a sequence of digits, along with a sign, and returns the number of digits in the decimal representation of the BigNum.

I’m not providing information on the distribution of calls to the various routines, except to say that the arithmetic routines will significantly outnumber the allocation and deallocation routines. The winner will be the solution that correctly completes a sequence of arithmetic operations on BigNums in the least amount of time. You are strongly encouraged to adequately comment the code in your submissions. Not only does that make your code more understandable if it is published as the winning solution, but it also helps me track down any minor problems that might occur.

I’ll close with a plug for the Challenge mailing list, where you can receive notice of the problems before the hard-copy magazine reaches your mailbox, and where any post-publication clarifications are distributed. Subscription instructions can be found at www.mactech.com/progchallenge/.