The latter introduces the only significant inefficiency as most processors nowadays obtain residues after trial division, which is slow. However, this is performed just once for each output point. Discussion NTTs are most useful for convolution of sequences for the exact multiplication of large integers. We have shown that software simulations of NTTs which use integer arithmetic only significantly improve the efficiency of high-volume computation of mask processing techniques in neural networks. The overall effect is to produce a substantial reduction in execution time using fundamental algebraic reasoning alone.
Further optimization is possible when hierarchical memory access etc. is accounted for.
R.C. Agarwal and C.S. Burrus. Fast convolution using Fermat number transforms with applications to digital filtering. P.B. Bhattacharya, S.K. Jain, and S.R. Nagpaul. Basic Abstract Algebra . Cambridge University Press, Cambridge, UK, edition, 1986.