Fast evaluation of iterated multiplication of very large polynomials: An application to chinese remainder theory
David Laing, Bruce E. Litow · ANZIAM Journal · 2007
We consider the problem of exactly computing the number of integers in a Chinese Remainder Representation (CRR) whose pseudorank does not equal the rank. We call this number the census. The rank is key in developing CRR-intrinsic methods for comparing integers in CRR, a problem known to be notoriously difficult. Pseudorank can be computed in highly restrictive computation models. We have developed and implemented a fast, efficient algorithm for computing the census based on using a variant of the FFT to compute iterated products of polynomials of very large degree, and with arbitrary size integer coefficients. Experimental census results are tabulated. This census information makes possible a new approach to exploring the fine structure of CRR. References J. Hee. Fast convolution using polynomial transforms. http://jenshee.dk/signalprocessing/polytrans.pdf, 2004. W. Hesse. Division is in uniform tc0. In ICALP '01: Proceedings of the 28th International Colloquium on Automata, Languages and Programming, pages 104--114, London, UK, 2001. Springer--Verlag. Also available as http://people.clarkson.edu/ whesse/div.ps. D. Knuth. Seminumerical Algorithms, volume 1 of The Art of Computer Programming, section 4.3.2. Addison--Wesley, third edition, 1997. W. Kuich and A. Salomaa. Semirings,Automata,Languages. Springer-Verlag, 1986. B. Litow and D. Laing. A census algorithm for chinese remainder pseudorank with experimental results. James Cook University, School of IT Tech Report http://www.cs.jcu.edu.au/ftp/pub/techreports/2005-3.pdf, 2005. H. J. Nussbaumer. Fast Fourier Transform and Convolution Algorithms. Springer, 1982. 2nd ed. A. Salomaa and S. Soittola. Automata Theoretic Aspects of Formal Power Series. Springer--Verlag, 1978. M. P. Schutzenberger. On a theorem of {Jungen}. Proc. Am. Math. Soc., 13:885--890, 1962. R. Tanaka and N. Szabo. Residue Arithmetic and its Application to Computer Technology. McGraw--Hill, 1968. S. P. Tarasov and M. N. Vyalyi. Semidefinite programming and arithmetic circuit evaluation. Technical report, 2005. Available as http://arxiv.org/abs/cs/0512035v1. G. Davida A. Chiu and B. Litow. Division in logspace-uniform NC$^1$. Theoretical Informatics and Applications, 35:259--275, 2001. doi:10.1051/ita:2001119 I. M. Vinagradov. Elements of Number Theory. Dover, 1954. S. A. Cook and S. O. Aanderaa. On the minimum computation time of functions. Transactions of the American Mathematical Society, 142:291--314, Aug 1969. K. Culik and J. Kari. Handbook of Formal Languages, chapter 10, pages 599--616. Springer, 1997. G. Davida and B. Litow. Fast parallel arithmetic via modular representation. SIAM J. Comp., 20,4:756--765, 1991. doi:10.1137/0220048