Esercizio - convoluzione con il vettore delle potenze di due in tempo lineare (compito del 5 settembre 2025, es. 2)

Teoria usata: Polinomi - rappresentazione per coefficienti e per valori e convoluzioneun polinomio di grado limitato da n si rappresenta con n coefficienti o con n valori su n punti distinti (teorema di interpolazione, matrice di Vandermonde). Per coefficienti la somma costa n e il prodotto, la convoluzione lineare, n^2 prodotti e (n-1)^2 somme; per valori il prodotto costa 2n-1 prodotti ma serve una base estesa di almeno 2n-1 punti. Le conversioni generali costano troppo: valutazione n volte con Horner 2n(n-1), interpolazione con Gauss-Jordan n^3 o con Lagrange n^2. Serve una base speciale: la DFT.Polinomi - rappresentazione per coefficienti e per valori e convoluzione → (definizione di convoluzione lineare, regola di Horner), Dimostrazioni, induzione e invariantiTecniche di dimostrazione (esempio, controesempio, assurdo), induzione con casi base multipli, invarianti di ciclo (inizializzazione, conservazione, uso alla fine), schema generale per provare la correttezza; esempi svolti su arrayMax, sequenza di bit e numeri di Fibonacci.Dimostrazioni, induzione e invarianti → (invarianti dei cicli), Esponenziazione veloce per quadrature successivepotenza x^n con un operatore associativo con elemento neutro, costo = numero di applicazioni dell'operatore; STUPID_POWER costa n-1, la sottostruttura x^n = (x^floor(n/2))^2 (per n dispari per x) dà POWER con T(n) = floor(log2 n) + (numero di bit a 1 di n) - 1, Theta(log n) (caso peggiore 2 floor(log2 n), n = 2^t - 1); versioni iterative POWER2 e POWER3 dalla rappresentazione binaria di n; esempio con la matrice di Fibonacci; il modello a costo unitario vale solo se l'operatore non fa crescere gli operandi.Esponenziazione veloce per quadrature successive → (potenza di $2$ in tempo logaritmico).

