Was ist der effizienteste Algorithmus für die Teilbarkeit?

12

Was ist der effizienteste Algorithmus (in Bezug auf die zeitliche Komplexität), der heutzutage für das Divisibitätsentscheidungsproblem bekannt ist: Wenn zwei ganze Zahlen $a$ und $b$ , ist $a$ Division von $b$ ? Es sei klargestellt, dass das, wonach ich bitte, kein (notwendiger) Algorithmus für die Restberechnung ist. Ich möchte nur wissen, ob $a$ teilt oder nicht. Als spezifischere, ist meine Frage , ob einige der jüngsten Algorithmus für Teilbarkeit mit Zeitkomplexität besser als existiert oder nicht , wobei die Anzahl der Bits ist $b$ $O(m\log m\log\log m)$ $m$ $\max\{a,b\}$ . Ist die untere Grenze dieses Problems? $\Omega(m\log m\log\log m)$

Danke und Grüße, und tut mir leid, wenn dies eine so naive Frage ist.

time-complexity lower-bounds nt.number-theory primes Leandro Zatesko
quelle

AFAIK Es sind keine nicht trivialen Untergrenzen bekannt. Ich glaube, dass Multiplikation und Division nach Newtons Methode bekanntermaßen im Wesentlichen dieselbe Komplexität aufweisen (obwohl dies möglicherweise an einem logarithmischen Faktor liegt?), Und da keine nichtlineare Untergrenze für die Multiplikation bekannt ist, denke ich, dass jede Untergrenze der Form gleich ist Sie behaupten, wäre ein wichtiges Ergebnis.

Steven Stadnicki

(Wenn ich es mir jetzt anschaue, denke ich, dass der Log-Log-Faktor wegfällt, weil bei einer nicht konstanten Anzahl von Multiplikationen nicht alle gleich lang sind, sodass die superlinearen Faktoren auf die gleiche Weise absorbiert werden können, zB ist in immer noch linear , obwohl es eine nicht konstante Anzahl von 'linearen' Faktoren gibt.)

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

$\sum_{k=1}^{\lfloor\lg n\rfloor} \frac{n}{2^k}$

n

$n$

Steven Stadnicki

4

Meine Kommentare zu einer Antwort zusammenfassen: Da die Teilbarkeit (trivial) auf die Teilung und die Teilung (nichttrivial) auf die Multiplikation über Ansätze wie Newtons Methode reduziert werden kann, sollte Ihr Problem dieselbe zeitliche Komplexität haben wie die ganzzahlige Multiplikation. AFAIK, es gibt keine bekannteren Untergrenzen für die Multiplikation als die triviale lineare, daher sollte das Gleiche für Ihr Problem gelten - und insbesondere, da bekannt ist, dass die Multiplikation (im Wesentlichen) Algorithmen, Ihre Hoffnungen auf eine Untergrenze sind mit ziemlicher Sicherheit vergebens. $O(n\log n\log^* n)$ $n\log n\log\log n$

Der Grund, warum sich die Komplexität der Division genau auf die Multiplikation reduziert - so wie ich es verstehe -, ist, dass Newtons Methode eine Folge von Multiplikationen mit unterschiedlichen eskalierenden Größen ausführt; Dies bedeutet, dass, wenn es einen Algorithmus zur Multiplikation mit der Komplexität die Komplexität eines Divisionsalgorithmus, der diesen Multiplikationsalgorithmus als Zwischenschritt verwendet, entlang der Linien von - und für alle diskutierten Komplexitätsklassen ist dies nur . $\Theta(f(n))$ $\Theta\left(\sum_{k=0}^{\lg n} f(\frac{n}{2^k})\right)$ $\Theta(f(n))$

Steven Stadnicki
quelle

2

Nitpick: Ich verstehe nicht, wie diese Art von Argumentation zu einer niedrigeren Grenze führt, auch wenn wir davon ausgehen, dass es keine besseren Algorithmen für die Multiplikation gibt als die derzeit bekanntesten. Ihre Verringerungen implizieren, dass die Teilbarkeit nicht schwieriger ist als die Multiplikation. Es besteht jedoch weiterhin die Möglichkeit, dass die Teilbarkeit einfacher ist als die Teilung und einfacher als die Multiplikation, da für die Teilbarkeit nur eine Ja / Nein-Antwort anstelle einer Zahl erforderlich ist. (Zumindest scheint die erwähnte Reduzierung das nicht auszuschließen.)

DW

2

@ DW einverstanden, und das ist ein ausgezeichneter Punkt; aber ich habe nicht versucht, eine Untergrenze zu bekommen. Der Punkt ist vielmehr, dass jede untere Grenze für die Teilbarkeit die entsprechende untere Grenze für die Multiplikation impliziert, und da keine derartigen Grenzen über die triviale lineare Grenze hinaus bekannt sind, wird eine bessere als die lineare untere Grenze für die Teilbarkeit erhalten (was ein Teil dessen ist) OP gefragt) ist unwahrscheinlich.

Steven Stadnicki

@DW Ich wäre nicht ganz schockiert, wenn ich von einer linearen Obergrenze für die Teilbarkeit erfahren würde , und wie Sie sagen, würde das nichts spezielles über Obergrenzen für die Multiplikation bedeuten, aber es gibt keine spezifischen Ergebnisse in dieser Richtung AFAIK.

Steven Stadnicki

-2

Ich denke, es gibt vedische Arten von Hacks für einige Zahlen, die mit 3,7 enden. Oder Basis 2 ^ n Divisoren ...

Aber im Allgemeinen scheint der schnellste Teilungsalgorithmus die Norm zu sein.

Das beste, das ich kenne, ohne es zu studieren, ist Algorithmus D von Knuths seminarischen Methoden. Es läuft in mehr oder weniger O (mn-n ^ 2), wobei m und n die Dividende und der Divisor sind ... ohne Berücksichtigung der Multiplikationskomplexität ...

Eine Untergrenze könnte jedoch überraschend niedrig sein, da sich Ihre Frage nur mit dem Entscheidungsproblem befasst.

Phil
quelle

Was ist der effizienteste Algorithmus für die Teilbarkeit?

Antworten: