Comparing Partial and Full Return Spectral Methods

An analysis on the arithmetic complexity of recently proposed spectral modular arithmetic - in particular spectral modular multiplication-is presented through a step-by-step evaluation. Standart use of spectral methods in computer arithmetic instructs to utilize separated multiplication and reduction steps taking place in spectrum and time domains respectively. Such a procedure clearly needs full return (forward and backward) DFT calculations. On the other hand, by calculating some partial values on-the-fly, new methods adopt an approach that keeps the data in the spectrum at all times, including the reduction process. After comparing the timing performances of these approaches, it is concluded that full return algorithms perform better than the recently proposed methods.