Question

FFT ile 2 nin kuvvetleri nasıl hesaplanır ve FFT ile büyük sayılar nasıl çarpılır ?

Comments

FFT denilen şey nedir?

---

Fast Fourier Transform, yani hızlı fourier dönüşümü

Answer 1

Normalde $N$ haneli iki sayının çarpımı için $N^2$ kere toplama ve $N^2-1$ kere çarpma işlemi yapmak gerekir (yeni işlemcilerde toplama işlemleri de önemlidir), örn. $15\cdot 76$ işlemini  $15\cdot 76=6\cdot 5+6\cdot 10+70\cdot 5+70\cdot 10=1140$  olarak hesaplıyoruz. Landau işaretiyle $O(f):=\{g:\mathbb{N}\rightarrow\mathbb{R^+}\vert\ \exists c \text{ öyle ki } \forall n\in \mathbb{N}:g(n)\leq cf(n) \}$ gösterirsek bu algoritma kayan nokta işlemlerinin (ing. FLOP) sayısında $O(N\mapsto 2N^2-1)=O(N\mapsto N^2)\equiv O(N^2)$ derecesindendir.

Tanım: Bir f fonksiyonu için $f_n:=f(x_n)$'lerin
 $\mathcal{F}^a:\mathbb{C}^N\rightarrow\mathbb{C}^N, f_j\mapsto \hat{f}_j:=\displaystyle\sum_{k=0}^{N-1}f_k e^{-2\pi i j k/N}$,  $j=0,...,N-1$ eşdönüşümüne ayrık Fourier dönüşümü denir. Tersi ($\mathcal{F}^a)^{-1}$ $f_j:=\frac{1}{N}\displaystyle\sum_{k=0}^{N-1}\hat{f}_k e^{2\pi i j k/N}$'dir.

Hızlı Fourier dönüşümü, $O(N^2)$ derecesinden olan ayrık Fourier dönüşümünü adı üstünde hızlı bir biçimde -$O(Nlog_2 N)$ ile- gerçekleştiren   bir tekniktir, grup teorisinden sayı teorisine uzanan farklı çeşitleri vardır, ilk kez verimli bir böl-ve-yönet algoritması biçiminde Cooley, J. W., and J. W. Tukey; An Algorithm for the Machine Calculation of Complex Fourier Series. Math. Comp. 19, 297-301 (1965) doi:10.2307/2003354 'de yayınlanmıştır. Cooley-Tukey algoritmasının kanıtı (yazılacak gibi değil) ve genel olarak hızlı Fourier dönüşümüyle ilgili herşey için E.O. Brigham, The Fast Fourier Transform, Prentice Hall, Englewood Cliffs (1974) kitabını incelemenizi öneririm.

1971'de A. Schönhage ve V. Strassen Schnelle Multiplikation grosser Zahlen, Computing 7, 281-292 doi:10.1007/BF02242355 adlı makalelerinde sadece herhangi iki büyük sayının çarpımını hesaplamaya yönelik  hızlı Fourier dönüşümüne dayalı $O(N log(N) log(log(N)))$ derecesinden  olan Schönhage-Strassen algoritmasını geliştirmişlerdir. Ancak 2007 yılından sonra Schönhage-Strassen'den daha hızlı, işlem karmaşıklığını $O(N log(N) 2^{3log_*(N)})$'e kadar düşürülebilen ($log_*$ burada yinelemeli logaritmadır) Fürer algoritması  bkz. arXiv:1407.3360 bulunabilinmiştir.

Ama ben ikinin bir kuvveti olan bir sayıyı (=$2^m$=$2N$ olsun) hesaplamak için Cooley-Tukey'in h.F.d. algoritmasının  nasıl kullanılabileceğini göstermekle yetineceğim.

Tanım: $p:\mathbb{C}\rightarrow\mathbb{C},x\mapsto p(x):=\displaystyle \sum_{k=0}^{N}a_k x^k$,
 $N$ derecesinden karmaşık değerli bir çokterimlidir, $x$ değişkenine taban denir.

Herhangi bir tamsayıyı $m$ belli bir positif taban sayısı için bir çokterimli olarak yazabiliriz, örn. $T:=10, m=134 \rightarrow m=p(T), a_0=4, a_1=3, a_2=1, a_k=0\ \ \forall k\geq3$. O zaman $N$ haneli iki sayıyı çarpma işlemi $N-1$ derecesinden iki çokterimliyi çarpma işlemine $r(x)=p(x)q(x)$ denk gelir (şimdilik tabanı sabit seçmiyoruz).  $p(x)q(x)$'nın katsayılarını doğrudan hesaplamak yerine belli $x_k$ noktalarında $r(x_k)=p(x_k)q(x_k)$'yi belirleyelim ve bunların yardımıyla $c=[c_0,...,c_{2N-1}]$'yi bulup $r(x)=\displaystyle \sum_{k=0}^{2N-1}c_k x^k$'yi oluşturalım. İçdeğer biçim teoremine göre $2N-1$ derecesinden $r(x)$ çokterimlisini saptayabilmek için $2N$ tane $r(x_k)$ fonksiyon değerine ihtiyacımız var. Akla ilk gelen soru hangi $x_k$ değerlerini seçmemiz gerektiği, yanıtı ise (sonradan kullanacağımız) indirgeme ve yansıma özelliğine sahip olan ilkel birim kökleridir.

