Patent attributes
A one-dimensional Fourier transform program for quickly performing a one-dimensional Fourier transform intended for a scalar computer comprises a step of resolving a data length N of one-dimensional data into the product of factors N1×N2×. . . ×Nm, a step of setting the data length N as P×Q, calculating twiddle factors that are required for a multiplication with results of a one-dimensional Fourier transform of a length Q, which is performed by P times, for an initial one of Q-1 twiddle factors for multiplication intended for each of P Fourier transform results, while changing P and Q, and storing calculation results in a table, and a step of performing a Fourier transform of data as m separated phases with the table for storing the calculated twiddle factors.
