File Polynomial.h

↰ Parent directory (ADS/numeric)

The product of two polynomials of n coefficients each, the vectors p[ 0 .

Definition (ADS/numeric/Polynomial.h)

Detailed Description

. n - 1 ] and q[ 0 .. n - 1 ] from the constant one, into the 2 n - 1 coefficients of r = p q (section 12.3):

  • multiplyNaive(), :math:` r_{h+k} mathrel{+}= p_h q_k ` for all h and k, :math:` Theta( n^2 ) `;

  • multiplyFour(), p = x^{n/2} p_S + p_D and q = x^{n/2} q_S + q_D, the four products :math:` p_S q_S , :math: p_S q_D , :math: p_D q_S , :math: p_D q_D ` recursively, :math:` T( n ) = 4 T( n / 2 ) + Theta( n ) = Theta( n^2 ) ` (the Prodotto4() of section 2.6);

  • multiplyKaratsuba(), with the three products :math:` r_S = p_S q_S , :math: r_D = p_D q_D ` and :math:` r_M = ( p_S + p_D ) ( q_S + q_D ) `, :math:`[ r = x^n r_S + x^{n/2} ( r_M - r_S - r_D ) + r_D ,

` :math:` T( n ) = 3 T( n / 2 ) + Theta( n ) = Theta( n^{log_2 3} ) =

O( n^{1.59} ) `.

The recursive ones split at h = :math:` lfloor n / 2 rfloor `, so that n need not be a power of two, and count in *mults, if given, the products of two coefficients.

The contracts [see File Contract.h]: the recursion needs two polynomials of the same degree, and the products of the four and of the three halves equal the product of multiplyNaive(), an audit. The functions are defined in Polynomial.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 12.3, https://algoritmicamente.it/materiali/libro/capitoli/cap12.pdf

  1. Karatsuba, Yu. Ofman, Multiplication of multidigit numbers on automata, Soviet Physics Doklady 7, 595-596, 1963

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions