Berechnen der Anzahl von Bits einer großen Potenz von ganzen Zahlen

10

Wie komplex ist die Berechnung der Bitgröße von zwei Ganzzahlen und in binärer Darstellung ?n x nxnxn

Eine Möglichkeit, dies zu tun, besteht darin, berechnen, indem eine Näherung von mit ausreichender Genauigkeit berechnet wird . Es scheint, dass die Berechnung von mit Genauigkeitsbits in wobei die Zeit ist, die benötigt wird, um das Produkt von zwei ganzen Zahlen der Länge zu berechnen . Dies ergibt einen (nicht besonders einfachen) Komplexitätsalgorithmus von ungefähr wenn eine Grenze für die Bitgröße von und (wenn ich keinen Fehler gemacht habe).log 2 ( x ) log 2 ( x ) k O ( M ( k ) log k ) M ( k ) k O ( s log 2 s ) s x n1+log2(xn)=1+nlog2(x)log2(x)log2(x)kO(M(k)logk)M(k)kO(slog2s)sxn

Können wir schlagen, wobei die Größe von und (falls sie vergleichbare Größen haben)? Gibt es einen einfachen Algorithmus, um diese Komplexität oder besser zu erreichen?s x nO(slog2(s))sxn

Hinweis: Ich interessiere mich für die Komplexität eines theoretischen Modells wie Turing-Maschinen.

Bruno
quelle
schlagen vor, dies zu Theoretical Computer Science zu
vzn
@vzn: Ich denke nicht, dass dies nützlich ist ...
Bruno
warum nicht? Diese Frage erinnert mich an algorithmische Angriffe auf Dysons Vermutungen, wie sie von RJLipton in 1 , 2
vzn
Einfach, weil ich eine Antwort auf meine Frage gefunden habe, also muss ich sie mir nicht anderswo fragen.
Bruno

Antworten:

1

[Bearbeiten] Wie vorgeschlagen, bearbeite ich meine Antwort, um weitere Details anzugeben.

Die Antwort auf meine zweite Frage lautet nein :

Vorschlag. Das Berechnen von bis zur Genauigkeit ist mindestens so schwierig wie das Berechnen der Bitgröße von .k x 2 klog(x)kx2k

Beweis. Seibezeichnen die Bitgröße einer ganzen Zahl . Beachten Sie zunächst, dass für eine nichtnegative Ganzzahl die Bitgröße von beträgt .y y y 1 + log y |y|yyy1+logy

Also . Jetzt ist verschoben Positionen nach links. Somit kann man mit der Genauigkeit berechnen, indem man einfach von der Bitgröße von subtrahiert und die Ergebnis- Positionen nach rechts verschiebt. 2 k log(x)log(x)klog(x)k1 x 2 k k|x2k|=1+2klogx2klog(x)log(x)klog(x)k1x2kk

Bruno
quelle
1
Warum können Sie mit der Anzahl der Bits in auf Bits genau berechnen ? Funktioniert Ihre Ermäßigung tatsächlich? Was wäre, wenn der Sonderfall mit viel einfacher / schwieriger wäre als alle anderen möglichen Werte von (Nicht-Zweierpotenzen)? Haben Sie eine Möglichkeit, diese Möglichkeit auszuschließen? log x k n = 2 k nx2klogxkn=2kn
DW
@ DW: Ich komme nach dem Kommentar von vzn auf diese Frage zurück. Mein Beweis lautet wie folgt: Die Anzahl der Bits einer ganzen Zahl beträgt . Somit ist die Anzahl von Bits in ist . Ferner ist dasselbe wie , jedoch wurden Positionen nach links verschoben . Somit gibt Ihnen (mindestens) die ersten Bits von . Wenn Sie also die Anzahl der Bits von berechnen können , indem Sie zum Ergebnis subtrahieren , erhalten Sie die ersten Bits von1 + log y x 2 k 1 + 2 k log x 2 k log x log x k 2 k log x k log x x 2 k 1 k log xy1+logyx2k1+2klogx2klogxlogxk2klogxklogxx2k1klogx. Macht das Sinn?
Bruno
Ja, das macht für mich mehr Sinn! Zumal Sie nur versuchen, Härte zu zeigen. Darf ich Sie ermutigen, Ihre Antwort mit dieser detaillierteren Erklärung zu aktualisieren? Vielen Dank, dass Sie darauf zurückgekommen sind und die Antwort auf Ihre eigene Frage dokumentiert haben.
DW