May 00 Challenge
Volume Number: 16
Issue Number: 5
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
BigNum Math
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:
long lengthInDigits; /* length of the BigNum in digits */
void *bigNumData; /* pointer to BigNum data */
BigNum NewBigNum ( /* create a BigNum */
char sign, /* +1 or -1 */
char digits[], [TOKEN:12074] digits to be made into a
BigNum */
long numDigits [TOKEN:12074] 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, [TOKEN:12074] return the sum A+B */
BigNum bigNumB
);
BigNum SubtractBigNums ( /* subtract two BigNums, returning a new
one */
BigNum bigNumA, [TOKEN:12074] return the difference A-B
*/
BigNum bigNumB
);
BigNum MultiplyBigNums ( /* multiply two BigNums, returning a new
one */
BigNum bigNumA, [TOKEN:12074] return the product A*B */
BigNum bigNumB
);
BigNum DivideBigNums ( /* divide two BigNums, returning a new one
*/
BigNum bigNumA, [TOKEN:12074] return the quotient A/B,
discarding the remainder */
BigNum bigNumB
);
BigNum ModBigNums ( /* divide two BigNums, returning a
new one */
BigNum bigNumA, [TOKEN:12074] 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, [TOKEN:12074] return A raised to the
power B, discarding the
quotient */
BigNum bigNumB
);
BigNum SqrtBigNum ( /* find the sqrt of a BigNum,
returning a new one */
BigNum bigNumA [TOKEN:12074] return the square root of A
*/
);
long /* numDigits */ BigNumToDigits( /* convert a bigNum to decimal
digits */
BigNum bigNumA, [TOKEN:12074] 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 . This will be a native PowerPC
Challenge, using the CodeWarrior Pro 5 environment. Solutions may be coded in C,
C++, or Pascal.
Three Months Ago Winner
The February Challenge required readers to calculate a minimal Latin square of a given
order. Latin Squares are nxn arrays of integers, where each row and each column
contains each integer from 1 to n exactly once. Congratulations to Willeke Rieken (The
Netherlands) for coming up with the winning solution to the Latin Squares Challenge.
Eleven readers submitted entries to this Challenge, and their performance varied
widely in efficiency. My test scenario was based on 28 test cases, consisting of the
Latin Squares of orders 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32, 33,
36, 37, 40, 41, 44, and 45. I selected those numbers because they formed a regular
pattern that could be continued as far as the solutions would allow, and because they
contained a mix of odd numbers, even numbers, perfect squares, prime numbers, and
powers of two. My original intent was to test even larger numbers, but even the best
solutions took too long to calculate some of the larger numbers.
Even limiting the tests to these cases, some of the solutions took a long time to execute,
so I divided the tests into three sets. The first set consisted of the first ten test cases,
and I ran all of the entries against that set. Three of the entries either did not complete
all of the cases, or calculated a Latin Square that was larger than the squares calculated
by other solutions. Three of the entries had fast execution times for the ten cases, and
one more had an execution time within roughly two orders of magnitude of the best
ones. So I ran the top four solutions against the next six test cases. Two of the entries
completed those cases correctly, so I ran those cases against the final six test cases.
The second place solution by Ernst Munter was by far the faster of the two, but
unfortunately, it did not compute the minimal solution for the square of order 37.
Where Ernst calculated a solution that included the following as the 28th row:
28 27 26 25 32 31 30 35 36 37 33 34 19 20 17 21 7 8 9 5 6 4 ...
... Willeke's entry produced the following smaller value:
28 27 26 25 32 31 30 35 36 37 33 34 19 20 17 21 7 8 9 5 6 3 ...