5.2.1 The Baseline Multiplication

Computing the product of two integers in software can be achieved using a trivial adaptation of the standard O(n²) long-hand multiplication algorithm that schoolchildren are taught. The algorithm is considered an O(n²) algorithm, since for two n-digit inputs n²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 shall represent the number of bits in the type mp_word. This implies that 2^α>2 · β². The constant δ= 2^α–2lg(β)will represent the maximal weight of any column in a product (see 6.2 for more information).

Algorithm s_mp_mul_digs. This algorithm computes the unsigned product of two inputs a and b, limited to an output precision of digs digits. While it may seem a bit awkward to modify the function from its simple O(n²) description, the usefulness of partial multipliers will arise in a subsequent algorithm. The algorithm is loosely based on algorithm 14.12 from [2, pp. 595] and is similar to Algorithm M of Knuth [1, pp. 268]. Algorithm s_mp_mul_digs differs from these cited references since it can produce a variable output precision regardless of the precision of the inputs (Figure 5.1).

The first thing this algorithm checks for is whether a Comba multiplier can be used instead. If the minimum digit count of either input is less than δ, then the Comba method may be used instead. After the Comba method is ruled out, the baseline algorithm begins. A temporary mp_int variable t is used to hold the intermediate result of the product. This allows the algorithm to be used to compute products when either a= c or b = c without overwriting the inputs.

All of step 5 is the infamous O(n²) multiplication loop slightly modified to only produce up to digs digits of output. The pb variable is given the count of digits to read from b inside the nested loop. If pb ≤ 1, then no more output digits can be produced and the algorithm will exit the loop. The best way to think of the loops are as a series of pb × 1 multiplications. That is, in each pass of the innermost loop, a_ixis multiplied against b and the result is added (with an appropriate shift) to t.

For example, consider multiplying 576 by 241. That is equivalent to computing 10⁰(1)(576) + 10¹(4)(576) + 10²(2)(576), which is best visualized in Figure 5.2.

Each row of the product is added to the result after being shifted to the left (multiplied by a power of the radix) by the appropriate count. That is, in pass ix of the inner loop the product is added starting at the ix′th digit of the result.

Step 5.4.1 introduces the hat symbol (e.g.,, ), which represents a double precision variable. The multiplication on that step is assumed to be a double wide output single precision multiplication. That is, two single precision variables are multiplied to produce a double precision result. The step is somewhat optimized from a long-hand multiplication algorithm because the carry from the addition in step 5.4.1 is propagated through the nested loop. If the carry were not propagated immediately, it would overflow the single precision digit t_ix+iyand the result would be lost.

At step 5.5 the nested loop is finished and any carry that was left over should be forwarded. The carry does not have to be added to the ix+ pb′th digit sincethat digit is assumed to be zero at this point. However, if ix + pb ≥ digs, the carry is not set, as it would make the result exceed the precision requested.

First, we determine (Line 31) if the Comba method can be used since it is faster. The conditions for using the Comba routine are that min(a.used, b.used) < δ and the number of digits of output is less than MP_WARRAY. This new constant is used to control the stack usage in the Comba routines. By default it is set to δ, but can be reduced when memory is at a premium.

If we cannot use the Comba method we proceed to set up the baseline routine. We allocate the the destination mp_int t(Line 37) to the exact size of the output to avoid further reallocations. At this point, we now begin the O(n²) loop.

This implementation of multiplication has the caveat that it can be trimmed to only produce a variable number of digits as output. In each iteration of the outer loop the pb variable is set (Line 49) to the maximum number of inner loop iterations.

Inside the inner loop we calculate as the mp_word product of the two mp_digits and the addition of the carry from the previous iteration. A particularly important observation is that most modern optimizing C compilers (GCC for instance) can recognize that an N × N → 2N multiplication is all that is required for the product. In x86 terms, for example, this means using the MUL instruction.

Each digit of the product is stored in turn (Line 69) and the carry propagated (Line 72) to the next iteration.

5.2.2 Faster Multiplication by the “Comba” Method

One of the huge drawbacks of the “baseline” algorithms is that at the O(n²) level the carry must be computed and propagated upwards. This makes the nested loop very sequential and hard to unroll and implement in parallel. The “Comba” [5] method is named after little known (in cryptographic venues) Paul G. Comba, who described a method of implementing fast multipliers that do not require nested carry fix-up operations. As an interesting aside it seems that Paul Barrett describes a similar technique in his 1986 paper [5] written five years before.

At the heart of the Comba technique is again the long-hand algorithm, except in this case a slight twist is placed on how the columns of the result are produced. In the standard long-hand algorithm, rows of products are produced and then added together to form the result. In the baseline algorithm, the columns are added together after each iteration to get the result instantaneously.

In the Comba algorithm, the columns of the result are produced entirely independently of each other; that is, at the O(n²)level a simple multiplication and addition step is performed. The carries of the columns are propagated after the nested loop to reduce the amount of work required. Succinctly, the first step of the algorithm is to compute the product vector as follows:

(5.1)

where is the n′th column of the output vector. Consider Figure 5.3, which computes the vector for the multiplication of 576 and 241.

At this point the vector x= 〈10, 34, 45, 31, 6〉is the result of the first step of the Comba multiplier. Now the columns must be fixed by propagating the carry upwards. The resultant vector will have one extra dimension over the input vector, which is congruent to adding a leading zero digit (Figure 5.4).

With that algorithm and k= 5 and β = 10 the = 〈1, 3, 8, 8, 1, 6〉vector is produced. In this case, 241 · 576 is in fact 138816 and the procedure succeeded. If the algorithm is correct and, as will be demonstrated shortly, more efficient than the baseline algorithm, why not simply always use this algorithm?

5.2.3 Even Faster Multiplication

In the realm of O(n²) multipliers, we can actually do better than Comba multipliers. In the case of the portable code, only lg(β) bits of each digit are being used. This is only because accessing carry bits from the CPU flags is not efficient in portable C.

In the TomsFastMath²project, a triple-precision register is used to accumulate products. The multiplication algorithm produces digits of the result at a time. The benefit of this algorithm is that we are packing more bits per digit resulting in fewer single precision multiplications. For example, a 1024-bit multiplication on a 32-bit platform involves 1024 single precision multiplications with TomsFastMath and 37²== 1369 with LibTomMath (33% more).

Algorithm fast_mult. This algorithm performs a multiplication using the full precision of the digits (Figure 5.6). It is not strictly part of LibTomMath, instead this is part of TomsFastMath. Quite literally the TomsFastMath library was a port of LibTomMath.

The first noteworthy change from our LibTomMath conventions is that we are indeed using the full precision of the digits. For example, on a 32-bit platform, a 1024-bit number would require 32 digits to be fully represented (instead of the 37 that LibTomMath would require).

The shuffle in step 3.4 is effectively a triple-precision shift right by the size of one digit. Similarly, in step 3.5.1, a double-precision product is being accumulated in the triple–precision array {c 2 : c 1 : c 0}.

The TomsFastMath library gets its significant speed increase over LibTomMath not only due to the use of full precision digits, but also the fact that the multipliers are unrolled and use inline assembler. It unrolls the multipliers in steps of 1 through 16, 20, 24, 28, 32, 48 and 64 digits. The unrolling takes considerable space, but the savings in time from not having all of the loop control overhead is significant. The use of inline assembler also lets us perform the inner loop with code such as the following x 86 assembler.

This performs the 32 × 32 multiplication and accumulates it in the 96-bit array {c 2 : c 1 : c 0}, as required in step 3.5.1 · A particular feature of the TomsFastMath approach is to use these functional macro blocks instead of hand-tuning the implementation for a given platform. As a result, we can change the macro to the following and produce a math library for ARM processors.

In total, TomsFastMath supports four distinct hardware architectures covering x86, PPC32 and ARM platforms from a relatively consistent code base. Adding new ports for most platforms is usually a matter of implementing the macros, and then choosing a suitable level of loop unrolling to match the processor cache.

When fully unrolled, the x86 assembly code achieves very high performance on the AMD K8 series of processors. An “instructions per cycle” count close to 2 can be observed through 1024-bit multiplications. This means that, on average, more than one processor pipeline is actively processing opcodes. This is particularly significant due to the long delay of the single precision multiplication instruction.

