An optimal multiplication algorithm for reconfigurable mesh

It is shown that multiplication of two N-bit integers can be performed in O(1) time on N×N reconfigurable mesh. This result is obtained by combining the O(1) time multiplication algorithm on N×N ² reconfigurable mesh, the Rader transform, and decomposition of one-dimensional convolution into multidimensional convolution. Choosing the Radar transform at the expense of long word length frees one from storing twiddle factors in advance, which is needed in other designs. It is also shown that the present algorithm can be simulated on other restricted reconfigurable mesh models without asymptotic increase in time or number of processing elements. It is shown that the present result can be extended to provide area-time tradeoffs in the usual bit model of VLSI to satisfy AT² optimality over 1⩽T⩽√N