Multiplication

S. B. Gashkov ; I. S. Sergeev

Čebyševskij sbornik, Tome 21 (2020) no. 1, pp. 101-134.

Résumé

The paper provides a survey of the modern state of the theory of fast multiplication of numbers and polynomials. We consider the development of multiplication methods from the initial block algorithms of 1960s due to Karatsuba and Toom to the methods of 1970s based on the Discrete Fourier transform (DFT) and further to the novel methods invented in 2007–2009. Modern multiplication methods combine exploiting of special algebraic structures, the use of approximate computations, special forms of Fourier transforms, namely, multidimensional DFT, additive analogue of DFT. These and other concepts essential for the fast multiplication algorithms are thoroughly discussed in the present survey. In particular, we provide an introduction to the theory of DFT with derivation of facts necessary for the exposition. The final part of the survey contains a brief discussion of results on parallel multiplication algorithms, accurate complexity bounds of the basic methods, online multiplication algorithms, multiplicative complexity of the multiplication of polynomials over finite fields. We mention computational models where multiplication has either linear, or quadratic complexity.

Détail

Keywords: fast computations, multiplication, complexity, discrete Fourier transform, additive DFT.

Bibliographie

[1] Aho A. V., Hopcroft J. E., Ullman J. D., The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass., 1976 | MR

[2] Blahut R. E., Fast algorithms for digital signal processing, Addison-Wesley, Reading, Mass., 1985 | MR | MR | Zbl

[3] Vlasenko V. A., Lappa Yu. M., Jaroslavsky L. P., Methods to design the fast convolution algorithms and spectral signal analysis, Nauka, M., 1990 (in Russian) | MR

[4] Gashkov S. B., “Remarks on the fast multiplication of polynomials, and Fourier and Hartley transforms”, Discrete Math. and Appl., 12:3 (2000), 124–153 | MR | Zbl

[5] Gashkov S. B., Sergeev I. S., “Fast Fourier transform algorithms”, Discrete mathematics and its applications. V, Keldysh Inst. Appl. Math., M., 2009, 3–23 (in Russian)

[6] Gashkov S. B., Sergeev I. S., “On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic 2”, Discrete Math. and Appl., 23:1 (2013), 1–37 | DOI | MR | Zbl

[7] Grinchuk M. I., “Sharpening an upper bound on the adder and comparator depths”, J. Appl. and Industr. Math., 3:1 (2009), 61–67 | MR | Zbl

[8] Karatsuba A. A., Ofman Yu. P., “Multiplication of multidigit numbers on automata”, Soviet Physics Doklady, 7 (1963), 595–596 | MR

[9] Karatsuba A. A., “The complexity of computations”, Proc. Steklov Inst. Math., 211 (1995), 169–183 | MR | Zbl

[10] Karatsuba A. A., “Comments to my works, written by myself”, Proc. Steklov Inst. Math., 282, suppl. 1 (2013), S1–S23 | DOI | MR | Zbl

[11] Knuth D. E., The art of computer programming, v. 2, Seminumerical algorithms, 3rd ed., Addison–Wesley Longman, Reading, Mass., 1998 | MR

[12] Lupanov O. B., Asymptotic bounds on the complexity of control systems, Mosk. Gos. Univ., M., 1984 (in Russian)

[13] Lupanov O. B., “A. N. Kolmogorov and the circuit complexity theory”, Mathematical issues of cybernetics, 17, Fizmatlit, M., 2008, 5–12 (in Russian)

[14] Nussbaumer H. J., Fast Fourier transform and convolution algorithms, 2nd ed., Springer, Berlin–Heidelberg, 1982 | MR | MR

[15] Red'kin N. P., “On the minimal realization of the binary adder”, Problems of cybernetics, 38, Nauka, M., 1981, 181–216 (in Russian)

[16] Sergeev I. S., “Regular estimates for the complexity of polynomial multiplication and truncated Fourier transform”, Applied discrete mathematics, 2011, no. 4(14), 72–88 (in Russian)

[17] Sergeev I. S., “Upper bounds on the depth of symmetric Boolean functions”, Univ. Comput. Math. and Cybernetics, 37:4 (2013), 195–201 | MR | Zbl

[18] Sergeev I. S., “On the circuit complexity of the standard and the Karatsuba methods of multiplying integers”, Proc. 22th Int. Sci.-Tech. Conf. “Information tools and technologies”, v. 3, Izd. dom MEI, M., 2014, 180–187 (in Russian); 2016, arXiv: 1602.02362

