Prodotto di polinomi

Consideriamo qui il problema di moltiplicare due polinomi di grado n a coefficienti reali con un algorit-mo che utilizzi un basso numero di somme e prodotti.

Dati due polinomi di grado n, p(z) =Pn

k=0p_k· zke q(z) =Pn k=0q_k· zk, il loro prodotto p(z) · q(z) `e il polinomio, di grado 2n, s(z) =P2n k=0s_k· zkdove: s_k =              k X j=0 p_j· q_k−j se 0 ≤ k ≤ n n X j=k−n pj· q_k−j se n < k ≤ 2n

Il calcolo diretto di sk richiede k + 1 prodotti e k somme (se k ≤ n) o 2n − k + 1 prodotti e 2n − k somme (se k > n). Il numero totale di prodotti e di somme `e allora ≈ 2n<sup>2</sup>. Tale numero pu`o essere ridotto a O(n lg n) osservando che la convoluzione circolare dei vettori a 2n + 1 compo-nenti (p0, p1, . . . , pn, 0, 0, . . . , 0) e (q0, q1, . . . , qn, 0, 0, . . . , 0) `e esattamente il vettore (s0, s1, . . . , s2n). Ci`o unitamente alle propriet`a della trasformata discreta di Fourier, prova la correttezza del seguente algoritmo:

ALGORITMO: Moltiplicazione Veloce

Ingresso: due polinomi rappresentati dai vettori dei coefficienti (p0, p1, . . . , pn), (qo, q1, . . . , qn) 1. Calcola l’intero N = 2^ktale che 2n + 1 ≤ N < 2(2n + 1).

2. a:= vettore a N componenti (p₀, . . . , p_n, 0, . . . , 0). 3. b:= vettore a N componenti (q₀, . . . , q_n, 0, . . . , 0). 4. c := F⁻¹(F (a) · F (b)).

Uscita : il polinomio di grado al pi`u 2n i cui coefficienti sono c0, . . . , c_2n.

Per quanto riguarda l’analisi di complessit`a, da Fatto 10.1 segue immediatamente che l’algoritmo precedente richiede O(n lg n) somme e prodotti per potenza di ω = e^2πiN e solo O(n) operazioni di prodotto.

Per quanto riguarda l’implementazione su RAM, l’analisi precedente non `e realistica, basandosi sulla facolt`a di rappresentare arbitrari numeri complessi ed eseguire somme e prodotti in tempo costante. In realt`a, se rappresentiamo i numeri con errore di arrotondamento, sia l’errore sul risultato sia il tempo di calcolo viene a dipendere dall’errore di arrotondamento fissato.

Vogliamo qui studiare algoritmi efficienti per il calcolo esatto del prodotto di due polinomi a coeffi-cienti interi, rispetto ad un modello di calcolo in cui:

1. Gli interi sono rappresentati in notazione binaria.

2. La somma di due interi in n bit richiede n operazioni elementari. 3. Il prodotto di due interi di n bit richiede M (n) operazioni elementari.

Ad esempio, utilizzando l’algoritmo di moltiplicazione che si impara alle elementari, ab-biamo M (n) = n² mentre, utilizzando l’algoritmo di Sch¨onhage-Strassen, otteniamo M (n) = O(n lg n lg lg n).

Il problema pu`o essere cos`ı formulato: Problema: Prodotto Esatto.

Istanza: due polinomi rappresentati da due vettori (p0, . . . , pn) e (q0, . . . , qn) di interi di al pi`u n bit l’uno.

Richiesta: calcolare s_k =

k

X

j=0

pjq_k−jcon 0 ≤ k ≤ 2n, assumendo pj = qj = 0 per ogni j tale che j < 0 oppure j > n.

Osserviamo innanzitutto che se a < m, allora hai_m = a.

