Cryptography Reference
In-Depth Information
CHAPTER 4
The Fundamental
Operations
Thus calculation can be seen as the basis and foundation of all the arts.
—Adam Ries,
Topic of Calculation
And you, poor creature, you are completely useless. Look at me. Everyone
needs me.
—Aesop, “The Fir and the Blackberry Bush”
There is one small prerequisite for mastering the mathemagic tricks in
this chapter—you need to know the multiplication tables through 10
...
backward and forward.
—Arthur Benjamin, Michael B. Shermer,
Mathemagics
T
HE FUNDAMENTAL BUILDING BLOCKS OF
any software package for computer
arithmetic are the functions that carry out the basic operations of addition,
subtraction, multiplication, and division. The efficiency of the entire package
hangs on the last two of these, and for that reason great care must be taken in the
selection and implementation of the associated algorithms. Fortunately, volume
2 of Donald Knuth's classic
The Art of Computer Programming
contains most of
what we need for this portion of the FLINT/C functions.
In anticipation of their representation to come, the functions developed in
the following sections use the operations
cpy_l()
, which copies one
CLINT
object
to another in the sense of an allocation, and
cmp_l()
, which makes a comparison
of the sizes of two
CLINT
values. For a more precise description see Section 7.4 and
Chapter 8.
Let us mention at this point that for the sake of clarity, in this chapter the
functions for the fundamental arithmetic operations are developed all of a piece,
while in Chapter 5 it will prove practical to split some of the functions into their
respective “core” operations and from there develop additional steps such as
the elimination of leading zeros and the handling of overflow and underflow,
where, however, the syntax and semantics of the functions are kept intact. For an
understanding of the relations described in this chapter this is irrelevant, so that
for now we can forget about these more difficult issues.
