The multiplication of univariate polynomials and multi-precision integers is one of the most basic, well-studied, and widely-used operations in mathematical computing. While asymptotic time complexity correlates with performance, it is well-known that memory access and cache misses also contribute significantly to the running time of computer programs. Unfortunately, all algorithms which achieve sub-quadratic time complexity for multiplication currently require at least O(n) auxiliary storage space for their implementation.

New algorithms are presented which achieve the same time complexity as Karatsuba's and FFT-based algorithms without requiring the use of an auxiliary array for temporary storage. We will discuss some optimizations and other issues encountered in writing a low-level C language implementation of these algorithms with the goal of high performance. The memory usage and cache performance will be compared to other existing software, and the effects on the actual running time will be examined. Finally, we will mention some future application areas and further extensions that could be beneficial.