La convoluzione per definizione costa $\Theta(n^2)$ operazioni (nota sui polinomi) e la FFT darebbe $\Theta(n\log n)$ (Fast Fourier Transform - algoritmo ricorsivo e trasformata inversala FFT calcola DFT_n (n potenza di due) con divide et impera: si separano i coefficienti di indice pari e dispari, p(x) = p0(x^2) + x p1(x^2), e per il lemma di dimezzamento bastano due DFT di ordine n/2; y_i = y0_i + w^i y1_i e y_{i+n/2} = y0_i - w^i y1_i. La ricorrenza T(n) = 2T(n/2) + 2n con T(1) = 0 ha soluzione esatta 2 n log2 n. L'inversa ha matrice F^{-1}_{ij} = w^{-ij}/n: si ottiene con la FFT sulle potenze negative (poi si divide per n fuori dalla ricorsione) oppure con DFT_n(y) rovesciato. LIN_CONV moltiplica due polinomi con n coefficienti in 12 n log2(2n) + 4n operazioni.Fast Fourier Transform - algoritmo ricorsivo e trasformata inversa →). Qui il secondo vettore ha una struttura (progressione geometrica di ragione $2$) che permette di scendere a $\Theta(n)$ con due semplici ricorrenze, senza trasformate.

(a) Il caso $n=4$

La componente $c_j$ somma i prodotti $x_k\cdot2^{h}$ con $k+h=j$, $0\le k,h\le3$ (convoluzione lineare, vedi la definizione nella nota sui polinomi). Per $j=0,\dots,3$ si possono usare tutti gli indici $k=0,\dots,j$: $$\begin{aligned}c_0&=x_0\cdot2^0=x_0,\\c_1&=x_0\cdot2^1+x_1\cdot2^0=2x_0+x_1,\\c_2&=x_0\cdot2^2+x_1\cdot2^1+x_2\cdot2^0=4x_0+2x_1+x_2,\\c_3&=x_0\cdot2^3+x_1\cdot2^2+x_2\cdot2^1+x_3\cdot2^0=8x_0+4x_1+2x_2+x_3.\end{aligned}$$ Per $j=4,5,6$ l'esponente $h=j-k$ non può superare $3$, quindi $k\ge j-3$: si parte da $k=j-3$ e si arriva a $k=3$: $$\begin{aligned}c_4&=x_1\cdot2^3+x_2\cdot2^2+x_3\cdot2^1=8x_1+4x_2+2x_3,\\c_5&=x_2\cdot2^3+x_3\cdot2^2=8x_2+4x_3,\\c_6&=x_3\cdot2^3=8x_3.\end{aligned}$$ Controllo con $\mathbf x=(1,0,0,0)$: $\mathbf c=(1,2,4,8,0,0,0)=\mathbf p_4$ completato con zeri, come deve essere perché $\mathbf x$ è l'elemento neutro della convoluzione.

(b) Le due sommatorie

La definizione di convoluzione lineare per vettori di lunghezza $n$ è $$c_i=\sum_{j=\max\{0,\,i-n+1\}}^{\min\{i,\,n-1\}}x_j\,p_{i-j},\qquad p_m=2^m,$$ cioè $c_i=\sum_{j=\max\{0,i-n+1\}}^{\min\{i,n-1\}}x_j\,2^{\,i-j}$, per $0\le i\le2n-2$. Si distinguono due casi:

• se $0\le i\le n-1$ allora $i-n+1\le0$ e $i\le n-1$, quindi $\max\{0,i-n+1\}=0$ e $\min\{i,n-1\}=i$;
• se $n\le i\le2n-2$ allora $i-n+1\ge1$ e $i\ge n-1$, quindi $\max\{0,i-n+1\}=i-n+1$ e $\min\{i,n-1\}=n-1$.

Perciò $$c_i=\begin{cases}\displaystyle\sum_{j=0}^{i}x_j\,2^{\,i-j}&0\le i\le n-1,\\[3mm]\displaystyle\sum_{j=i-n+1}^{n-1}x_j\,2^{\,i-j}&n\le i\le2n-2.\end{cases}$$ Per $n=4$ danno esattamente le espressioni del punto (a) (per esempio $i=5$: $j$ da $2$ a $3$, $x_2\cdot2^3+x_3\cdot2^2$).

(c) Le due ricorrenze

Prima metà, $0\le i\le n-1$. Caso base: $c_0=x_0\cdot2^0=x_0$. Per $0<i\le n-1$ si separa l'ultimo addendo ($j=i$, con $2^0=1$) e si raccoglie $2$ dai restanti: $$\begin{aligned}c_i&=\sum_{j=0}^{i-1}x_j2^{\,i-j}+x_i=2\sum_{j=0}^{i-1}x_j2^{\,i-1-j}+x_i\\&=2\,c_{i-1}+x_i.\end{aligned}$$ (la somma che resta è proprio $c_{i-1}$ per la formula del punto (b), valida perché $i-1\le n-1$). Questa è una regola di Horner calcolata in $2$ ($c_i$ è il polinomio con coefficienti $x_0,\dots,x_i$ valutato in $z=2$, vedi Polinomi - rappresentazione per coefficienti e per valori e convoluzioneun polinomio di grado limitato da n si rappresenta con n coefficienti o con n valori su n punti distinti (teorema di interpolazione, matrice di Vandermonde). Per coefficienti la somma costa n e il prodotto, la convoluzione lineare, n^2 prodotti e (n-1)^2 somme; per valori il prodotto costa 2n-1 prodotti ma serve una base estesa di almeno 2n-1 punti. Le conversioni generali costano troppo: valutazione n volte con Horner 2n(n-1), interpolazione con Gauss-Jordan n^3 o con Lagrange n^2. Serve una base speciale: la DFT.Polinomi - rappresentazione per coefficienti e per valori e convoluzione →).

Seconda metà, $n\le i\le2n-2$. Caso base: $c_{2n-2}=x_{n-1}\cdot2^{(2n-2)-(n-1)}=x_{n-1}\,2^{n-1}$ (un solo addendo, $j=n-1$). Per $n\le i<2n-2$ si ha $i+1\le2n-2$, quindi per la formula del punto (b) $$c_{i+1}=\sum_{j=i-n+2}^{n-1}x_j\,2^{\,i+1-j},\qquad\text{cioè}\qquad\frac12c_{i+1}=\sum_{j=i-n+2}^{n-1}x_j\,2^{\,i-j}.$$ La somma di $c_i$ ha lo stesso intervallo con in più l'addendo $j=i-n+1$, che vale $x_{i-n+1}2^{\,i-(i-n+1)}=x_{i-n+1}\,2^{\,n-1}$: $$c_i=\frac12\,c_{i+1}+x_{i-n+1}\,2^{\,n-1}.$$ Controllo per $n=4$, $i=5$: $c_5=\frac12c_6+x_2\cdot2^3=4x_3+8x_2$, come in (a).

(d) L'algoritmo e il suo costo

La prima ricorrenza si percorre in avanti da $i=1$ a $n-1$; la seconda all'indietro da $2n-3$ a $n$. Serve $2^{n-1}$, che si ottiene man mano nel primo ciclo, dove pow2 assume il valore $2^i$.

POWER_CONV(x)
n <- x.len
if n = 1 then return (x[0])
c[0] <- x[0]
pow2 <- 1
for i <- 1 to n-1
    pow2 <- 2 * pow2                   { pow2 = 2^i }
    c[i] <- 2 * c[i-1] + x[i]
                                       { ora pow2 = 2^(n-1) }
c[2n-2] <- x[n-1] * pow2
for i <- 2n-3 downto n
    c[i] <- c[i+1] / 2 + x[i-n+1] * pow2
return c

Correttezza. Primo ciclo, invarianti: all'inizio dell'iterazione $i$ vale pow2 $=2^{i-1}$ e c[i-1] $=c_{i-1}$ (per $i=1$ perché c[0] $=x_0=c_0$ e pow2 $=1$). L'iterazione calcola pow2 $=2^i$ e $c_i=2c_{i-1}+x_i$, corretto per la prima ricorrenza. Alla fine pow2 $=2^{n-1}$ e le componenti $c_0,\dots,c_{n-1}$ sono corrette. Dopo il ciclo, c[2n-2] $=x_{n-1}2^{n-1}$ è il caso base della seconda ricorrenza. Secondo ciclo, invariante: all'inizio dell'iterazione $i$ la componente c[i+1] è corretta (vero per $i=2n-3$ dopo l'assegnamento del caso base); l'iterazione calcola $c_i=\frac12c_{i+1}+x_{i-n+1}2^{n-1}$, corretto per la seconda ricorrenza. Quindi alla fine tutte le $2n-1$ componenti sono corrette. Verificato con un'implementazione confrontata con numpy.convolve per $n=1,\dots,11$ con $\mathbf x$ complesso casuale.

Costo (operazioni tra complessi: somme, prodotti, divisioni; per $n\ge2$):

• primo ciclo, $n-1$ iterazioni, ciascuna con un prodotto per aggiornare pow2, un prodotto per $2c_{i-1}$ e una somma: $3(n-1)$;
• c[2n-2]: $1$ prodotto;
• secondo ciclo, $n-2$ iterazioni (da $2n-3$ a $n$), ciascuna con una divisione, un prodotto e una somma: $3(n-2)$.

Totale: $T(n)=3(n-1)+1+3(n-2)=6n-8=\Theta(n)$. Per $n=1$ nessuna operazione. Il conteggio è stato verificato contando le operazioni dell'implementazione per $n=2,\dots,11$ ($4,10,16,\dots,58$).

Miglioramento della costante. pow2 $=2^{n-1}$ serve solo dopo il primo ciclo, e si può ottenere per quadrature successive con $O(\log n)$ prodotti (Esponenziazione veloce per quadrature successivepotenza x^n con un operatore associativo con elemento neutro, costo = numero di applicazioni dell'operatore; STUPID_POWER costa n-1, la sottostruttura x^n = (x^floor(n/2))^2 (per n dispari per x) dà POWER con T(n) = floor(log2 n) + (numero di bit a 1 di n) - 1, Theta(log n) (caso peggiore 2 floor(log2 n), n = 2^t - 1); versioni iterative POWER2 e POWER3 dalla rappresentazione binaria di n; esempio con la matrice di Fibonacci; il modello a costo unitario vale solo se l'operatore non fa crescere gli operandi.Esponenziazione veloce per quadrature successive →). Allora il primo ciclo costa $2(n-1)$ ($2c_{i-1}$ e la somma) e il totale diventa $2(n-1)+1+3(n-2)+O(\log n)=5n+O(\log n)$, con coefficiente del termine dominante $5$ al posto di $6$. In entrambi i casi la complessità è lineare, contro il $\Theta(n^2)$ della convoluzione per definizione.