Unfortunately, while this routine could be adapted to LibTomMath (using a more complicated right shift in step 3.4), it would not help as we still have to perform the same number of single precision multiplications. Readers are encouraged to investigate the TomsFastMath library on its own to see how far these optimizations can push performance.

5.2.4 Polynomial Basis Multiplication

To break the O(n²) barrier in multiplication requires a completely different look at integer multiplication. In the following algorithms the use of polynomial basis representation for two integers a and b as and respectively, is required. In this system, both f(x) and g(x) have n+ 1 terms and are of the n′th degree.

The product a. b≡ f(x)g(x) is the polynomial . The coefficients w_iwill directly yield the desired product when β is substituted for x. The direct solution to solve for the 2n+ 1 coefficients requires O(n²) time and would in practice be slower than the Comba technique.

However, numerical analysis theory indicates that only 2n+ 1 distinct points in W(x) are required to determine the values of the 2n+1 unknown coefficients. This means by finding ζ_y= W(y) for 2n+ 1 small values of y, the coefficients of W(x) can be found with Gaussian elimination. This technique is also occasionally referred to as the interpolation technique [5], since in effect an interpolation based on 2n+ 1 points will yield a polynomial equivalent to W(x).

The coefficients of the polynomial W(x) are unknown, which makes finding W(y) for any value of y impossible. However, since W(x) = f(x)g(x), the equivalent ζ_y= f(y)g(y) can be used in its place. The benefit of this technique stems from the fact that f(y) and g(y) are much smaller than either a or b, respectively. As a result, finding the 2n+ 1 relations required by multiplying f(y)g(y) involves multiplying integers that are much smaller than either of the inputs.

When you are picking points to gather relations, there are always three obvious points to choose, y = 0, 1, and ∞. The ζ₀term is simply the product W(0) = w₀= a₀. b₀. The ζ₁term is the product . The third point ζ_∞is less obvious but rather simple to explain. The 2n+ 1′th coefficient of W(x) is numerically equivalent to the most significant column in an integer multiplication. The point at ∞ is used symbolically to represent the most significant column– W(∞) = w_2n= a_nb_n. Note that the points at y = 0 and ∞ yield the coefficients w₀and w_2ndirectly.

If more points are required they should be of small values and powers of twosuch as 2^qand the related mirror points(2^q)²ⁿ. ζ_{2– q}for small values of q. The term “mirror point” stems from the fact that (2^q)²ⁿ. ζ_{2– q}can be calculated in the exact opposite fashion as ζ_2q. For example, when n = 2 and q = 1, the following two equations are equivalent to the point ζ₂and its mirror.

(5.5)

Using such points will allow the values of f(y) and g(y) to be independently calculated using only left shifts. For example, when n = 2 the polynomial f(2^q) is equal to 2^q((2^qa₂) + a₁) + a₀. This technique of polynomial representation is known as Horner’s method.

As a general rule of the algorithm when the inputs are split into n parts each, there are 2n– 1 multiplications. Each multiplication is of multiplicands that have n times fewer digits than the inputs. The asymptotic running time of this algorithm is O(k^lgn(2n–1)) for k digit inputs (assuming they have the same number of digits). Figure 5.7 summarizes the exponents for various values of n.

At first, it may seem like a good idea to choose n = 1000 since the exponent is approximately 1 · 1. However, the overhead of solving for the 2001 terms of W(x) will certainly consume any savings the algorithm could offer for all but exceedingly large numbers.

5.2.5 Karatsuba Multiplication

Karatsuba [5] multiplication when originally proposed in 1962 was among the first set of algorithms to break the O(n²) barrier for general-purpose multiplication.

Given two polynomial basis representations f(x) = ax+ b and g(x) = cx+ d, Karatsuba proved with light algebra [5] that the following polynomial is equivalent to multiplication of the two integers the polynomials represent.

(5.6)

Using the observation that ac and bd could be re-used, only three half-sized multiplications would be required to produce the product. Applying this algorithm recursively the work factor becomes O(n^lg(3)), which is substantially better than the work factor O(n²) of the Comba technique. It turns out what Karatsuba did not know or at least did not publish was that this is simply polynomial basis multiplication with the points ζ₀, ζ_∞, and ζ₁. Consider the resultant system of equations.

