Cryptography Reference
In-Depth Information
CHAPTER 2
Number Formats:
The Representation of
Large Numbers in C
So I have made up my own system for writing large numbers and I am going
to use this chapter as a chance to explain it
—Isaac Asimov,
Adding a Dimension
The process that has led to the higher organization of this form could also be
imagined differently
—J. Weber,
Form, Motion, Color
O
NE OF THE FIRST STEPS
in creating a function library for calculating with large
numbers is to determine how large numbers are to represented in the computer's
main memory. It is necessary to plan carefully, since decisions made at this point
will be difficult to revise at a later time. Changes to the internal structure of a
software library are always possible, but the user interface should be kept as
stable as possible in the sense of “upward compatibility.”
It is necessary to determine the order of magnitude of the numbers to be
processed and the data type to be used for coding these numerical values.
The basic function of all routines in the FLINT/C library is the processing
of natural numbers of several hundred digits, which far exceeds the capacity of
standard data types. We thus require a logical ordering of a computer's memory
units by means of which large numbers can be expressed and operated on. In
this regard one might imagine structures that automatically create sufficient
space for the values to be represented, but no more than is actually needed. One
would like to maintain such economically organized housekeeping with respect
to main memory by means of dynamic memory management for large numbers
that allocates or releases memory according to need in the course of arithmetic
operations. Although such can certainly be realized (see, for example, [Skal]),
memory management has a price in computation time, for which reason the
