An efficient algorithm for doing this based on the convolution theorem uses a Fast Fourier Transform and an inverse Fast Fourier Transform before a combination step; that algorithm was slightly improved by Martin Furer. The "big-Oh of n to the log base 2 of 3" running time of one method for doing this task made it faster than the "big-Oh of n squared" naive approach since it reduced four operations to three. Algorithms that do this include the (*) Schonhage-Strassen algorithm and the Karatsuba algorithm, which is asymptotically slower than the more general Toom-Cook algorithm. In two's complement, this operation can be done by sign extending to 2n length to avoid ove
An efficient algorithm for doing this based on the convolution theorem uses a Fast Fourier Transform and an inverse Fast Fourier Transform before a combination step; that algorithm was slightly improved by Martin Furer. The "big-Oh of n to the log base 2 of 3" running time of one method for doing this task made it faster than the "big-Oh of n squared" naive approach since it reduced four operations to three. Algorithms that do this include the (*) Schonhage-Strassen algorithm and the Karatsuba algorithm, which is asymptotically slower than the more general Toom-Cook algorithm. In two's complement, this operation can be done by sign extending to 2n length to avoid overflow errors, and this operation with a 2 in binary is equivalent to shifting left once. For 10 points, name this operation whose identity is 1 and that is unfortunately explained as repeated addition.
An efficient algorithm for doing this based on the convolution theorem uses a Fast Fourier Transform and an inverse Fast Fourier Transform before a combination step; that algorithm was slightly improved by Martin Furer.
multiplication [accept word forms]