By adding the first and last equation to the equation in the middle, the term w₁can be isolated and all three coefficients solved for. The simplicity of this system of equations has made Karatsuba fairly popular. In fact, the cutoff point is often fairly low³, making it an ideal algorithm to speed up certain public key cryptosystems such as RSA and Diffie-Hellman.

Algorithm mp_karatsuba_mul. This algorithm computes the unsigned product of two inputs using the Karatsuba multiplication algorithm. It is loosely based on the description from Knuth [1, pp. 294-295] (Figure 5.8).

To split the two inputs into their respective halves, a suitable radix point must be chosen. The radix point chosen must be used for both of the inputs, meaning that it must be smaller than the smallest input. Step 3 chooses the radix point B as half of the smallest input used count. After the radix point is chosen, the inputs are split into lower and upper halves. Steps 4 and 5 compute the lower halves. Steps 6 and 7 compute the upper halves.

After the halves have been computed the three intermediate half-size products must be computed. Step 8 and 9 compute the trivial products x 0 · y 0 and x 1 · y 1. The mp_int x 0 is used as a temporary variable after x 1 + x 0 has been computed. By using x 0 instead of an additional temporary variable, the algorithm can avoid an addition memory allocation operation.

The remaining steps 13 through 18 compute the Karatsuba polynomial through a variety of digit shifting and addition operations.

The new coding element in this routine, not seen in previous routines, is the usage of goto statements. The conventional wisdom is that goto statements should be avoided. This is generally true; however, when every single function call can fail, it makes sense to handle error recovery with a single piece of code. Lines 62 to 76 handle initializing all of the temporary variables required. Note how each of the if statements goes to a different label in case of failure. This allows the routine to correctly free only the temporaries that have been successfully allocated so far.

The temporary variables are all initialized using the mp_init_size routine since they are expected to be large. This saves the additional reallocation that would have been necessary. Moreover, x 0, x 1, y 0, and y 1 have to be able to hold at least their respective number of digits for the next section of code.

The first algebraic portion of the algorithm is to split the two inputs into their halves. However, instead of using mp_mod_2d and mp_rshd to extract the halves, the respective code has been placed inline within the body of the function. To initialize the halves, the used and sign members are copied first. The first for loop on Line 96 copies the lower halves. Since they are both the same magnitude, it is simpler to calculate both lower halves in a single loop. The for loop on lines 102 and 107 calculate the upper halves x 1 and y 1, respectively.

By inlining the calculation of the halves, the Karatsuba multiplier has a slightly lower overhead and can be used for smaller magnitude inputs.

When Line 151 is reached, the algorithm has completed successfully. The “error status” variable err is set to MP_OKAY so the same code that handles errors can be used to clear the temporary variables and return.

5.2.6 Toom-Cook 3-Way Multiplication

The 3-Way multiplication scheme, usually known as Toom–Cook, is actually a variation of the Toom–Cook multiplication [1, pp. 296–299] algorithm. In their combined approach, multiplication is essentially linearized by increasing the number of ways as the size of the inputs increase. The 3-Way approach is the polynomial basis algorithm for n = 2, except that the points are chosen such that ζ is easy to compute and the resulting system of equations easy to reduce. Here, the points ζ₀, 16 ·ζ_1/2, ζ₁, ζ₂, and ζ_∞make up the five required points to solve for the coefficients of W(x).

With the five relations Toom-Cook specifies, the following system of equations is formed.

A trivial solution to this matrix requires 12 subtractions, two multiplications by a small power of two, two divisions by a small power of two, two divisions by three, and one multiplication by three. All of these 19 sub-operations require less than quadratic time, meaning that the algorithm can be faster than a baseline multiplication. However, the greater complexity of this algorithm places the cutoff point (TOOM_MUL_CUTOFF) where Toom-Cook becomes more efficient much higher than the Karatsuba cutoff point.

