Page 224 - ARM 64 Bit Assembly Language

212 Chapter 7

digit divisor and producing a 2n digit quotient and an n digit remainder. for example, the
AArch64 processor is capable of dividing a 64-bit dividend by a 64-bit divisor, producing a
64-bit quotient. The remainder can be calculated by multiplying the quotient by the divisor
and subtracting the product from the dividend. Using this division operation it is possible to
divide an arbitrarily large dividend by a 32-bit divisor.

We have seen that, given a divide operation capable of dividing an n digit dividend by an n
digit divisor, it is possible to divide a dividend with any number of digits by a divisor with n
2
digits. Unfortunately, there is no similar method to deal with an arbitrarily large divisor, or
to divide an arbitrarily large dividend by a divisor with more than n digits. In those cases the
2
division must be performed using a general division algorithm as shown previously.

7.4 Big integer ADT

For some programming tasks, it may be helpful to deal with arbitrarily large integers. For ex-
ample, the factorial function and Ackerman’s function grow very quickly and will overflow a
32-bit integer for even small input values. Even a 64 bit integer is insufficient for holding the
results of these functions with even relatively small inputs. The GNU C compiler is able to do
some big number arithmetic using __uint128_t, but even a 128 bit integer is insufficient for
these functions.

In this section, we will examine an abstract data type which provides basic operations for ar-
bitrarily large integer values. Listing 7.7 shows the C header for this ADT, and Listing 7.8
shows the C implementation. Listing 7.9 shows a small program that runs regression tests
on the big integer ADT. A regression test is a (relatively) small test that is used to verify that
changes to the code have not introduced bugs. Regression tests are very valuable tools in soft-
ware engineering, and are typically used in larger companies by code testing specialists.

Listing 7.7 Header file for a big integer abstract data type.
1 #ifndef BIGINT_H
2 #define BIGINT_H
3 #include <stdio.h>
4
5 struct bigint_struct;
6
7 /* Define bigint to be a pointer to a bigint_struct */
8 typedef struct bigint_struct* bigint;
9
10 /* There are three ways to create a bigint */
11 bigint bigint_from_str(char *s);
12 bigint bigint_from_int(int i);
13 bigint bigint_copy(bigint source);