Although any multiplication system could readily be used for squaring, specialized systems can provide both time and cost savings. Actually, normal multiplication requires *n*^{2} partial products while the maximum depth of the adding tree reaches *n* (maximum column depth in Figure 5.1a). Squaring only needs *n*(*n* − 1)/2 partial products, plus *n* digit-squares. Moreover, the adding process is simplified by the fact that each nonsquare partial product digit appears twice. As far as partial products are multiplied by two beforehand, the maximum depth of the adding tree is reduced to *n*/2. The complexity of squaring in base *B* > 2 comes from the fact that digit double products could need up to three digits while squaring only needs two. So the saving in column depth is consumed by second-order carries. For the particular case *B* = 2, the digit squaring is trivial as double products are performed through straight shifts. Moreover, Boolean simplification provides further reductions in the depth of the adding tree.

Algorithm 5.16 is a modification of the cellular carry-save Algorithm 5.5. It computes *X*^{2} + *C* + *D;* the main difference rests upon the (*i*, *j*)-cell loops, adding squares whenever *i* = *j*, and adding double products ...

Start Free Trial

No credit card required