TABLE OF CONTENTS Computing the product of two integers in software can be achieved using a trivial adaptation of the standard O( n 2) long-hand multiplication algorithm that schoolchildren are taught. The algorithm is considered an O( n 2) algorithm, since for two n-digit inputs n 2 single precision multiplications are required. More specifically, for an m and n digit input m n single precision multiplications are required. To simplify most discussions, it will be assumed that the inputs have a comparable number of digits.
The "baseline multiplication" algorithm is designed to act as the "catch-all" algorithm, only to be used when the faster algorithms cannot be used. This algorithm does not use any particularly interesting optimizations and should ideally be avoided if possible. One important facet of this algorithm is that it has been modified to only produce a certain amount of output digits as resolution. The importance of this modification will become evident during the discussion of Barrett modular reduction. Recall that for an n and m digit input the product will be at most n + m digits. Therefore, this algorithm can be reduced to a full multiplier by having it produce n + m digits of the product.
Recall from section 4.2.2 the definition of ? as the number of bits in the type mp_digit. We shall now extend the variable set to include ?, which...
