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

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

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). $1+\lfloor \log_2(x^n)\rfloor=1+\lfloor n\log_2(x)\rfloor$ $\log_2(x)$ $\log_2(x)$ $k$ $O(M(k)\log k)$ $M(k)$ $k$ $O(s\log^2 s)$ $s$ $x$ $n$

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? $O(s\log^2(s))$ $s$ $x$ $n$

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

complexity-theory time-complexity binary-arithmetic 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:

[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 . $\log(x)$ $k$ $x^{2^k}$

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$ $y$ $1+\lfloor \log y\rfloor$

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. $\left|x^{2^k}\right| = 1+\lfloor 2^k\log x\rfloor$ $2^k\log(x)$ $\log(x)$ $k$ $\log(x)$ $k$ $1$ $x^{2^k}$ $k$

Bruno
quelle

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?

x^{2^{k}}

$x^{2^k}$

\log x

$\log x$

k

$k$

n = 2^{k}

$n=2^k$

n

$n$

@ 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 von

y

$y$

1 + ⌊ \log y ⌋

$1+\lfloor\log y\rfloor$

x^{2^{k}}

$x^{2^k}$

1 + ⌊ 2^{k} \log x ⌋

$1+\lfloor 2^k\log x\rfloor$

2^{k} \log x

$2^k\log x$

\log x

$\log x$

k

$k$

⌊ 2^{k} \log x ⌋

$\lfloor 2^k\log x\rfloor$

k

$k$

\log x

$\log x$

x^{2^{k}}

$x^{2^k}$

1

$1$

k

$k$

\log x

$\log x$ . 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.