4.1 Introduction

At this point, algorithms for initialization, clearing, zeroing, copying, comparing, and setting small constants have been established. The next logical set of algorithms to develop are addition, subtraction, and digit shifting algorithms. These algorithms make use of the lower level algorithms and are the crucial building block for the multiplication algorithms. It is very important that these algorithms are highly optimized. On their own they are simple O( n) algorithms but they can be called from higher level algorithms, which easily places them at O( n ²) or even O( n ³) work levels.

All of the algorithms within this chapter make use of the logical bit shift operations denoted by << and >> for left and right logical shifts, respectively. A logical shift is analogous to sliding the decimal point of radix-10 representations. For example, the real number 0.9345 is equivalent to 93.45%, which is found by sliding the decimal two places to the right ( multiplying by ? ² = 10 ²). Algebraically, a binary logical shift is equivalent to a division or multiplication by a power of two. For example, a << k = a 2 ^k while a >> k = ? a/2 ^k ?.

One significant difference between a logical shift and the way decimals are shifted is that digits below the zero'th position are removed from the number. For example, consider 1101 ₂ >>...