Number Formats: The Representation of Large Numbers in C - Cryptography in C and C++ - page 12

representation of integers in the FLINT/C package gives preference to the simpler
definition of static length.
For representing large natural numbers one might use vectors whose
elements are a standard data type. For reasons of efficiency an unsigned data
type is to be preferred, which allows the results of arithmetic operations to be
stored in this type without loss as unsigned long (defined in flint.h as ULONG ),
which is the largest arithmetic standard C data type (see [Harb], Section 5.1.1). A
ULONG variable can usually be represented exactly with a complete register word of
the CPU.
Our goal is that operations on large numbers be reducible by the compiler as
directly as possible to the register arithmetic of the CPU, for those are the parts
that the computer calculates “in its head,” so to speak. For the FLINT/C package
the representation of large integers is therefore by means of the type unsigned
short int (in the sequel USHORT ). We assume that the type USHORT is represented
by 16 bits and that the type ULONG can fully accept results of arithmetic operations
with USHORT types, which is to say that the informally formulated size relationship
USHORT

× USHORT ≤ ULONG holds.
Whether these assumptions hold for a particular compiler can be deduced
from the ISO header file limits.h (cf. [Harb], Sections 2.7.1 and 5.1). For example,
in the file limits.h for the GNU C/C++ compiler (cf. [Stlm]) the following appears:

#define UCHAR_MAX 0xffU
#define USHRT_MAX 0xffffU
#define UINT_MAX 0xffffffffU
#define ULONG_MAX 0xffffffffUL

One should note that with respect to the number of binary places there
are actually only three sizes that are distinguished. The type USHRT (respectively
USHORT in our notation) can be represented in a 16-bit register; the type ULONG fills
the word length of a CPU with 32-bit registers. The type ULONG_MAX determines
the value of the largest unsigned whole numbers representable by scalar types
(cf. [Harb], page 110). 1 The value of the product of two numbers of type USHRT
is at most 0xffff * 0xffff = 0xfffe0001 and is thus representable by a ULONG
type, where the least-significant 16 bits, in our example the value 0x0001, can be
isolated by a cast operation into the type USHRT . The implementation of the basic
arithmetic functions of the FLINT/C package is based on the above-discussed
size relationship between the types USHORT and ULONG .
An analogous approach, one that used data types with 32-bit and 64-bit
lengths in the role of USHORT and ULONG in the present implementation, would
reduce the calculation time for multiplication, division, and exponentiation

1

Without taking into account such practical nonstandard types as unsigned long long in GNU
C/C++ and certain other C compilers.