TABLE OF CONTENTS This chapter discusses the various higher level algorithms that are required to complete a well rounded multiple precision integer package. These routines are less performance oriented than the algorithms in Chapters 5, 6, and 7, but are no less important.
The first section describes a method of integer division with remainder that is universally well known. It provides the signed division logic for the package. The subsequent section discusses a set of algorithms that allow a single digit to be the 2nd operand for a variety of operations. These algorithms serve mostly to simplify other algorithms where small constants are required. The last two sections discuss how to manipulate various representations of integers; for example, converting from an mp_int to a string of character.
Integer division aside from modular exponentiation is the most intensive algorithm to compute. Like addition, subtraction, and multiplication, the basis of this algorithm is the long-hand division algorithm taught to schoolchildren. Throughout this discussion several common variables will be used. Let x represent the divisor and y represent the dividend. Let q represent the integer quotient ? y/ x ? and let r represent the remainder r = y - x ? y/ x ?. The following simple algorithm will be used to start the discussion (Figure 8.1).
| Algorithm Radix- ? Integer Division. Input. integer x and y Output. q = ? y/ x ? |
