Bignum: Arbitrary-Precision Arithmetic (C)
Topics: numeric algorithms, strings, carries
Problem
Implement arbitrary-precision unsigned integer addition and
multiplication on decimal strings, so you can compute with numbers far larger
than uint64_t can hold.
void big_add(const char *a, const char *b, char *out, size_t outcap);
void big_mul(const char *a, const char *b, char *out, size_t outcap);
Inputs are canonical decimal strings (no leading zeros, except "0"), and outputs
must be too. No allocation.
How it works
These are the algorithms you used in grade school, made precise.
Addition walks both numbers from the least significant digit, adds matching
digits plus a carry, writes sum % 10, and carries sum / 10. When one number runs
out, treat its missing digits as 0. A final carry adds one more digit.
Multiplication is the long-multiplication grid: digit i of a times digit j
of b contributes to position i + j of the result. Accumulate all those products
into an integer array of length len(a) + len(b), then make a single carry-
propagation pass to reduce every position below 10. Strip leading zeros at the end.
for i in a: for j in b: prod[i + j] += a_digit * b_digit;
for k: prod[k+1] += prod[k] / 10; prod[k] %= 10;
Key concepts
- Strings sidestep overflow. By storing one decimal digit per character, the
size of the number is limited only by your buffer, not by a machine word. The
arithmetic never overflows because each step works on small digits.
- Carry is the whole subtlety. Addition carries as it goes; multiplication
accumulates first (where a position can briefly exceed 9 many times over) and
normalizes in one pass. Getting the carry and the final leading-zero trim right is
the exercise.
- Edge cases:
0 + 0, multiply by zero (the answer is "0", not ""), and a
result one digit longer than either input.
This is the core of every bignum library (Python's ints, Java's BigInteger,
crypto math), just without the optimizations.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/bignum && /tmp/bignum
Sign in to submit your solution.