Autor Wątek: Algorytm Szybkiej Transformaty Fouriera  (Przeczytany 3948 razy)

Offline davidbnpl

  • Użytkownik

# Sierpień 13, 2011, 15:32:49
Witam. Nie wiem czy w dobrym dziale zamieściłem temat. Jeśli nie, to przepraszam.

Czy ma ktoś link do dobrego kompleksowego wyjaśnienia działania algorytmu z tematu?
Na wikipedii pl jest tylko wspomniane, że istnieje coś takiego. Na wiki eng jest coś więcej ale też niezbyt dużo.
Czy jest gdzieś możliwie jasno i przejrzyście wytłumaczone działanie tego algorytmu? Wraz z jakimiś przykładami najlepiej.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Tomcat

  • Użytkownik

# Sierpień 13, 2011, 16:10:58

Offline davidbnpl

  • Użytkownik

# Sierpień 13, 2011, 19:46:25
Troszkę nie doczytałem :( Chodzi mi o algorytm Schönhage-Strassen'a do szybkiego mnożenia, który opiera się o FFT :)

Chyba, że macie inne propozycje do szybkiego podniesienia dużej liczby do kwadratu? Wyczytałem na wikipedii
Cytuj
In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2^(2^15) to 2^(2^17) (10,000 to 40,000 decimal digits).
Czy to znaczy, że dla liczb większych niż 2^(2^17) lepiej opłaca się stosować algorytm Karatsuby?

Jakie optymalizacje można zastosować podnosząc liczbę do kwadratu? Na pewno mogę zmniejszyć ilość mnożeń przy a*b jeśli a==b.
Z wzoru skróconego mnożenia wychodzi zamiast 4 mnożeń tylko 3, oraz przesunięcie bitowe (mnożenie *2).

Z tego by wychodziło, że a^2 można rozbić na b^2+c^2+2bc, b^2 i c^2 dalej można rozbijać a do b*c zastosować algorytm Karatsuby. Po czym wynik przesunąć o bit w lewo.
Licząc jednak złożoność obliczeniową wychodzi mi dokładnie taka sama jak algorytmu Karatsuby, więc czy ja coś źle liczę, czy taka optymalizacja po prostu nie ma sensu?

Offline davidbnpl

  • Użytkownik

# Sierpień 17, 2011, 15:24:00
Ponawiam pytanie: gdzie mogę znaleźć opis algorytmu FFT, a jeszcze lepiej algorytmu Schönhage-Strassen'a. Chodzi o szybkie mnożenie dużych liczb. Chodzi mi o opis w miarę dokładny, bo te, które znajduję w internecie składają się zwykle z kilku akapitów w rodzaju:
"z wzoru <tutaj niezrozumiały, niewytłumaczony i zagmatwany wzór> wynika, że <tutaj kolejny wzór>, a z tego, że <i kolejny wzór>, więc widać, że FFT jest szybkie"
A ja chcę, żeby te wzory właśnie były wytłumaczone na jakimś konkretnym przykładzie, a nie na sucho tylko podane, że tak jest i już. Szczególnie, że z tych wzorów nie za dużo rozumiem, a linki tłumaczące dane zagadnienie wprowadzają znowu mnóstwo kolejnych niezrozumiałych wzorów itd... Czyli musiałbym się cofnąć i od podstaw zrozumieć wszystko o wielomianach. Trochę szkoda mi na to czasu, skoro ja chcę tylko poznać jeden konkretny algorytm.

PS. Tomcat - link, który podałeś jest nie wspomina ani słowem o transformacie Fouriera, traktuje ogólnie o programowaniu dynamicznym.

Offline vinc999

  • Użytkownik

# Sierpień 17, 2011, 15:34:27
Jezeli chcesz FFT - to wystarczy na wikipedii obczaic jak sie algorytm nazywa, co prowadzi do kolejnej strony:
http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
Algorytm FFT jest tez chyba w TAOCP Knutha.

Prawda jest taka, ze przez te rownania tak czy tak musisz przejsc. Szczegolnie jezeli Cie interesuje wyprowadzenie/podstawy. Sily nie ma, to jest matematyka. Jak masz gotowe rownanie to mozesz je zastosowac i nie pytac, lub pytac i duuzo czytac.

Gdzie mozna to znalezc - oczywiscie google, trza szukac do oporu. Wyzszy poziom to oczywiscie publikacje naukowe, ale tam bedzie wylacznie algorytm.

Pewnie Cie nie zadowala takie rozwiazanie, ale ja kiedys tez szukalem pewnego zagadnienia, nasciagalem sobie wiele publikacji (oczywiscie w prawie kazdej byl inny formalizm matematyczny), ale metoda prob i bledow, porownyania itp w koncu doszedlem do tego co chcialem.

Offline davidbnpl

  • Użytkownik

# Sierpień 17, 2011, 15:43:53
Chodzi mi o coś takiego, co przed chwilą znalazłem (właśnie czytam, więc nie wiem czy na 100% dobrze wyjaśni, ale zapowiada się obiecująco).
Wcześniej czytałem tutaj ale jest tam przykład przeprowadzenia SFT dla wielomianu, jednak nie ma przykładu mnożenia, tylko kilka wzorów w rodzaju "z tego wzoru wynika <inny wzór>".

Wikipedia to pierwsze źródło, gdzie szukałem. Ale chyba sam przyznasz, że łopatologicznie to tam wyjaśnione nie jest :) Nie chodzi o to, że nie chcę duuużo poczytać. Mogę i przeczytać 200 stron ale, żeby było jasno wyjaśnione, już się naczytałem sporo artykułów na ten temat i wszędzie miałem wrażenie, że artykuł jest przeznaczony dla osób, które wiedzą na ten temat tyle, że nie muszą artykułu czytać...