Tanım: $R$ etkisiz elemanı 1 olan  değişmeli bir halka ve $0\leq n\in\mathbb{N}$ olsun. Eğer $\omega^n=1$ ve $0<k<n$ için $\omega^k\neq 1$'i sağlarsa, $\omega\in R$'ya $n$'inci ilkel birim kökü denir. İndirgeme özelliği : Eğer bir $2n-1$ derecesinden çokterimli için $2n$ ilkel birim kökünü belirlemişsek, bunların yarısı $n-1$ derecesinden bir çokterimli için de ilkel birim kökleridir. Yansıma özelliği ise şöyle açıklanabilir: Eğer $\omega$ $n$'inci ilkel birim kökü ve $n\geq 2$ çift ise, $\omega^{k+\frac{n}{2}}=-\omega^k$'dır.

Bizim için $R=\mathbb{C}$'dir. O zaman  $\omega:=e^{-\frac{2\pi i}{n}}$ bir $n$'inci ilkel birim köküdür.

Bu durumda $r(x_k)$ değerlerini  bulmak ayrık Fourier dönüşümü uygulamakla eşdeğerdir!

İlkönce tek çokterimlinin hızlı Fourier dönüşümüyle ilgileneceğiz. $2N$ çift olduğu için, $2N-1$ derecesinden bir $q(x):=\displaystyle \sum_{k=0}^{N-1}b_k x^k$ çokterimlisini iki tane $({N}-1)$ derecesi çokterimlisine dönüştürebiliriz:

$q_{çift}(x):=b_0+b_2 x+b_4 x^2+...+b_{2N-2}x^{N -1}$

$q_{tek}(x):=b_1+b_3 x+b_5 x^2+...+b_{2N-1}x^{N -1}$

, çünkü $q(x)=xq_{tek}(x^2)+q_{çift}(x^2)$.

 Cooley-Tukey algoritmasını -betik olarak gösterimi CT(çokterimli,sayı)- şimdi yazabiliriz:

1. $b=[b_0,...,b_{2N-1}]$ ve $\omega$'yı parametre olarak ver.
 
2. $b$'yi $b_{çift}\leftrightarrow q_{çift}$ ve $b_{tek}\leftrightarrow q_{tek}$'e böl. Özyineli olmak üzere C.-T. prosedürünü  her biri için $\omega^2$ ile çağır:$y_{çift/tek}=CT(b_{çift/tek},\omega^2)$ (indirgeme öz.) $\rightarrow$ $q_{çift}$ ve $q_{tek}$'in, $\omega^2$'nin bütün $N$ üsleri için değerleri $\rightarrow$ $q$'nun $\omega$'nın bütün $2N$ üsleri kümesindeki elemanların yarısı için değerleri biliyoruz.
 
3. Diğer yarısı için aşağıdaki denklemleri, 2.'de bulunan $y_{çift}$ ve $y_{tek}$'ler için ($N$ kere)  çöz:
 
 $q(\omega^k)=q_{çift}(\omega^{2k})+\omega^kq_{tek}(\omega^{2k})$
 
 $q(\omega^{k+N/2})=q_{çift}(\omega^{2k})-\omega^kq_{tek}(\omega^{2k})$ (yansıma öz.)
 
4. $2N=2^m$ olduğu için sonunda çokterimliden geriye sadece bir katsayı kalacak (en son yinelemede), bunu işlem yapmadan $y$'ye eşleyip geri döndürebiliriz.
 
5. $y=(q(\omega^k))_{k\in\{0,...,2N-1\}}$ a.F.d. değerlerini yazdır.
 
Son olarak $a$,$b$ katsayı vektörlü iki N-1 derecesinden çokterimliyi $p$,$q$ çarpma işlemine geliyoruz. Bunun için $y=CT(a)$ ve $z=CT(b)$'yi hesaplayalım, $y$ ve $z$'yi çarpalım, $h:=[y_0 z_0,...,y_{2N-1}z_{2N-1}]$. $h$'nin ters a.F.d.'ü , benzer şekilde $c_k=\displaystyle \frac{1}{2N}\sum_{j=0}^{2N-1}h_j \omega^{-ij}$, bize $r(x)$'in katsayılarını verir.