Algorithm mp_toom_mul. This algorithm computes the product of two mp_int variables a and b using the Toom-Cook approach. Compared to the Karatsuba multiplication, this algorithm has a lower asymptotic running time of approximately O(n^1.464) but at an obvious cost in overhead. In this description, several statements have been compounded to save space. The intention is that the statements are executed from left to right across any given step (Figure 5.9).

The two inputs a and b are first split into three k-digit integers a₀, a₁, a₂and b₀, b₁, b₂, respectively. From these smaller integers the coefficients of the polynomial basis representations f(x) and g(x) are known and can be used to find the relations required.

The first two relations w₀and w₄are the points ζ₀and ζ_∞, respectively. The relation w₁, W₂, and w₃correspond to the points 16 · ζ_1/2, ζ₂and ζ₁, respectively. These are found using logical shifts to independently find f(y) and g(y) which significantly speeds up the algorithm.

After the five relations w₀, w₁, …, w₄have been computed, the system they represent must be solved in order for the unknown coefficients w₁, w₂, and w₃to be isolated. Steps 18 through 25 perform the system reduction required as previously described. Each step of the reduction represents the comparable matrix operation that would be performed had this been performed by pencil. For example, step 18 indicates that row 1 must be subtracted from row 4, and simultaneously row 0 subtracted from row 3.

Once the coefficients have been isolated, the polynomial is known. By substituting β^kfor x, the integer result a. b is produced.

The first obvious thing to note is that this algorithm is complicated. The complexity is worth it if you are multiplying very large numbers. For example, a 10,000 digit multiplication takes approximately 99,282,205 fewer single precision multiplications with Toom-Cook than a Comba or baseline approach (a savings of more than 99%). For most “crypto” sized numbers this algorithm is not practical, as Karatsuba has a much lower cutoff point.

First, we split a and b into three roughly equal portions. This has been accomplished (lines 41 to 70) with combinations of mp_rshd() and mp_mod_2d() function calls. At this point, a= a 2 · β²+ a 1 · β+ a 0, and similarly for b.

Next, we compute the five points w 0, w 1, w 2, w 3, and w 4. Recall that w 0 and w 4 can be computed directly from the portions so we get those out of the way first (lines 73 and 78). Next, we compute w 1, w 2, and w 3 using Horner’s method.

After this point we solve for the actual values of w 1, w 2, and w 3 by reducing the 5 × 5 system, which is relatively straightforward.

5.2.7 Signed Multiplication

Now that algorithms to handle multiplications of every useful dimensions have been developed, a rather simple finishing touch is required. So far, all of the multiplication algorithms have been unsigned multiplications, which leaves only a signed multiplication algorithm to be established.

Algorithm mp_mul. This algorithm performs the signed multiplication of two inputs (Figure 5.10). It will make use of any of the three unsigned multiplication algorithms available when the input is of appropriate size. The sign of the result is not set until the end of the algorithm, since algorithm s_mp_mul_digs (Figure 5.1) will clear it.

The implementation is rather simplistic and is not particularly noteworthy. Line 22 computes the sign of the result using the “?” operator from the C programming language. Line 48 computes δ using the fact that 1 << k is equal to 2^k.

5.3.1 The Baseline Squaring Algorithm

The baseline squaring algorithm is meant to be a catch-all squaring algorithm. It will handle any of the input sizes that the faster routines will not handle.

Algorithm s_mp_sqr. This algorithm computes the square of an input using the three observations on squaring. It is based fairly faithfully on algorithm 14.16 of HAC [2, pp.596-597]. Similar to algorithm s_mp_mul_digs, a temporary mp_int is allocated to hold the result of the squaring. This allows the destination mp_int to be the same as the source mp_int (Figure 5.12).

The outer loop of this algorithm begins on step 4. It is best to think of the outer loop as walking down the rows of the partial results, while the inner loop computes the columns of the partial result. Steps 4.1 and 4.2 compute the square term for each row, and steps 4.3 and 4.4 propagate the carry and compute the double products.

The requirement that an mp_word be able to represent the range 0 ≤ x < 2β²arises from this very algorithm. The product a_ixa_iywill lie in the range 0 ≤ x≤ β²– 2β+1, which is obviously less than β², meaning that when it is multiplied by two, it can be properly represented by an mp_word.

Similar to algorithm s_mp_mul_digs, after every pass of the inner loop, the destination is correctly set to the sum of all of the partial results calculated so far. This involves expensive carry propagation, which will be eliminated in the next algorithm.

Inside the outer loop (line 34) the square term is calculated on Line 37. The carry (Line 44) has been extracted from the mp_word accumulator using a right shift. Aliases for a_ixand t_{ix+ iy}are initialized (lines 47 and 50) to simplify the inner loop. The doubling is performed using two additions (Line 59), since it is usually faster than shifting, if not at least as fast.

The important observation is that the inner loop does not begin at iy= 0 like for multiplication. As such, the inner loops get progressively shorter as the algorithm proceeds. This is what leads to the savings compared to using a multiplication to square a number.

5.3.2 Faster Squaring by the “Comba” Method

A major drawback to the baseline method is the requirement for single precision shifting inside the O(n²) nested loop. Squaring has an additional drawback in that it must double the product inside the inner loop as well. As for multiplication, the Comba technique can be used to eliminate these performance hazards.

The first obvious solution is to make an array of mp_words that will hold all the columns. This will indeed eliminate all of the carry propagation operations from the inner loop. However, the inner product must still be doubled O(n²) times. The solution stems from the simple fact that 2a+ 2b+ 2c= 2(a+ b+ c). That is, the sum of all of the double products is equal to double the sum of all the products. For example, ab+ ba+ ac+ ca= 2ab+ 2ac= 2(ab+ ac).

However, we cannot simply double all the columns, since the squares appear only once per row. The most practical solution is to have two mp_word arrays. One array will hold the squares, and the other will hold the double products. With both arrays, the doubling and carry propagation can be moved to a O(n) work level outside the O(n²) level. In this case, we have an even simpler solution in mind.

Algorithm fast_s_mp_sqr. This algorithm computes the square of an input using the Comba technique. It is designed to be a replacement for algorithm s_mp_sqr when the number of input digits is less than MP_WARRAY and less than δ/2. This algorithm is very similar to the Comba multiplier, except with a few key differences we shall make note of (Figure 5.13).

First, we have an accumulator and carry variables _Ŵ and Ŵ 1, respectively. This is because the inner loop products are to be doubled. If we had added the previous carry in we would be doubling too much. Next, we perform an addition MIN condition on iy(step 5.5) to prevent overlapping digits. For example, a₃. a₅is equal a₅. a₃, whereas in the multiplication case we would have 5 < a.used, and 3 ≥ 0 is maintained since we double the sum of the products just outside the inner loop, which we have to avoid doing. This is also a good thing since we perform fewer multiplications and the routine ends up being faster.

The last difference is the addition of the “square” term outside the inner loop (step 5.8). We add in the square only to even outputs, and it is the square of the term at the ix/2 position.

This implementation is essentially a copy of Comba multiplication with the appropriate changes added to make it faster for the special case of squaring. The innermost loop (lines 72 to 74) computes the products the same way the multiplication routine does. The sum of the products is doubled separately (Line 77) outside the innermost loop. The square term is added if ix is even (lines 80 to 82), indicating column with a square.

5.3.3 Even Faster Squaring

Just like the case of algorithm fast_mult (Section 5.2.3), squaring can be performed using the full precision of single precision variables. This algorithm borrows much from the algorithm in Figure 5.13. Except that, in this case, we will be accumulating into a triple-precision accumulator. Similarly, loop unrolling can boost the performance of this operation significantly.

The TomsFastMath library incorporates fast squaring that is a direct port of algorithm fast_s_mp_sqr. Readers are encouraged to research this project to learn more.

5.3.4 Polynomial Basis Squaring

The same algorithm that performs optimal polynomial basis multiplication can be used to perform polynomial basis squaring. The minor exception is that ζ_y= f(y)g(y) is actually equivalent to ζ_y= f(y)², since f(y)= g(y). Instead of performing 2n+ 1 multiplications to find the ζ relations, squaring operations are performed instead.

5.3.5 Karatsuba Squaring