Wiem, że to prawie niemożliwe ale najbardziej interesują mnie źródła w języku ojczystym :) Nie to, żebym nie znał angielskiego, ale jednak z fachowym matematyczno/informatycznym słownictwem mam jeszcze pewne problemy. Wiem - pozostaje słownik, ale to spowalnia czytanie i rozumienie artykułu kilkukrotnie :(

Offline vinc999

  • Użytkownik

# Sierpień 17, 2011, 15:56:23
A po co dokladnie Ci FFT? Mozesz sobie zobaczyc np:
http://www.librow.com/articles/article-10
Jak widze, to powinno dac rade - tam jest pseudokod itp.

Jezeli chodzi o to mnozenie - jezeli nie ma to duzego zastosowania (tylko matematyczne) to wydaje mi sie, ze ciezko bedzie znalezc inne zrodlo niz literatura fachowa.

Coz - trzeba czytac po angielsku - zeby poznac slownictwo:) Czesto nawet slowniki tu zawodza:)

--edit
Jeszcze tylko dodam - ja niezbyt czesto uzywam slownik (na ogol mi sie nie chce...), a tak czy tak, zeby artykul zrozumiec to musze mu poswiecic conajmniej kilka godzin.

Offline davidbnpl

  • Użytkownik

# Sierpień 17, 2011, 18:02:42
Jest mi potrzebny do podniesienia dużych liczb do kwadratu. A konkretniej do sprawdzania pierwszości liczb Mersenne'a. Jest do tego np program z projektu GIMPS, ale on używa CPU. Natomiast tworząc program wykorzystujący GPU można uzyskać o wiele lepsze wyniki. Szczególnie mając do dyspozycji np coś takiego.

Poprawiłem się, nie chodzi mi konkretnie o FFT, ale algorytm szybkiego mnożenia wielomianów (najlepiej Shoenge-Strassena) opierający się na FFT. Więcej bym pewnie zrozumiał na konkretnym przykładzie mnożenia 2 wielomianów 4-stopnia niż z 10 długich artykułów. Samą ideę FFT mniej więcej rozumiem ale nadal nie widzę jej zastosowania przy mnożeniu wielomianów.

Projekty obliczeń rozproszonych typu GIMPS imo nie mają zastosowania dla olbrzymich liczb Mersenne'a, bo kolejne iteracje muszą być prowadzone kolejno po sobie, nie da się tego robić równolegle na kilku maszynach. Uzyskanie na jednym komputerze czasu iteracji mniejszego niż przesył danych do i z serwera sprawi, że wyniki uzyska się szybciej niż na nieskończonej ilości komputerów użytych do obliczeń rozproszonych.

