Chapter 4: The Fundamental Operations | Cryptography in C and C++

Team-Fly

Overview

Thus calculation can be seen as the basis and foundation of all the arts.

—Adam Ries, Book 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

THE 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.

Team-Fly