mnożenie wielkich liczb

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

Jest udowodnione, to jest Schonchage - Strassen algorytm, w modelu RAM, jest on nawet O(n). Zobacz. na przykład, tutaj:

Chociaż pewnie wyprzedzi Karatsubę dla liczb większych niż 1000 cyfr.

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...

lion137 napisał(a):

Jest udowodnione, to jest Schonchage - Strassen algorytm, w modelu RAM, jest on nawet O(n). Zobacz. na przykład, tutaj:

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 * 4*10 * 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 * 4*20 * 5 = n * 400

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

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:

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 * 4*10 * 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 * 4*20 * 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?

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.

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... :)

https://www.mathsisfun.com/long_division3.html

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/Approximations_of_%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.

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.

"Koszt: 2log(n) mnożeń, czyli całkiem przyzwoicie;"

Nie rozpowszechniaj, jakiejś fake science, tylko Przeczytaj podlinkowany artykuł z wikipedii, dzielenie jest O(mnożenie).

lion137 napisał(a):

"Koszt: 2log(n) mnożeń, czyli całkiem przyzwoicie;"

Nie rozpowszechniaj, jakiejś fake science, tylko Przeczytaj podlinkowany artykuł z wikipedii, dzielenie jest O(mnożenie).

W praktyce wyjdzie 2 góra 4 mnożenia, ponieważ mnożymy tu krótkie liczby, które się sukcesywnie wydłużają:
x = 16 cyfr - na starcie, zatem mnożymy 16-cyfrową, co jest łatwe,
otrzymujemy 32 cyfry, potem 64, itd.

co daje w sumie koszt około 2 pełnych mnożeń zaledwie.

Zatem pozostaje spróbować opracować wersję dla czwórek:
4: n^(log7/log4) = n^1.40

