Abstract
Sometimes only some digits of a numerical product or some terms of a polynomial or series product are required. Frequently these constitute the most significant or least significant part of the value, for example when computing initial values or refinement steps in iterative approximation schemes. Other situations require the middle portion. In this paper we provide algorithms for the general problem of computing a given span of coefficients within a product, that is, the terms within a range of degrees for univariate polynomials or range digits of an integer. This generalizes the “middle product” concept of Hanrot, Quercia and Zimmerman. We are primarily interested in problems of modest size where constant speed up factors can improve overall system performance, and therefore focus the discussion on classical and Karatsuba multiplication and how methods may be combined.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Cook, S.A.: On the Minimum Computation Time of Functions. Ph.D. thesis, Harvard University (1966)
Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19(90), 297–301 (1965)
Hanrot, G., Quercia, M., Zimmermann, P.: The middle product algorithm I: Speeding up the division and square root of power series. Appl. Algebra Eng. Commun. Comput. 14, 415–438 (2004)
Hanrot, G., Zimmermann, P.: A long note on Mulders’ short product. J. Symbolic Comput. 37, 391–401 (2004)
van der Hoeven, J.: The truncated Fourier transform and applications. In: Proceedings of ISSAC 2004, pp. 290–296. ACM, New York (2004)
van der Hoeven, J., Lecerf, G.: On the complexity of multivariate blockwise polynomial multiplication. In: Proceedings of ISSAC 2012, pp. 211—218. ACM, New York (2012)
Karatsuba, A., Yu., O.: Multiplication of many-digital numbers by automatic computers. Proc. USSR Acad. Sci. 145, 293–294 (1962). Translation in the academic journal Physics-Doklady, 7 (1963), pp. 595–596
Knuth, D.E.: The Art of Computer Programming, Volume 4b: Combinatorial Algorithms, Part 2. Addison-Wesley, Boston (2022)
Mulders, T.: On short multiplication and division. In: Proceedings AAECC 11, 1, pp. 69–88 (2000)
Norman, A.C., Watt, S.M.: A symbolic computing perspective on software systems. arxiv:2406.09085, 1–18 (2024)
Toom, A.L.: The complexity of a scheme of functional elements realizing the multiplication of integers. Soviet Math. Doklady 3, 714–716 (1963)
Watt, S.M.: Efficient generic quotients using exact arithmetic. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC 2023), pp. 535–544. ACM, New York (2023)
Watt, S.M.: Efficient quotients of non-commutative polynomials. In: Boulier, F., England, M., Kotsireas, I., Sadykov, T.M., Vorozhtsov, E.V. (eds.) CASC 2023. LNCS, vol. 14139, pp. 370–392. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-41724-5_20
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Norman, A.C., Watt, S.M. (2024). Computing Clipped Products. In: Boulier, F., Mou, C., Sadykov, T.M., Vorozhtsov, E.V. (eds) Computer Algebra in Scientific Computing. CASC 2024. Lecture Notes in Computer Science, vol 14938. Springer, Cham. https://doi.org/10.1007/978-3-031-69070-9_16
Download citation
DOI: https://doi.org/10.1007/978-3-031-69070-9_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-69069-3
Online ISBN: 978-3-031-69070-9
eBook Packages: Computer ScienceComputer Science (R0)