mnożenie wielkich liczb

0

Optymalny algorytm mnożenia długich liczb, np. n=1000 cyfr ma podobno złożoność nlogn - w wersji FFT.

Czy to było udowodnione kiedykolwiek?

Mam wątpliwości, bo generalnie schemat mnożenia polega na podziale liczb na grupy cyfr, np. po dwie cyfry, 3, 4 itd.

Złożoność jest tu następująca: n do potęgi log(2k-1)/logk; gdzie k = liczba cyfr w grupie.

Można sobie sprawdzić szczególne przypadki:
2: n^(log3/log2) = n^1.585 - metoda par Karatsuby
https://en.wikipedia.org/wiki/Karatsuba_algorithm

3: n^(log5/log3) = n^1.465 - Toome3
https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication

4: n^(log7/log4) = n^1.40 - ?
...
8: n^(log15/log8) = n^ 1.3 - ?

itd.

jak widać możemy sobie tu zaserwować dowolnie mały wykładnik - znaczy dowolnie blisko 1, co jest na pewno szybsze od nlogn.

1000: ln(2*1000-1)/lln1000 = 1.1

1

Jest udowodnione, to jest Schonchage - Strassen algorytm, w modelu RAM, jest on nawet O(n). Zobacz. na przykład, tutaj:
https://www.youtube.com/watch[...]0oaFux3aafQm568blS9blxtA_EWQv
Chociaż pewnie wyprzedzi Karatsubę dla liczb większych niż 1000 cyfr.

0

Hej,
ja myślę, że aktualnie trzeba zacząć myśleć o współbieżności wykonywania pewnych procesów, działań... i niekoniecznie sekwencyjnie, można przecież równolegle to robić, tylko to trzeba robić z głową... w praktyce moim zdaniem, aby wykonać mnożenie dużych liczby, wystarczy wziąć metodę Karatsuby i od pewnego momentu puścić ją równolegle na jakimś klastrze... i szybkość będzie zależała od sposobu implementacji... wielkości klastra... i wielu innych czynników...

0
lion137 napisał(a):

Jest udowodnione, to jest Schonchage - Strassen algorytm, w modelu RAM, jest on nawet O(n). Zobacz. na przykład, tutaj:
https://www.youtube.com/watch[...]0oaFux3aafQm568blS9blxtA_EWQv
Chociaż pewnie wyprzedzi Karatsubę dla liczb większych niż 1000 cyfr.

Raczej mało prawdopodobne aby FFT wyprzedziło nawet wersję po 2 dla 1000 cyfr.
przyjmując skrajnie optymistyczny algorytm: 4nlogn loglogn, co dla n = 1024 daje około:
n
410 4 = n * 160

natomiast metoda Karatsuby: n^log3 = 59049 = n * 58, czyli szybciej od 160 x n.

Ale to jest nadal słabe, bo biorąc np.: k = 8 cyfr, otrzymamy tu: n^(log15/log8) operacji, czyli: n^1.3 = n n^0.3 = n 8, czyli aż 20 razy szybciej od FFT!
..

n = milion cyfr: 4nlogn loglogn = n 420 5 = n * 400

a metoda ósemkowa:
8: n^1.3 = n 63
a np. wersja grupowania po 16 cyfr daje tu: n
27

0
exp napisał(a):
lion137 napisał(a):

Jest udowodnione, to jest Schonchage - Strassen algorytm, w modelu RAM, jest on nawet O(n). Zobacz. na przykład, tutaj:
https://www.youtube.com/watch[...]0oaFux3aafQm568blS9blxtA_EWQv
Chociaż pewnie wyprzedzi Karatsubę dla liczb większych niż 1000 cyfr.

Raczej mało prawdopodobne aby FFT wyprzedziło nawet wersję po 2 dla 1000 cyfr.
przyjmując skrajnie optymistyczny algorytm: 4nlogn loglogn, co dla n = 1024 daje około:
n
410 4 = n * 160

natomiast metoda Karatsuby: n^log3 = 59049 = n * 58, czyli szybciej od 160 x n.