[19] Sergeev I. S., “Complexity and depth of formulas for symmetric Boolean functions”, Moscow Univ. Math. Bulletin, 71:3 (2016), 127–130 | DOI | MR | Zbl

[20] Sergeev I. S., “On the real complexity of a complex DFT”, Problems of Information Transmission, 53:3 (2017), 284–293 | DOI | MR | Zbl

[21] Slisenko A. O., “Complexity problems in computational theory”, Russian Math. Surveys, 36:6 (1981), 23–125 | DOI | MR | Zbl | Zbl

[22] Toom A. L., “The complexity of a scheme of functional elements realizing the multiplication of integers”, Soviet Math. Doklady, 3 (1963), 714–716 | MR | Zbl

[23] Khrapchenko V. M., “Asymptotic estimation of addition time of a parallel adder”, Systems Theory Research, 19 (1970), 105–122

[24] Khrapchenko V. M., “Some estimates for the multiplication time”, Problems of cybernetics, 33, Nauka, M., 1978, 221–227 (in Russian) | MR

[25] Chashkin A. V., Discrete mathematics, Akademiya, M., 2012 (in Russian)

[26] Shkalikova N. A., “On the complexity of realization of some functions by cellular circuits”, Selected papers on math. cybernetics, 1, Izd. Vychisl. Ts. AN SSSR, M., 1976, 102–115 (in Russian) | MR

[27] Adleman L. M., Pomerance C., Rumely R. S., “On distinguishing prime numbers from composite numbers”, The Annals of Mathematics, Second Series, 117:1 (1983), 173–206 | DOI | MR | Zbl

[28] Agarwal R. C., Cooley J. W., “New algorithms for digital convolution”, IEEE Trans. on ASSP, 25:5 (1977), 392–410 | DOI | Zbl

[29] Arnold A., “A new truncated Fourier transform algorithm”, Proc. Int. Symp. on Symbolic and Algebraic Comp. (Boston, 2013), ACM, NY, 2013, 15–22 | MR | Zbl

[30] Avizienis A., “Signed-digit number representations for fast parallel arithmetic”, IRE Trans. on Electr. Computers, EC10 (1961), 389–400 | DOI | MR

[31] Ballet S., Chaumine J., Pieltant J., Rolland R., On the tensor rank of multiplication in finite fields, 2011, arXiv: 1107.1184 | MR

[32] Bernstein D. J., “Fast multiplication and its applications”, Algorithmic Number Theory, MSRI Publ., 44, ACM, NY, 2008, 325–384 | MR

[33] Bernstein D. J., Chou T., “Faster binary-field multiplication and faster binary-field MACs”, Lecture Notes on Comp. Sci., 8781, 2014, 92–111 | DOI | MR | Zbl

[34] Bluestein L. I., “A linear filtering approach to the computation of discrete Fourier transform”, ECCC Trans. on Audio and Electroacoustics, 18:4 (1970), 451–455 ; NEREM record, 10 (1968), 218–219 | DOI

[35] Cantor D. G., “On arithmetical algorithms over finite fields”, J. Comb. Theory. Series A, 50 (1989), 285–300 | DOI | MR | Zbl

[36] Cantor D., Kaltofen E., “On fast multiplication of polynomials over arbitrary algebras”, Acta Inf., 28:7 (1991), 693–701 | DOI | MR | Zbl

[37] Cenk M., Hasan M. A., “Some new results on binary polynomial multiplication”, J. Cryptographic Engineering, 5:4 (2015), 289–303 | DOI

[38] Chen M.-S., Cheng C.-M., Kuo P.-C., Li W.-D., Yang B.-Y., Multiplying boolean polynomials with Frobenius partitions in additive fast Fourier transform, 2018, arXiv: 1803.11301 | MR

[39] Chudnovsky D. V., Chudnovsky G. V., “Algebraic complexities and algebraic curves over finite fields”, J. Complexity, 4 (1988), 285–316 | DOI | MR | Zbl

[40] Cook S., On the minimum computation time of functions, Ph.D. Thesis, Harvard Univ., 1966 | MR

[41] Cooley J. W., Tukey J. W., “An algorithm for the machine calculation of complex Fourier series”, Math. Comp., 19:90 (1965), 297–301 | DOI | MR | Zbl

[42] Crandall R., Fagin B., “Discrete weighted transforms and large-integer arithmetic”, Math. Comp., 62:205 (1994), 305–324 | DOI | MR | Zbl

[43] De A., Kurur P. P., Saha C., Saptharishi R., “Fast integer multiplication using modular arithmetic”, SIAM J. Comput., 42:2 (2013), 685–699 | DOI | MR | Zbl

[44] Demenkov E., Kojevnikov A., Kulikov A., Yaroslavtsev G., “New upper bounds on the Boolean circuit complexity of symmetric functions”, Inf. Proc. Letters, 110:7 (2010), 264–267 | DOI | MR | Zbl

[45] Dutt A., Rokhlin V., “Fast Fourier transforms for nonequispaced data”, SIAM J. Sci. Comput., 14:6 (1993), 1368–1393 | DOI | MR | Zbl

[46] Find M. G., Peralta R., “Better circuits for binary polynomial multiplication”, IEEE Trans. on Comp., 68:4 (2019), 624–630 | DOI | MR | Zbl

[47] Fischer M. J., Stockmeyer L., “Fast on-line integer multiplication”, J. Comput. and System Sci., 9 (1974), 317–331 | DOI | MR | Zbl

[48] Fürer M., On the complexity of integer multiplication (extended abstract), Tech. Report CS-89-17, Pennsylvania State Univ., 1989

[49] Fürer M., “Faster integer multiplication”, SIAM J. Comput., 39:3 (2009), 979–1005 | DOI | MR | Zbl

[50] Fürer M., How fast can we multiply large integers on an actual computer?, Proc. Latin Amer. Symp. on Theor. Inf. (Montevideo, 2014), Lecture Notes on Comp. Sci., 8392, 2014, 660–670 | DOI | MR | Zbl

[51] Gao S., Mateer T., “Additive fast Fourier transforms over finite fields”, IEEE Trans. on Information Theory, 56 (2010), 6265–6272 | DOI | MR | Zbl

[52] von zur Gathen J., Gerhard J., “Arithmetic and factorization of polynomials over $\mathbb{F}_2$”, Proc. Int. Symp. on Symbolic and Algebraic Comp. (Zürich, 1996), ACM, NY, 1996, 1–9 | Zbl

[53] von zur Gathen J., Gerhard J., Modern computer algebra, Cambridge University Press, Cambridge, 1999 | MR | Zbl

[54] Good I. J., “The interaction algorithm and practical Fourier analysis”, J. R. Statist. Soc. B, 20:2 (1958), 361–372 ; 22:2 (1960), 372–375 | MR | Zbl | Zbl

[55] Harvey D., van der Hoeven J., Lecerf G., “Even faster integer multiplication”, J. Complexity, 36 (2016), 1–30 | DOI | MR | Zbl

[56] Harvey D., van der Hoeven J., Lecerf G., “Faster polynomial multiplication over finite fields”, J. ACM, 63:6 (2017), 52 | DOI | MR | Zbl

[57] Harvey D., van der Hoeven J., Faster integer and polynomial multiplication using cyclotomic coefficient rings, 2017, arXiv: 1712.03693 | MR

[58] Harvey D., van der Hoeven J., “Faster integer multiplication using short lattice vectors”, Proc. 13th Algorithm. Number Theory Symp. (Madison, Wisconsin, 2018), Math. Sci. Publ., Berkeley, 2019, 293–310 | MR

[59] Harvey D., van der Hoeven J., Integer multiplication in time $O(n\log n)$, Tech. report No 02070778, HAL, 2019

[60] Harvey D., van der Hoeven J., Polynomial multiplication over finite fields in time $O(n\log n)$, Tech. report No 02070816, HAL, 2019 | MR

[61] Haynal S., Haynal H., “Generating and searching families of FFT algorithms”, J. Satisf., Boolean Modeling and Comput., 7:4 (2011), 145–187 | DOI | MR | Zbl

[62] Heideman M. T., Applications of multiplicative complexity theory to convolution and the discrete Fourier transform, Ph.D. Thesis, Rice Univ., 1986 | MR

[63] van der Hoeven J., “The truncated Fourier transform and applications”, Proc. Int. Symp. on Symbolic and Algebraic Comput. (Santander, 2004), ACM, NY, 2004, 290–296 | MR | Zbl

[64] van der Hoeven J., “Faster relaxed multiplication”, Proc. Int. Symp. on Symbolic and Algebraic Comp. (Kobe, 2014), ACM, NY, 2014, 405–412 | MR | Zbl

[65] van der Hoeven J., Larrieu R., “The Frobenius FFT”, Proc. Int. Symp. on Symbolic and Algebraic Comp. (Kaiserslautern, 2017), ACM, NY, 2017, 437–444 | MR | Zbl

