erste n Ziffern einer Potenzierung

Berechnen Sie ein ^b durch die folgenden Iterationen:

a ₁ = ein ¹ ,
ein ₂ = a ² ,
...
ein _i = ein ⁱ ,
...
ein _b = a ^b

Sie haben ein _{i + 1} = ein _i × a . Berechne jedes a _i nicht genau. Der relative Fehler von a ^b ist kleiner als n mal der relative Fehler von a .
Sie möchten einen relativen Fehler kleiner als 10 ^-n erhalten. Daher kann der relative Fehler in jedem Schritt sein. Entfernen Sie die letzten Ziffern bei jedem Schritt.

Zum Beispiel a = 2 , b = 16 , n = 1 . Letzter relativer Fehler ist 10 ^-n = 0.1 . Der relative Fehler bei jedem Schritt ist 0,1 / 16 & gt; 0,001 . Daher sind bei jedem Schritt 3 Ziffern wichtig. Wenn n = 2 ist, müssen Sie 4 Ziffern speichern. Allgemeine Regel: Speichern Sie bei jedem Schritt [ n + log ₁₀ b ] Ziffern.

2 (1), 4 (2), 8 (3), 16 (4), 32 (5), 64 (6), 128 (7), 256 (8), 512 (9), 1024 ( 10) → 102,
204 (11), 408 (12), 816 (13), 1632 (14) → 163, 326 (15), 652 (16).

Antwort: 6.

Dieser Algorithmus hat eine Komplexität von O (b) . Aber es ist einfach, es zu ändern, um O (log b)

n = 9 k = 3 n ^ n = 387420489 und die Antwort sollte 387 sein

Das ist das gleiche, was @RC in seinem Code getan hat. Danke @RC Ich habe gerade die mathematische Darstellung Ihres Codes gezeigt.

Der einfachste Weg, dies programmatisch zu tun, besteht darin, einen Stringstream zu verwenden, um das Ergebnis der Potenzierung in eine Zeichenkette umzuwandeln und dann die n höchstwertigen (d. h. linken) Zeichen zu nehmen.

Wenn Sie einen Weg ohne Strings wollen, dann wird dies funktionieren:

Aber es ist kaum der eleganteste Code. Ich bin mir sicher, dass du es verbessern kannst.

Für diesen Fall - mit magischen Zahlen 12,13,4:

output="1069"

intVal = 1069

BEARBEITEN: Dies sollte für jede Kombination funktionieren, bei der das Ergebnis double nicht überläuft.