Let f(x) = ax+ b represent the polynomial basis representation of a number to square. Let h(x) = (f(x))²represent the square of the polynomial. The Karatsuba equation can be modified to square a number with the following equation.

(5.7)

Upon closer inspection, this equation only requires the calculation of three half-sized squares:a², b², and (a+ b)². As in Karatsuba multiplication, this algorithm can be applied recursively on the input and will achieve an asymptotic running time of O(n^lg(3)).

If the asymptotic times of Karatsuba squaring and multiplication are the same, why not simply use the multiplication algorithm instead? The answer to this arises from the cutoff point for squaring. As in multiplication, there exists a cutoff point, at which the time required for a Comba–based squaring and a Karatsuba–based squaring meet. Due to the overhead inherent in the Karatsuba method, the cutoff point is fairly high. For example, on an AMD Athlon XP processor with β= 2²⁸, the cutoff point is around 127 digits.

Consider squaring a 200-digit number with this technique. It will be split into two 100-digit halves that are subsequently squared. The 100-digit halves will not be squared using Karatsuba, but instead using the faster Comba–based squaring algorithm. If Karatsuba multiplication were used instead, the 100-digit numbers would be squared with a slower Comba–based multiplication.

Algorithm mp_karatsuba_sqr. This algorithm computes the square of an input a using the Karatsuba technique. It is very similar to the Karatsuba–based multiplication algorithm with the exception that the three half-size multiplications have been replaced with three half-size squarings (Figure 5.14).

The radix point for squaring is simply placed exactly in the middle of the digits when the input has an odd number of digits; otherwise, it is placed just below the middle. Steps 3, 4, and 5 compute the two halves required using B as the radix point. The first two squares in steps 6 and 7 are straightforward, while the last square is of a more compact form.

By expanding (x 1 + x 0)², the x 1²and x 0²terms in the middle disappear; that is, (x 0 – x 1)²– (x 1²+ x 0²) = 2 · x 0 · x 1. Now if 5n single precision additions and a squaring of n-digits is faster than multiplying two n-digit numbers and doubling, then this method is faster. Assuming no further recursions occur, the difference can be estimated with the following inequality.

Let p represent the cost of a single precision addition and q the cost of a single precision multiplication both in terms of time⁴.

(5.8)

For example, on an AMD Athlon XP processor, p=1/3 q=6. This implies that the following inequality should hold.

This results in a cutoff point around n= 2. As a consequence, it is actually faster to compute the middle term the “long way” on processors where multiplication is substantially slower⁵than simpler operations such as addition.

This implementation is largely based on the implementation of algorithm mp_karatsuba_mul. It uses the same inline style to copy and shift the input into the two halves. The loop from Line 54 to Line 70 has been modified since only one input exists. The used count of both x 0 and x 1 is fixed up, and x 0 is clamped before the calculations begin. At this point, x 1 and x 0 are valid equivalents to the respective halves as if mp_rshd and mp_mod_2d had been used.

By inlining the copy and shift operations, the cutoff point for Karatsuba multiplication can be lowered. On the Athlon, the cutoff point is exactly at the point where Comba squaring can no longer be used (128 digits). On slower processors such as the Intel P4, it is actually below the Comba limit (at 110 digits).

This routine uses the same error trap coding style as mp_karatsuba_sqr. As the temporary variables are initialized, errors are redirected to the error trap higher up. If the algorithm completes without error, the error code is set to MP_OKAY and mp_clears are executed normally.

5.3.6 Toom-Cook Squaring

The Toom-Cook squaring algorithm mp_toom_sqr is heavily based on the algorithm mp_toom_mul, with the exception that squarings are used instead of multiplication to find the five relations. Readers are encouraged to read the description of the latter algorithm and try to derive their own Toom-Cook squaring algorithm.

5.3.7 High Level Squaring

Algorithm mp_sqr. This algorithm computes the square of the input using one of four different algorithms. If the input is very large and has at least TOOM_SQR_CUTOFF or KARATSUBA_SQR_CUTOFF digits, then either the Toom-Cook or the Karatsuba Squaring algorithm is used. If neither of the polynomial basis algorithms should be used, then either the Comba or baseline algorithm is used (Figure 5.15).

Exercises