[66] Johnson S. F., Frigo M., “A modified split-radix FFT with fewer arithmetic operations”, IEEE Trans. Signal Process, 55:1 (2007), 111–119 | DOI | MR | Zbl

[67] Li W.-D., Chen M.-S., Kuo P.-C., Cheng C.-M., Yang B.-Y., “Frobenius additive fast Fourier transform”, Proc. Int. Symp. on Symbolic and Algebraic Comp. (New York, 2018), ACM, NY, 2018, 263–270 | MR | Zbl

[68] Lundy T. J., van Buskirk J., “A new matrix approach to real FFTs and convolutions of length $2^k$”, Computing, 80:1 (2007), 23–45 | DOI | MR | Zbl

[69] Mateer T., Fast Fourier transform algorithms with applications, Ph.D. thesis, Clemson Univ., 2008 | MR

[70] Paterson M. S., Fischer M. J., Meyer A. R., An improved overlap argument for on-line multiplication, Tech. Report 40. Project MAC, MIT, 1974 | MR

[71] Paterson M. S., Pippenger N., Zwick U., “Optimal carry save networks”, Boolean function complexity, LMS Lecture Notes Series, 169, Cambridge Univ. Press, Cambridge, 1992, 174–201 | MR

[72] Paterson M., Zwick U., “Shallow circuits and concise formulae for multiple addition and multiplication”, Comput. Complexity, 3 (1993), 262–291 | DOI | MR | Zbl

[73] De Piccoli A., Visconti A., Rizzo O. G., Polynomial multiplication over binary finite fields: new upper bounds, Cryptology ePrint Archive, No 2018/901

[74] Pieltant J., Randriam H., “New uniform and asymptotic upper bounds on the tensor rank of multiplication in extensions of finite fields”, Math. Comp., 84 (2015), 2023–2045 | DOI | MR | Zbl

[75] Pollard J. M., “The Fast Fourier Transform in a finite field”, Math. Comp., 25:114 (1971), 365–374 | DOI | MR | Zbl

[76] Rader C. M., “Discrete Fourier transforms when the number of data samples is prime”, Proc. IEEE, 56 (1968), 1107–1108 | DOI

[77] Randriambololona H., “Bilinear complexity of algebras and the Chudnovsky—Chudnovsky interpolation method”, J. Complexity, 28:4 (2012), 489–517 | DOI | MR | Zbl

[78] Schönhage A., “Multiplikation großer Zahlen”, Computing, 1:3 (1966), 182–196 | DOI | MR | Zbl

[79] Schönhage A., Strassen V., “Schnelle Multiplikation großer Zahlen”, Computing, 7:3–4 (1971), 271–282 | MR

[80] Schönhage A., “Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2”, Acta Inf., 7 (1977), 395–398 | DOI | MR | Zbl

[81] Schönhage A., “Storage modification machines”, SIAM J. Comput., 9:3 (1980), 490–508 | DOI | MR | Zbl

[82] Schönhage A., “Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients”, Proc. Europ. Comput. Algebra Conf. (Marseille, 1982), Lecture Notes on Comp. Sci., 144, 1982, 3–15 | DOI | MR | Zbl

[83] Schönhage A., Grotefeld A. F. W., Vetter E., Fast algorithms: a multitape Turing machine implementation, BI-Wissenschaftsverlag, Mannheim–Leipzig–Wien–Zürich, 1994 | MR | Zbl

[84] Thomas L. H., “Using a computer to solve problem in Physics”, Application in digital computers, Ginn and Co, Boston, 1963

[85] Wang Y., Zhu X., “A fast algorithm for Fourier transform over finite fields and its VLSI implementation”, IEEE Journal on Selected Areas in Communications, 6:3 (1988), 572–577 | DOI

[86] Wegener I., The complexity of Boolean functions, Wiley-Teubner, Stuttgart, 1987 | MR | Zbl

[87] Winograd S., “On the multiplicative complexity of the discrete Fourier transform”, Advances in Math., 32:2 (1979), 83–117 | DOI | MR | Zbl

[88] Yavne R., “An economical method for calculating the discrete Fourier transform”, Proc. Fall Joint Computer Conf. (San Francisco, 1968), v. I, ACM, NY, 1968, 115–125

[89] Zheng W., Li K., Li K., “Scaled radix-2/8 algorithm for efficient computation of length-$N=2^m$ DFTs”, IEEE Trans. Signal Process., 62:10 (2014), 2492–2503 | DOI | MR | Zbl