Ale to jest nadal słabe, bo biorąc np.: k = 8 cyfr, otrzymamy tu: n^(log15/log8) operacji, czyli: n^1.3 = n n^0.3 = n 8, czyli aż 20 razy szybciej od FFT!
..

n = milion cyfr: 4nlogn loglogn = n 420 5 = n * 400

a metoda ósemkowa:
8: n^1.3 = n 63
a np. wersja grupowania po 16 cyfr daje tu: n
27

Możesz jaśniej, Obejrzałeś podliknowane video, Przeczytałeś artykuł na wikipedii?

0
hurgadion napisał(a):

Hej,
ja myślę, że aktualnie trzeba zacząć myśleć o współbieżności wykonywania pewnych procesów, działań... i niekoniecznie sekwencyjnie, można przecież równolegle to robić, tylko to trzeba robić z głową... w praktyce moim zdaniem, aby wykonać mnożenie dużych liczby, wystarczy wziąć metodę Karatsuby i od pewnego momentu puścić ją równolegle na jakimś klastrze... i szybkość będzie zależała od sposobu implementacji... wielkości klastra... i wielu innych czynników...

Równolegle też lepiej wyjdzie z podziałem na grupy od FFT.
Np. dla 4 rdzeni, dzielimy to zwyczajnie na 4 grupy, lub, 16 itd., co może być obliczane niezależnie - równolegle, a potem scalane jedynie w jednym przebiegu.

0

a macie jakąś wiedzę na temat dzielenia liczb ?? jak macie, to się podzielcie, jeżeli macie ochotę... zastanawiam się, jak się dzieli liczby na komputerze... to nie takie proste... zastanawiam się także jak się przechowuje ułamki... a najbardziej interesuje mnie implementacja liczb takich jak e, pi... miałem nawet ostatnio robić na ten temat jakiś research, ale może skorzystam z Waszej pomocy... :)

1
hurgadion napisał(a):

a macie jakąś wiedzę na temat dzielenia liczb ?? jak macie, to się podzielcie, jeżeli macie ochotę... zastanawiam się, jak się dzieli liczby na komputerze... to nie takie proste... zastanawiam się także jak się przechowuje ułamki... a najbardziej interesuje mnie implementacja liczb takich jak e, pi... miałem nawet ostatnio robić na ten temat jakiś research, ale może skorzystam z Waszej pomocy... :)

Jeśli mnożenie jest M(n), to dzielenie jest O(M(n)).
Research, Powiadasz, jak zwykle dobrym punktem startowym jest wikipedia:)

Tutaj Masz artykulik o dzieleniu: https://en.wikipedia.org/wiki/Division_algorithm

Generalnie o obliczaniu pi:
https://en.wikipedia.org/wiki/Approximationsof%CF%80
Najszybszy algorytm (Chudnovsky): https://en.wikipedia.org/wiki/Chudnovsky_algorithm
Implementacja: https://www.craig-wood.com/nick/articles/pi-chudnovsky/

EDIT: widze, że wklejanie dziś linków na 4programmers zachowuje się jak kobieta zmienną jest:), to po prostu Wpisz sobie w wyszukiwarkę: "approximations of pi", to do generalnie o obliczaniu pi.

0
hurgadion napisał(a):

a macie jakąś wiedzę na temat dzielenia liczb ?? jak macie, to się podzielcie, jeżeli macie ochotę... zastanawiam się, jak się dzieli liczby na komputerze... to nie takie proste... zastanawiam się także jak się przechowuje ułamki... a najbardziej interesuje mnie implementacja liczb takich jak e, pi... miałem nawet ostatnio robić na ten temat jakiś research, ale może skorzystam z Waszej pomocy... :)

Dzielenie długich liczb - tysiące cyfr, chyba najszybciej pójdzie za pomocą Newtona:
x = x(2 - ax); co wylicza odwrotność: 1/a,
dzielenie dowolnych liczb: b/a = b * 1/a, więc to jest załatwione jednym dodatkowym mnożeniem.

Koszt: 2log(n) mnożeń, czyli całkiem przyzwoicie;
np. 1000 'cyfr' wymaga tu około 20 mnożeń zaledwie;
natomiast milion cyfr: 40, czyli tylko 2 razy dłużej.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0