Wie nah kommen wir der linearen Multiplikation, Addition und dem Vergleich (mit ganzen Zahlen)?

21

In Übereinstimmung mit KW Regans Artikel "Connect the Stars" erwähnt er am Ende, dass es immer noch ein offenes Problem ist, eine Darstellung von ganzen Zahlen zu finden, so dass die Additions-, Multiplikations- und Vergleichsoperationen in linearer Zeit berechenbar sind:

Gibt es eine Darstellung von ganzen Zahlen, so dass Addition, Multiplikation und Vergleich in linearer Zeit möglich sind? Gibt es grundsätzlich einen linearen zeitdiskret geordneten Ring?

(1) Wie nahe können wir der linearen Zeitmultiplikation und -addition ohne Vergleiche kommen? Hier gehe ich davon aus, dass die Problemgrößen variieren können, sodass wir möglicherweise eine Datenstruktur / einen Datenalgorithmus benötigen, mit dem sich ganzzahlige Größen ändern lassen.

(2) Für das vollständige Problem können wir davon ausgehen, dass wir ein optimales Schema zum Multiplizieren, Addieren und Vergleichen der ganzen Zahlen finden. Wie nahe können wir der linearen Zeit die langsamste dieser drei Operationen (im schlimmsten Fall) kommen? Und in diesem Sinne, wie schnell wären die anderen Operationen?

FORMALE PROBLEMERKLÄRUNG

Wie Emil Jeřábek erwähnt, möchten wir Trivialfälle ausschließen und uns bei dieser Frage auf das Worst-Case-Verhalten konzentrieren.

Wir fragen also nach nicht negativen ganzen Zahlen und y, wobei 0 x < n und 0 y < n ist. Können wir eine Datenstruktur / einen Datenalgorithmus finden, die / der Addition, Multiplikation und Vergleich mit \ zwischen x und y durchführen kann ? in O ( n log ( n ) ) Zeit und O ( log 2 ( n ) ) Raum?xy0x<n0y<nxyO(nlog(n))O(log2(n))

Matt Groff
quelle
1
Ich erwähne, dass es möglich ist, ein Schema zu erstellen, das diese Operationen in der Zeit für nicht negative ganze Zahlen ausführt , wobei n die Bitgröße der größten ganzen Zahl ist (vorausgesetzt, wir kennen n im Voraus ). Ich frage mich, ob wir es besser machen können und zwar in der Zeit, die proportional zu den aktuell berechneten Ganzzahlen ist. Θ(n)nn
Matt Groff
5
@TysonWilliams: Ja! Binär!
Jeffs
2
Gibt es eine Darstellung von ganzen Zahlen, damit alle diese Operationen die Zeit haben, anstatt die lineare Zeit für alle diese Operationen zu erhalten ? O(nlogn)
Emil Jeřábek unterstützt Monica
4
Tatsächlich gibt es eine triviale positive Antwort: Stellen Sie ganze Zahlen in Binärform mit Auffüllbits dar. Sollte die Anweisung nicht eine Bedingung dahingehend enthalten, dass die Länge der Darstellung in der Länge der binären Darstellung linear sein sollte? n2
Emil Jeřábek unterstützt Monica
5
EmilJeřábek @: Ich nehme an, er die Darstellung eines beliebigen ganzzahligen will Gebrauch f ( n ) Bits, für eine Funktion f ( n ) = Θ ( log n ) . nf(n)f(n)=Θ(logn)
Jeffs

Antworten:

14

Wahrscheinlich nicht die beste Antwort, aber vielleicht ist dies ein nützlicher Ausgangspunkt. Wenn wir eine nicht negative ganze Zahl darstellen möchten, können wir sie als eine Reihe von Modulo-Sequential-Primzahlen mit Resten ab 2 speichern. In dieser Form ist der Vergleich möglicherweise schwierig, aber die Multiplikation und Addition kann ziemlich schnell durchgeführt werden. Das Produkt der ersten Primzahlen wird durch p n # = exp ( ( 1 + o ( 1 ) ) n log n ) approximiert . Um also eine ganze Zahl N darzustellen , benötigen Sie Reste modulo der ersten n Primzahlen, wobein

pn#=exp((1+o(1))nlogn).
Nn . Da wir jedes N < p n # mit Resten modulo der ersten n Primreste darstellen können, können wir n log n log ( N ) nehmen . Die Zugabe und Vermehrung kann direkt zwischen Paaren von Resten erfolgen. Es gibt n solcher Paare, wobei die maximale Primzahl bei n log ( n ) liegt . Also soll der Zusatz drin seinN<exp((1+o(1))nlogn)N<pn#nnlognlog(N)nnlog(n) , währendMultiplikation über Schönhage-Strassen in sein sollte , O ( n log log ( N ) log log log log ( N ) log log log ( N ) ) . Da n log n log N ist , ergibt eine grobe Näherung n in O ( log N / log log N )O(nloglog(N))O(nloglog(N)loglogloglog(N)logloglog(N))nlognlogNnO(logN/loglogN). Dies würde die Komplexität der Addition und Multiplikation als etwa und O ( log N log log log N log log log log N ) .O(logN)O(logNlogloglogNloglogloglogN)
Joe Fitzsimons
quelle
1
siehe auch chinesischer
restsatz
1
@vzn: Ja, ich wollte das für Vergleiche erwähnen, aber dann kam mir der Gedanke, dass es eine schnellere Vergleichsoperation über eine gemischte Radix-Darstellung geben könnte.
Joe Fitzsimons