Poich´e ora i numeri pi, qisono al pi`u di n bit, ne segue che pi, qi< 2ⁿe quindi per ogni k (0 ≤ k ≤ 2n) vale s_k =

k

X

j=0

q_jp_k−j < n2²ⁿ < 2^2.5n+ 1 (a meno che n < 4 ). Posto allora m ≥ 22.5n+ 1, ne segue: hski_m= s_k (0 ≤ k ≤ 2n).

Per ottenere il corretto prodotto, basta allora considerare i coefficienti pk, qicome elementi dell’anel-lo Z_mcon le operazioni di somma e prodotto modulo m. Detta F_mla trasformata di Fourier su Z_m con radice 4 (vedi Esempio 10.2) si ha il seguente:

ALGORITMO: Prodotto Esatto Veloce.

Ingresso: due polinomi rappresentati da due vettori (p0, . . . , pn) e (q₀, . . . , q_n) di interi di al pi`u n bit l’uno.

m := 2N + 1 dove N = 2^kcon 2.5n ≤ N ≤ 5n a:=(p0, . . . , pn, 0, . . . , 0) vettore a N componenti in Zm. b:=(q0, . . . , qn, 0, . . . , 0) vettore a N componenti in Zm. c := F_m⁻¹(F_m(a) · F_m(b)).

Uscita: sk = ck (0 ≤ k ≤ 2n)

Per quando riguarda la complessit`a dell’algoritmo precedente, osserviamo che esso richiede O(N lg N ) operazioni di somma e moltiplicazioni per potenze di 4 nonch´e N moltiplicazioni di interi di al pi`u N bit.

Ricordando che ogni somma costa al pi`u N operazioni elementari, ogni prodotto per potenze di 4 `e uno shift e quindi costa al pi`u N operazioni elementari, ogni prodotto costa al pi`u M (N ) operazioni elementari, concludiamo che il tempo di T (n) complessivo `e :

dove abbiamo tenuto conto che N < 5n. Implementando il prodotto col metodo di Sch¨onhage-Strassen, si pu`o concludere :

T (n) = O^n²lg n lg lg n^

10.6.4 Prodotto di interi

Obiettivo di questo paragrafo `e il progetto di un algoritmo asintoticamente veloce per il prodotto di interi di n bit.

L’algoritmo di moltiplicazione imparato alle scuole elementari richiede tempo O(n²); abbiamo visto che una semplice applicazione della tecnica “Divide et impera” permette di realizzare un algoritmo pi`u veloce (Tempo= O(n^log23)).

