Lazy multiplication of formal power series
Joris van der Hoeven · 1997
For most fast algorithms to manipulate formal power series, a fzustmultiplication algorithm is essential.If one desires to compute all coefficients of a product of two power series up to a given order, then several efficient algorithms are available, such as fast Fourier multiplication.However, one often needs a lazy multiplication algorithm, for instance when the product computation is part of the computation of the coefficients of an implicitly defined power series.In this paper, we describe two lazy multiplication algorithms, which are faster than the naive method.In articular, we Y give analgorithm oftimecomplexity O(nlog n). Key words: Imwer series, multiplication, algorithm.I'ermission to make rfigital/hard copy of all or part of this work for personal or classroom use is granted without fee provided that copies are not niade or dist rihuted for profit or commercial advantage, the