mnożenie wielomianów stopnia 3:
(a,b,c,d)(e,f,g,h) = (ae, af+be, ag+ce+bf, ...

i teraz według schematu:
z1 = ..
z2 =
...
z7 =

Porównanie metody 4 z FFT dla obliczeń w precyzji miliona cyfr.

milion cyfr dziesiętnych to około 100 tysięcy liczb binarnych typu 32-bit, zatem:

n = 100000 = 1e5;
więc dla wersji z czwórkami otrzymamy liczbę operacji: n^1.4 = 100n.

a metoda FFT: n * 4log(1e5) * loglog(1e5) > 260n

czyli FFT byłaby tu prawie 3 razy gorsza.

exp napisał(a):

Porównanie metody 4 z FFT dla obliczeń w precyzji miliona cyfr.

milion cyfr dziesiętnych to około 100 tysięcy liczb binarnych typu 32-bit, zatem:

n = 100000 = 1e5;
więc dla wersji z czwórkami otrzymamy liczbę operacji: n^1.4 = 100n.

a metoda FFT: n * 4log(1e5) * loglog(1e5) > 260n

czyli FFT byłaby tu prawie 3 razy gorsza.

Znowu piszesz rzeczy wyssane z palca. Wikipedia podaje, że Schonchage - Strassen Algorytm, jest szybszy od wcześniejszych (m. in. Karatsuba), dla liczb od 10 do 40 tysięcy cyfr dziesiętnych.

lion137 napisał(a):

exp napisał(a):

Porównanie metody 4 z FFT dla obliczeń w precyzji miliona cyfr.

milion cyfr dziesiętnych to około 100 tysięcy liczb binarnych typu 32-bit, zatem:

n = 100000 = 1e5;
więc dla wersji z czwórkami otrzymamy liczbę operacji: n^1.4 = 100n.

a metoda FFT: n * 4log(1e5) * loglog(1e5) > 260n

czyli FFT byłaby tu prawie 3 razy gorsza.

Znowu piszesz rzeczy wyssane z palca. Wikipedia podaje, że Schonchage - Strassen Algorytm, jest szybszy od wcześniejszych (m. in. Karatsuba), dla liczb od 10 do 40 tysięcy cyfr dziesiętnych.

Karatsuba to metoda podziału na 2, która ma złożoność około n^1.6, co w tym przypadku daje: 1000n, co faktycznie jest większe od 260n - FFT.

Metoda czwórek jest szybsza 10 razy od par - wykładnik 1.4, co daje 100n, i jest szybsza od FFT w tym przypadku, tz. dla n = 100000.

Opublikuj swoją "Metodę Czwórek", roześlij do sprawdzenia i chwała Ci, a jak nie, to nie Fantazjuj.

lion137 napisał(a):

Opublikuj swoją "Metodę Czwórek", roześlij do sprawdzenia i chwała Ci, a jak nie, to nie Fantazjuj.

Metoda podziału na k=4 części to tylko kolejny szczególny przypadek.

Optymalne mnożenie pewnie polegałoby na podziale na: k = logn;
co w przypadku n=100 tyś. daje k = 16, więc złożoność na poziomie: ln(31)/ln(16) = 1.24 ->
16n, czyli około 16 aż razy szybciej od FFT.

Może ktoś ma coś do dodania, ale Dyskutujesz sam ze sobą; dla mnie EOT.

lion137 napisał(a):

Może ktoś ma coś do dodania, ale Dyskutujesz sam ze sobą; dla mnie EOT.

zadaniem dla ciebie jest wyprowadzenie schematu dla czwórek,
a nie gadanie dookoła o wydumanej wyższości FFT nad wszelkimi innymi metodami, co już na samym początku pokazałem.

exp napisał(a):

Koszt: 2log(n) mnożeń, czyli całkiem przyzwoicie;
np. 1000 'cyfr' wymaga tu około 20 mnożeń zaledwie;

Jak masz daną wejściową o długości N i każdy element tych danych ma wpływ na wynik końcowy, to nie ma szans taki algorytm musi mieć złożoność co najmniej o(n), bo musisz odczytać wszystkie dane.
Wniosek: by osiągnąć to twoje 2log(n) podczas mnożenia, musisz zignorować część danych wejściowych i wyjściowych, więc jest oczywiste, że bujasz w obłokach, albo gdzieś coś źle przeczytałeś.

Jak masz daną wejściową o długości N i każdy element tych danych ma wpływ na wynik końcowy, to nie ma szans taki algorytm musi mieć złożoność co najmniej o(n), bo musisz odczytać wszystkie dane.
Wniosek: by osiągnąć to twoje 2log(n) podczas mnożenia, musisz zignorować część danych wejściowych i wyjściowych, więc jest oczywiste, że bujasz w obłokach, albo gdzieś coś źle przeczytałeś.

Wszystko jest OK.
Gdy obliczasz 1/a metodą Newtona - rząd 2,
wówczas w każdym kroku podwajasz liczbę cyfr.

Zatem w kolejnych krokach musisz tu utrzymać jedynie precyzję x 2 z poprzedniego wyniku, ponieważ dalsze cyfry są tu bezużyteczne.

x0 = 8 cyfr,
x1 = 16 cyfr - i tyle wystarczy użyć, nie potrzeba więcej.
x2 = 32
itd.

zatem nie mnożymy tu dwóch liczb o tysiącach cyfr każda, a tylko takie mnożenie jest kosztowne!

x = x(2-ax)

x ma 16 cyfr tylko, potem 32, itd.
jedynie 'a' może tu być długa, np. 1000000 cyfr.

Mnożenie: 16567555576467546 x 7, jest drastycznie szybsze od: 16567555576467546 x 77656744353543453,
bo to jest liniowe - n cyfr kolejno mnożysz przez 7, czyli koszt wynosi jedynie: n, a nie więcej.

Prościej - dla szkolnej metody mnożenia mamy: n^2 operacji, ale dla liczb o długości n każda.
Faktycznie tam jest: nm; n, m - długości obu liczb.

Zatem posumujmy ile tego wyjdzie w... sumie:
dla dwóch cyfr na starcie będzie tam 2n, a potem byłoby 4n, 8n, ... n^2 - raz na końcu.

szereg geometryczny log(n) składników:
s = 2 + 4 + 8 ... = ?

exp2 napisał(a):

Wszystko jest OK.
Gdy obliczasz 1/a metodą Newtona - rząd 2,

?? 1/a metodą Newtona? Przecież w samej metodzie Newtona masz dzielenie.

exp2 napisał(a):

wówczas w każdym kroku podwajasz liczbę cyfr.

Zatem w kolejnych krokach musisz tu utrzymać jedynie precyzję x 2 z poprzedniego wyniku, ponieważ dalsze cyfry są tu bezużyteczne.

Już to zdanie wskazuje na złożoność kwadratową!

Cały ten twój opis wskazuje na to, że najwyraźniej nie rozumiesz czym jest notacja o i jak wyznacza się złożoność czasową algorytmów (nie jest to łatwe), dlatego wychodzi ci coś bezsensu.

Zamiast męczyć się nad pisaniem niestworzonych opisów, zrób coś praktycznego.
Napisz kod, który według ciebie ma złożoność czasową logarytmiczną, dopisz testy, żeby udowodni iż działa poprawnie, a potem go pokaż.
Jeśli okaże się, że masz rację wszyscy cię tu ogłoszą największym geniuszem tego forum, ba może ktoś cie nominuje do medalu Fieldsa.

Gdy obliczasz 1/a metodą Newtona - rząd 2,

?? 1/a metodą Newtona? Przecież w samej metodzie Newtona masz dzielenie.

dzielenie za pomocą metody Newtona:

1. bierzesz funkcję: f(x) = 1/x - a
2. wyznaczamy punkt zerowy tej funkcji, czyli: 1/x = a => x = 1/a

Metoda Newtona dla pierwiastków:
x -> x - y/y' = x - (1/x - a)/(-1/x^2) = x + x - ax^2 = x(2 - ax)

zatem w kilku krokach możesz wyliczyć wartość 1/a z precyzją tysięcy cyfr, za pomocą samych mnożeń i odejmowania.

Zamiast męczyć się nad pisaniem niestworzonych opisów, zrób coś praktycznego.
Napisz kod, który według ciebie ma złożoność czasową logarytmiczną, dopisz testy, żeby udowodni iż działa poprawnie, a potem go pokaż.
Jeśli okaże się, że masz rację wszyscy cię tu ogłoszą największym geniuszem tego forum, ba może ktoś cie nominuje do medalu Fieldsa.

Metod rzędu 2 produkuje n cyfr poprawnych w log(n) krokach - nie wiedziałeś o tym?

2^log(n) = n

@nalik: A jaka jest - dla przykładu - złożoność zapisania tych n cyfr z powrotem do pamięci? Ilość kroków to nie to samo co złożoność algorytmu, ważne jest ile w każdym kroku wykonuje się operacji. Jeżeli podwajasz ilość cyfr w każdym kroku, to rośnie Ci wielkość problemu.

Oczywiście że liczba obliczeń tu rośnie - podwaja się w każdym kroku.
czyli log(n) takich coraz dłuższych mnożeń to koszt 2 pełnych mnożeń - n x n.

co znaczy że złożoność dzielenia jest porównywalna z mnożeniem: o(mul) = o(div) - dla długich liczb, seki cyfr i więcej.

Inna metoda realizacji dzielenia - obliczamy: x = 1/sqrt(a), i finalnie wyliczamy, w jednym mnożeniu: x^2 = 1/a.
Może być szybciej, o ile metoda wyliczania 1/sqrt będzie szybsza od tej Newtona, np. rzędu 3, ale niewiele, np. 1.5 mnożeń, zamiast 3.

A może i szybciej to pójdzie.

x = x(2 - ax)

a nas interesuje tylko podwójna precyzja obliczeń w każdym kroku, zatem tu faktycznie będzie tylko:
2^2 + 4^2 + 8^2 + ... (n/2)^2, zamiast: 2n + 4n + 8n + ... n^2

s = 2^2 + 4^2 + 8^2 + ... = 2^2 + 2^4 + 2^6 + 2^8 + ... = ~ 1/3 n^2
albo 4/3 jeśli wykonamy jeszcze kolejne mnożenie: n x n = 1n^2.