Methods of squaring and multiplying large integers are discussed. The obvious O(n/sup 2/) methods turn out to be best for small numbers. Existing O(n/sup log/ /sup 3/log/ /sup 2/)/spl ap/O(n/sup 1.585/) methods become better as the numbers get bigger. New methods that are O(/sup log5/log/ /sup 3/)/spl ap/0(n/sup 1.465/), O(n/sup log/ /sup 7/log/ /sup 4/)/spl ap/O(n/sup 1.404/), and O(n/sup log/ /sup 9/log/ /sup 5/)/spl ap/O(n/sup 1.365/) presented. In actual experiments, all of these methods turn out to be faster than FFT multipliers for numbers that can be quite large (>37,000,000 bits). Squaring seems to be fundamentally faster than multiplying but it is shown that T/sub multiplyspl les/2T/sub square/+O(n).>

Methods of squaring large integers are discussed. The obvious O(n/sup 2/) method turns out to be best for small numbers. The existing /spl ap/ O(n/sup 1.585/) method becomes better as the numbers get bigger. New methods that are /spl ap/ O(n/sup 1.465/) and /spl ap/ O(n/sup 2.404/) are presented. All of these methods can be generalized to multiplication and turn out to be faster than a fast Fourier transform (FFT) multiplication for numbers that can be quite large (>3,000,000 b). Squaring seems to be fundamentally faster than multiplication, but it is shown that T/sub mult/ /spl les/ 2T/sub sq/ + O(n).>

In recent years, many architectural design efforts have focused on maximizing performance for frequently executed, simple instructions. The authors describe how a small set of primitive instructions combined with what is considered careful frequency analysis and clever programming allows the Hewlett-Packard (HP) Precision Architecture integer multiplication and division implementation to provide adequate performance at little or no hardware cost.>

In recent years, many architectural design efforts have focused on maximizing performance for frequently executed, simple instructions. Although these efforts have resulted in machines with better average price/performance ratios, certain complex instructions and, thus, certain classes of programs which heavily depend on these instructions may suffer by comparison. Integer multiplication and division are one such set of complex instructions. This paper describes how a small set of primitive instructions combined with careful frequency analysis and clever programming allows the Hewlett-Packard Precision Architecture integer multiplication and division implementation to provide adequate performance at little or no hardware cost.