square.txt (2403B)
1 Squaring Algorithm 2 3 When you are squaring a value, you can take advantage of the fact that 4 half the multiplications performed by the more general multiplication 5 algorithm (see 'mul.txt' for a description) are redundant when the 6 multiplicand equals the multiplier. 7 8 In particular, the modified algorithm is: 9 10 k = 0 11 for j <- 0 to (#a - 1) 12 w = c[2*j] + (a[j] ^ 2); 13 k = w div R 14 15 for i <- j+1 to (#a - 1) 16 w = (2 * a[j] * a[i]) + k + c[i+j] 17 c[i+j] = w mod R 18 k = w div R 19 endfor 20 c[i+j] = k; 21 k = 0; 22 endfor 23 24 On the surface, this looks identical to the multiplication algorithm; 25 however, note the following differences: 26 27 - precomputation of the leading term in the outer loop 28 29 - i runs from j+1 instead of from zero 30 31 - doubling of a[i] * a[j] in the inner product 32 33 Unfortunately, the construction of the inner product is such that we 34 need more than two digits to represent the inner product, in some 35 cases. In a C implementation, this means that some gymnastics must be 36 performed in order to handle overflow, for which C has no direct 37 abstraction. We do this by observing the following: 38 39 If we have multiplied a[i] and a[j], and the product is more than half 40 the maximum value expressible in two digits, then doubling this result 41 will overflow into a third digit. If this occurs, we take note of the 42 overflow, and double it anyway -- C integer arithmetic ignores 43 overflow, so the two digits we get back should still be valid, modulo 44 the overflow. 45 46 Having doubled this value, we now have to add in the remainders and 47 the digits already computed by earlier steps. If we did not overflow 48 in the previous step, we might still cause an overflow here. That 49 will happen whenever the maximum value expressible in two digits, less 50 the amount we have to add, is greater than the result of the previous 51 step. Thus, the overflow computation is: 52 53 54 u = 0 55 w = a[i] * a[j] 56 57 if(w > (R - 1)/ 2) 58 u = 1; 59 60 w = w * 2 61 v = c[i + j] + k 62 63 if(u == 0 && (R - 1 - v) < w) 64 u = 1 65 66 If there is an overflow, u will be 1, otherwise u will be 0. The rest 67 of the parameters are the same as they are in the above description. 68 69 ------------------------------------------------------------------ 70 This Source Code Form is subject to the terms of the Mozilla Public 71 # License, v. 2.0. If a copy of the MPL was not distributed with this 72 # file, You can obtain one at http://mozilla.org/MPL/2.0/.