Presentiamo qui un’ applicazione delle tecniche FFT, disegnando un algoritmo quasi lineare (Tem-po= O(n lg⁵n)). Tale algoritmo `e una semplificazione didattica di quello proposto da Sch¨onhage-Strassen, che `e tuttora l’algoritmo di moltiplicazione asintoticamente pi`u efficiente noto (Tempo= O(n lg n lg lg n)).

Parametri della procedura sono gli interi a = xn−1. . . x0 e b = yn−1. . . y0 rappresentati nella notazione binaria. Essi vengono decomposti in M = ^√n blocchi aM, . . . , a0 e bM, . . . , b0 ognuno composto da M bit: in tal modo a e b individuano rispettivamente i polinomi A(z) =

M X k=0 a_k· z^k e B(z) = M X k=0 b_k· zk. Si noti che a = M X k=0 a_k· 2M ·k= A(2^M) e b =PM k=0b_k· 2M ·k= B(2^M) .

Tali polinomi vengono moltiplicati con la tecnica veloce presentata precedentemente, in cui i prodotti vengono eseguiti richiamando ricorsivamente la procedura. Ottenuto il polinomio A(z)·B(z) = C(z) = PM

k=0c_kz^k, si calcola C(2^M) =PM

k=0c_k· 2M ·k. Risulta infatti che C(2^M) = A(2^M) · B(2^M) = a · b. Esiste una costante C > 0 per cui la seguente procedura calcola il prodotto di 2 interi:

ProceduraPROD VEL(a = xn−1. . . x₀; b = y_n−1. . . y₀)

ifn < C thencalcola a · b col metodo elementare,return (a · b)

else begin

• M =^√n

• decomponi a in M blocchi aM −1, . . . , a0di lunghezza M . • decomponi b in M blocchi b_{M −1}, . . . , b₀di lunghezza M . • Calcola l’intero N = 2ktale che 2.5 · M ≤ N < 5 · M . • siano a, b i vettori a N componenti

a = (a₀, . . . , a_{M −1}, 0, . . . , 0) b = (b₀, . . . , b_{M −1}, 0, . . . , 0) • (c₀, . . . , cN −1) = F₂N+1(a) (d0, . . . , d_{N −1}) = F₂N+1(b) •for k = 0toN − 1do αk= PROD VEL(ck; dk) • (z₀, . . . , z_{N −1}) := F₂⁻¹N+1(α₀, . . . , α_{N −1}) •return N −1 X k=0 zk· 2^{M ·k} ! end

Una semplice analisi permette di verificare che, detto T (n) il tempo di calcolo della procedura di cui sopra:

T (n) ≤ N T (N ) + O(n lg²n). Ricordando che N ≤ 5^√n, vale:

T (n) ≤ 5^√nT (5^√n) + O(n lg²n). Posto g(n) = n lg⁵n, si verifica che per n sufficientemente grande:

5^√n g(5^√n) + O^n lg²n^= 25n  lg 5 + ^{lg n} 2 5 + O^n lg²n^≤ g(n). Applicando ora il corollario 6.2 otteniamo:

T (n) = O(n lg⁵n).

Esercizi

1) Consideriamo il problema di calcolare il prodotto di n interi a1, a2, . . . , antali che ai∈ {1, 2, . . . , n}

per ogni i = 1, 2, . . . , n. Mantenedo gli n valori di input in un vettore A = (A[1], A[2], . . . , A[n]) di variabili globali, possiamo risolvere il problema chiamando la procedura Prodotto(1, n) definita nel modo seguente per ogni coppia di interi i, j, 1 ≤ i ≤ j ≤ n:

Procedure Prodotto(i, j) if i = j then return A[i]

else begin k := b^i+j₂ c a :=Prodotto(i, k) b :=Prodotto(k + 1, j) return c = a · b end

a) Assumendo il criterio di costo uniforme, determinare l’ordine di grandezza del tempo di calcolo richiesto dalla procedura su un input di dimensione n nel caso peggiore.

b) Svolgere l’esercizio richiesto al punto a) assumendo il criterio di costo logaritmico. 2) Consideriamo il problema di calcolare l’espressione

b = a1+ 2a2+ 2²a3+ · · · + 2ⁿ⁻¹an

su input a1, a2, . . . , antali che ai∈ {1, 2, . . . , n} per ogni i = 1, 2, . . . , n.

Tale calcolo pu`o essere eseguito dalla seguente procedura:

begin

b := a1

for j = 2, 3, . . . , n do

b := b + 2^j−1aj

end

a) Assumendo il criterio di costo logaritmico, determinare in funzione di n l’ordine di grandezza del tempo di calcolo e dello spazio di memoria richiesti dalla procedura nel caso peggiore.

b) Descrivere un algoritmo del tipo “divide et impera” che risolva in problema in tempo O(n) assumendo il criterio di costo uniforme.

c) Assumendo il criterio di costo logaritmico, determinare in funzione di n l’ordine di grandezza del tempo di calcolo e dello spazio di memoria richiesti nel caso peggiore dall’algoritmo descritto al punto b).

3) Considera la seguente procedura ricorsiva che su input n ∈ IN, n > 0, restituisce il valore F (n): Function F (n) begin if n = 1 then return 1 else begin i := bⁿ₂c j := dn 2e a := F (i) + i · F (j) return a end end

a) Assumendo il criterio di costo uniforme, determinare al crescere di n l’ordine di grandezza del tempo di calcolo e dello spazio di memoria richiesti dalla procedura su input n.

b) Assumendo il criterio di costo logaritmico, determinare al crescere di n l’ordine di grandezza del tempo di calcolo e dello spazio di memoria richiesti dalla procedura su input n.

Programmazione dinamica

Come abbiamo visto nel capitolo precedente, gli algoritmi basati sul metodo “divide et impera” suddi-vidono l’istanza di un problema in sottoistanze di ugual dimensione e quindi risolvono queste ultime in maniera indipendente, solitamente mediante chiamate ricorsive. Vi sono per`o problemi che possono essere decomposti in sottoproblemi definiti su istanze di dimensione diversa e in questo caso il metodo “divide et impera” non pu`o essere applicato (per lo meno secondo la formulazione che abbiamo descritto nel capitolo precedente). Inoltre, in molti casi interessanti, tali sottoproblemi presentano forti dipen-denze tra loro: cos`ı un’eventuale procedura ricorsiva che richiama semplicemente se stessa su tutte le sottoistanze per le quali `e richiesta la soluzione porta ad eseguire pi`u volte gli stessi calcoli. In alcuni casi il tempo dedicato alla ripetizione di computazioni gi`a eseguite `e cos`ı elevato da rendere l’algoritmo assolutamente inefficiente.

