Radici complesse dell'unità - Lemma del dimezzamento

[markzzz]

Durante lo studio di questo teorema, mi sono inbattuto in questa "mistica" frase che non riesco a decifrare :

Notate che, elevando al quadrato tutte le radici n-esime complesse dell'unità, ciascuna radice (n/2)-esima dell'unità è ottenuta due volte

Potete farmi un esempio? Cosa intende?

Grazie

[markzzz]

Effettivamente, non capendo quel teorema (alla base della FFT) non capisco appunto il perchè, valutare un polinomio nelle n-radici n-esime dell'unità dovrebbe "costarmi" di meno.

Se valuto con una DFT un polinomio impiego $O(n^2)$, con la FFT $O(nlogn)$.
Perchè succede questo? Dovrò comunque calcolarmi i valori n volte sugli n coefficenti (ergo, $n^2$).

Delucidazioni? Magari anche un semplice esempio

[orazioster]

E'semplicemente perchè ogni
numero ha due radici quadrate.
E così ogni radice $2^(n-1)$-esima(di qualsiasi numero, per
cui anche di 1)*
ha come sue radici quadrate due radici $2^n$-esime .

FFT è "Fast Fourier Trasform"? Nulla ne so.

*e lo zero


[@edit: -ho corretto il post...
sapete, mi "Correggo" pure gli appunti ed i 'foglietti volanti'!]

[markzzz]

"orazioster":E'semplicemente perchè ogni
numero ha due radici quadrate.
E così ogni radice $(n-1)$-esima(di qualsiasi numero, per
cui anche di 1)*
ha come sue radici quadrate due radici $n$-esime .

Uhm, no non mi è molto chiaro quello che stai dicendo! Se io ho $w_n^k$ allora per il teorema del dimezzamento ho $w_(n/2)^k$ (e fin quì rispondo a Notate che, elevando al quadrato tutte le radici n-esime complesse dell'unità).
Ma poi che significa ciascuna radice (n/2)-esima dell'unità è ottenuta due volte ? Ottengo $w_(n/2)^k$, punto! Perchè due volte?

"orazioster":
FFT è "Fast Fourier Trasform"? Nulla ne so.

*e lo zero

Si è la fast fourier transform

[hamming_burst]

Per la teoria non so risponederti, ma per quanto riguarda l'algoritmo, da quello che ricordo, il trucco alla base della complessità ridotta è usare il "lemma della cancellazione" e ricodarsi che l'algoritmo divide i coefficienti in due polinomi (con la regola di Horner) con indice pari e dispari. Questi due polinomi poi sono "convoluti" con i numeri complessi. Forse ho dimenticato un passaggio, ma ricordo bene che la base è quella divisone.

Mi hai fatto comunque ricordare che devi rivedermi questo algoritmo

[dissonance]

"markzzz":Ottengo $w_(n/2)^k$, punto! Perchè due volte?

Perché ti è sufficiente fare viaggiare il parametro $k$ da $1$ ad $n/2$ per ottenerle tutte. Se lo fai viaggiare fino ad $n$ le ottieni tutte, appunto, due volte.

[orazioster]

Ogni $w_(n-2)^k$ ha DUE radici quadrate sue $w_n^k$.
Perciò quando elevi al quadratoi $w_n^k$ (dimezzi la radice) ottieni
ogni $w_(n/2)K$ due volte.

[orazioster]

Ogni $w_(n/2)^k$ ha DUE radici quadrate sue: $w_n^k$ e $w_n^(k+n/2).
Perciò quando elevi queste al quadrato (dimezzi la radice) ottieni
$w_(n/2)^k$ due volte.

[nota: ho sbagliato nel mio precedente post
a scrivere :"radice $(n-1)esima" e "radice $n$-esima":
il mio pensiero era qualcosa "radice quadrata $(n-1)$-esima [etc.]", cioè
$2^(n-1)$,$2^n$...]

[markzzz]

Credo di aver capito! Thanks