Offline vinc999

  • Użytkownik

# Sierpień 17, 2011, 18:06:54
O samym FFT troche slyszalem, o tym o czym teraz piszesz nie mam juz najmniejszego pojecia, wiec nie moge Ci za bardzo pomoc.

A nie myslales kiedys o MatLabie? Nie mam 100% pewnosci, ale wydaje mi sie, ze mozna znalezc do niego odpowiedni toolbox zeby pracowac na GPU.

Offline davidbnpl

  • Użytkownik

# Sierpień 17, 2011, 18:54:22
W skrócie: zainteresowałem się liczbami pierwszymi Mersenne'a. Dołączenie do projektu GIMPS lub podobnych wydaje mi się bezcelowe, bo obecnie trwają poszukiwania liczby pierwszej mającej ponad (!) 100 milionów cyfr w zapisie dziesiętnym, czyli szukać trzeba w liczbach Mersenne'a począwszy od 2^(100kk/log(2))-1 (log przy podstawie 10), czyli w przybliżeniu 2^(332kk)-1. Pierwszość liczb Mersenne'a sprawdza się za pomocą testu Lucasa Lehmera. Dzieląc liczbę na 32-bitowe kawałki mamy 10kk takich kawałków. Czyli jakieś 332kk iteracji, a każda iteracja do podniesienie tych 10kk kawałków do kwadratu :) Jak pisałem obliczenia rozproszone tutaj już nie spełniają roli, bo mimo zmniejszenia czasu pojedynczej iteracji poprzez rozbicie na wiele maszyn zostaje dodany czas przesyłu danych do/z serwera czyli kilkadziesiąt ms (a nawet więcej, bo w projekcie biorą udział ludzie z różnych krajów). Zakładając, że jedna iteracja, czyli podniesienie do kwadratu zajęłoby 1ms, to czas na sprawdzenie pojedynczej liczby to 4 dni :) Przy obliczeniach rozproszonych to będzie 4*(ilość_ms_na_przesył_danych) dni, czyli dużo :P Stąd wg mnie lepiej użyć jednego, szybkiego komputera. Do tego jednak zwykły procesor nie wystarczy, a naprawdę szybki procesor obliczeniowy i dobrze zaimplementowany algorytm mnożenia np Fourera lub Shoenhage-Strassena (Karatsuba jest stanowczo zbyt wolny).

PS. O MatLabie nie słyszałem? Co to, czy mogę to jakoś wykorzystać?

Offline vinc999

  • Użytkownik

# Sierpień 17, 2011, 20:29:00
Matlab - z angielskiego to jest MATrix LABolatory. To jest takie srodowisko obliczeniowe. Na poczatku w zasadzie oferowalo tylko mozliwosc szybkich obliczen na macierzach itp + wizualizacje. Obecnie tam jest ogrom roznych toolboxow do roznych zastosowan (od analizy sygnalow po ekonomie czy AI).

W praktyce - piszesz tam skrypty i to cos liczy:))) Cos jak mathematica:) W zasadzie matlab i mathematica to sa takie podstawowe narzedzia dla naukowcow. Choc osobiscie na mathematice sprawdzilem, ze z wydajnoscia jest bardzo slabo. Z matlabem powinno byc jednak znacznie lepiej.

Offline davidbnpl

  • Użytkownik

# Sierpień 17, 2011, 23:45:45
Raczej z góry mogę założyć, że nie udostępnią mi na MatLabie mocy obliczeniowej rzędu 1TFLOP na xxx dni :) Może dla małych/średnich obliczeń tak, ale na pewno nie na całe miesiące obliczeń. To by było zbyt piękne mieć taką moc obliczeniową do dyspozycji za darmo ;)

Offline vinc999

  • Użytkownik

# Sierpień 17, 2011, 23:48:16
Nie jestem w stanie Ci odpowiedziec na ta watpliwosc:)

Offline Witek9002

  • Użytkownik

# Sierpień 18, 2011, 00:19:34
1TFLOP
Nie ma takiej jednostki jak "FLOP". Jeśli już, to FLOPS od Floating point operation per second. :) Dużo ludzi popełnia ten błąd...