Un metodo solitamente applicato per risolvere problemi di questo tipo `e quello della “program-mazione dinamica”. Intuitivamente esso consiste nel determinare per una data istanza i di un problema l’insieme S(i) di tutte le sottoistanze da cui dipende il calcolo della soluzione per i. Con lo stesso criterio si stabilisce poi una relazione dipendenza tra i vari elementi di S(i). Quindi, rispettando tale dipendenza, si ricavano le soluzioni delle sottoistanze di S(i) a partire da quelle di dimensione minore; i risultati parziali man mano ottenuti vengono conservati in opportune aree di memoria e utilizzati per determinare le soluzioni relative a istanze di dimensione via via crescente. Cos`ı , ogni sottoistanza del problema viene risolta una volta sola e il risultato utilizzato tutte le volte che occorre senza dover ripetere il calcolo. In questo modo, ad un modesto aumento dello spazio richiesto per l’esecuzione dell’algoritmo, corrisponde spesso una drastica riduzione dei tempi di calcolo.

11.1 Un esempio semplice

Un esempio di algoritmo che calcola ripetutamente le soluzioni parziali del problema dato `e fornito dalla procedura per determinare i numeri di Fibonacci descritta nella sezione 5.1. Su input n ∈ IN tale procedura calcola l’n-esimo numero di Fibonacci fnmediante il seguente programma ricorsivo:

Procedura FIB(n) ifn ≤ 1then returnn else begin a := n − 1 x :=FIB(a) b := n − 2 y :=FIB(b) return(x + y) end `

E chiaro che in questa procedura i vari termini della sequenza f₀, f₁, . . . , f_n−2 sono calcolati varie volte. Per esempio fn−2 viene calcolato sia per determinare fn = f_n−1+ f_n−2, sia per determinare fn−1= fn−2+ fn−3. Il fenomeno poi cresce man mano che decrescono gli indici della sequenza fino al punto che i primi termini vengono calcolati un numero esponenziale di volte, rendendo cos`ı l’algoritmo inutilizzabile anche per piccole dimensioni dell’ingresso. Abbiamo infatti gi`a osservato (sezione 7.2) che questa procedura richiede un tempo di calcolo Ω((

√ 5+1

2 )ⁿ).

Il modo pi`u semplice per risolvere il problema `e proprio basato sulla programmazione dinamica. I numeri di Fibonacci vengono calcolati a partire da quelli di indice minore e quindi memorizzati in un vettore apposito

V = (V [1], V [2], . . . , V [n]);

in questo modo essi sono calcolati una volta sola e quindi riutilizzati quando occorre:

Procedura DFIB(n) begin V [0] := 0 V [1] := 1 a := 0 b := 1 k := 2 whilek ≤ ndo begin x := V [a] y := V [b] V [k] := x + y a := b b := k k := k + 1 end returnV [n] end

Come si osserva immediatamente, il tempo di calcolo della proceduraDFIB `e Θ(n). DFIBcalcola la stessa funzione diFIBin modo straordinariamente pi`u efficiente. Con poca fatica, inoltre, possiamo ottimizzare l’algoritmo osservando che non `e necessario mantenere in memoria un vettore di n elementi; infatti, per calcolare ogni f<sub>i</sub> `e sufficiente ricordare i due coefficienti precedenti, cio`e f<sub>i−1</sub> e f<sub>i−2</sub>. Si ottiene cos`ı la seguente procedura:

Procedura OttFIB(n) ifn ≤ 1then returnn else begin x := 0 y := 1 fork = 2, ndo t := y y := x + y x := t return(y) end

Anche in questo caso abbiamo un tempo di calcolo Θ(n), mentre lo spazio di memoria richiesto si riduce a O(1).