Jaki jest najbardziej wydajny algorytm podzielności?

12

$a$ $b$ $a$ $b$ $a$ $b$ $O(m\log m\log\log m)$ $m$ $\max\{a,b\}$ $\Omega(m\log m\log\log m)$ dolna granica tego problemu?

Dziękuję i pozdrawiam, i przepraszam, jeśli to takie naiwne pytanie.

time-complexity lower-bounds nt.number-theory primes Leandro Zatesko
źródło

AFAIK nie są znane żadne trywialne dolne granice. Wierzę , że mnożenie i dzielenie są znane z tej samej złożoności (chociaż może to być logarytm logarytmiczny?) Metodą Newtona, a ponieważ nie ma znanej nieliniowej dolnej granicy mnożenia, to myślę, że jakakolwiek dolna granica formy Twoim zdaniem byłby to znaczący wynik.

Steven Stadnicki

(Właściwie, patrząc na to teraz, myślę, że współczynnik logarytmiczny zanika, ponieważ podczas wykonywania nietrwałej liczby mnożenia, nie wszystkie mają tę samą długość, więc czynniki superliniowe mogą być absorbowane w taki sam sposób, jak: np.

\sum_{k = 1}^{⌊ \lg n ⌋} \frac{n}{2^{k}}

$\sum_{k=1}^{\lfloor\lg n\rfloor} \frac{n}{2^k}$ jest nadal liniowy w

n

$n$ mimo że ma niestałą liczbę czynników „liniowych”.)

Steven Stadnicki

4

Przekształcając moje komentarze w odpowiedź: ponieważ podzielność (trywialnie) sprowadza się do dzielenia, a ponieważ dzielenie (nieprofesjonalnie) sprowadza się do mnożenia za pomocą metod takich jak metoda Newtona, twój problem powinien mieć tę samą złożoność czasową jak mnożenie liczb całkowitych. AFAIK, nie ma znanych dolnych granic mnożenia lepszych niż trywialna liniowa, więc to samo powinno dotyczyć twojego problemu - w szczególności, ponieważ wiadomo, że mnożenie ma (zasadniczo) algorytmy, twoje nadzieje na dolną granicę są prawie na pewno daremne. $O(n\log n\log^* n)$ $n\log n\log\log n$

Powodem, dla którego podział precyzyjnie sprowadza się do złożoności do mnożenia - jak rozumiem - jest to, że metoda Newtona wykonuje sekwencję mnożenia o różnych rosnących rozmiarach; oznacza to, że jeśli istnieje algorytm mnożenia ze złożonością wówczas złożoność algorytmu dzielenia używającego tego algorytmu mnożenia jako kroku pośredniego będzie przebiegać zgodnie z - i dla wszystkich omawianych klas złożoności jest to po prostu . $\Theta(f(n))$ $\Theta\left(\sum_{k=0}^{\lg n} f(\frac{n}{2^k})\right)$ $\Theta(f(n))$

Steven Stadnicki
źródło

2

Nitpick: Nie rozumiem, w jaki sposób uzyskujesz niższą granicę z tego rodzaju rozumowania, nawet jeśli założymy, że nie ma lepszych algorytmów mnożenia niż te obecnie znane. Twoje redukcje oznaczają, że podzielność nie jest trudniejsza niż pomnożenie. Ale nadal istnieje możliwość, że podzielność może być łatwiejsza niż dzielenie i łatwiejsza niż mnożenie, ponieważ podzielność wymaga tylko odpowiedzi typu tak / nie zamiast liczby. (Przynajmniej wspomniana redukcja nie wydaje się wykluczać.)

DW

2

@DW Zgoda, i to jest doskonały punkt; ale nie próbowałem dostać dolnej granicy. Chodzi raczej o to, że jakakolwiek dolna granica podzielności implikuje odpowiednią dolną granicę przy mnożeniu, a ponieważ żadne takie granice nie są znane poza trywialną liniową granicą, to uzyskanie lepszej niż liniowa dolnej granicy podzielności (która jest częścią tego OP, o które poproszono) jest mało prawdopodobne.

Steven Stadnicki

@DW Nie byłbym całkowicie zszokowany, gdybym dowiedział się o liniowej górnej granicy podzielności, a jak mówisz, nie oznaczałoby to nic o górnych granicach mnożenia, ale nie ma konkretnych wyników w tym kierunku AFAIK.

Steven Stadnicki

-2

Myślę, że istnieją hacki wedyjskie dla niektórych liczb kończących się na 3,7 itd. Lub bazowe dzielniki 2 ^ n ...

Ogólnie jednak algorytm najszybszego podziału wydaje się być normą.

Najlepszy, jaki znam bez patrzenia, to algorytm D metod seminumerycznych Knutha ... Nigdy jednak nie sprawdziłem jego poprawności. Działa w przybliżeniu O (mn-n ^ 2), gdzie m i n są dywidendą i dzielnikiem ... bez uwzględnienia złożoności mnożenia faktorów ...

Dolna granica może być zaskakująco niska, ponieważ twoje pytanie dotyczy tylko problemu decyzyjnego.

Phil
źródło

Jaki jest najbardziej wydajny algorytm podzielności?

Odpowiedzi: