Potenzieren zur Basis 2 bei großer Input-Zahl

Naja, das ist jetzt eine Frage davon, wie man die Aufgabe auffasst. Wenn man einfach nur das Ergebnis haben will, tut's in einer handelsüblichen UNIX-Shell

echo $(echo 2^1000 | bc  | sed -e 's/\\//' -e 's/\([0-9]\)/\1+/g')0 | bc

...aber damit gehen Spaß und Lerneffekt natürlich völlig verloren.

Was die schnelle Exponentialfunktion angeht (also Abkürzung über Quadrate), so klingt das zunächst besser, als es am Ende tatsächlich ist. Die Quadratur einer langen Zahl läuft, wenn man keine guten Tricks in der Tasche hat (ich glaube, es gab da etwas mit Fourier-Trafos, hab das aber gerade nicht auf dem Schirm), in O(n²) mit der Anzahl ihrer Stellen, und die Anzahl der Stellen ist proportional zum Exponenten. Die Verdoppelung einer langen Zahl dagegen läuft in O(n). Daher ist O("schnelle" Exponentialfunktion) > O(n²) = O(Grundschulmethode). Ich wage allerdings nicht abzuschätzen, wo der Break-Even-Punkt liegt.

SeppJ

Bashar schrieb:

µngbd schrieb:

Ich nehme irgendwas mit Bignums, hier habe ich einen Schemeinterpreter:

Das ist bekannt, in Python hat es der OP ja schon gelöst. Die große Frage ist nur noch, ob es ohne Bignums geht.

Vom Metadenken her wurde ich sagen ja. Projekt Euler würde die Aufgabe nicht stellen, wenn sie durch Wahl der Programmiersprache/Bibliothek trivial wäre. Das 2^1000 dürfte deshalb gewählt sein, so dass man etwas nachdenkt, bevor man es stumpf ausrechnet und dabei eine bessere Methode entdeckt.

Wobei ich selber auch nicht da drauf komme, was das sein könnte und um im Netz nach einer cleveren Lösung zu suchen, bin ich zu stolz.

knivil

Diese Euleraufgabe gehoert zu den einfacheren. Sie ist trivial. Dummes Ausreichen und Addieren reicht voellig. Wenn man keine BigInt-LIbrary benutzen moechte, kann man mit 2^1000 : 2^3 + 2^1 aehnlich der Polynomdivision jede Ziffer einzeln abspalten. Die Muehe habe ich mir nicht gemacht. Die interessanten Aufgaben kommen spaeter.

volkard

knivil schrieb:

Wenn man keine BigInt-LIbrary benutzen moechte, kann man mit 2^1000 : 2^3 + 2^1 aehnlich der Polynomdivision jede Ziffer einzeln abspalten. Die Muehe habe ich mir nicht gemacht.

Ähm. 1000 Polynomdivisionen statt 1000 Verdopplungen? Verstehe nicht, warum Du das ansetzt.

Bashar

Wenn man sich die Mühe nicht machen will und alles trivial findet, ist das völlig egal, ob man eine schnelle, langsame, oder überhaupt nicht funktionierende Lösung hat, äh, hätte.

knivil

volkard schrieb:

Ähm. 1000 Polynomdivisionen statt 1000 Verdopplungen? Verstehe nicht, warum Du das ansetzt.

Du meinst char-Zahlen verdoppeln ist einfacher?

Bashar schrieb:

Wenn man sich die Mühe nicht machen will und alles trivial findet, ist das völlig egal, ob man eine schnelle, langsame, oder überhaupt nicht funktionierende Lösung hat, äh, hätte.

Ja, klar. In den Lösungs-Foren bei Project Euler finden sich am Anfang auch meistens analytische Lösungen, die ohne Computer auskommen. Aber es geht dort ihmo auch darum, dass man mit irgendeiner Bignum-Variante umgehen kann, damit man später bequem weiterkommt.

Zum Beispiel das hier:
http://projecteuler.net/index.php?section=problems&id=13

Was wollt ihr da ohne Computer ausrichten?

volkard

knivil schrieb:

volkard schrieb:

Ähm. 1000 Polynomdivisionen statt 1000 Verdopplungen? Verstehe nicht, warum Du das ansetzt.

Du meinst char-Zahlen verdoppeln ist einfacher?

Ja, aber um einiges.

volkard

µngbd schrieb:

Zum Beispiel das hier:
http://projecteuler.net/index.php?section=problems&id=13
Was wollt ihr da ohne Computer ausrichten?

Ohne Computer würde ich es nicht machen. Aber eine Bignum-Lib ist hier noch nicht nötig.

volkard

µngbd schrieb:

Aber es geht dort ihmo auch darum, dass man mit irgendeiner Bignum-Variante umgehen kann, damit man später bequem weiterkommt.

Ich hab wohl noch nicht genügend Aufgaben gelesen, aber bisher hatte ich den Eindruck, daß es ohne Bignum mehr Spaß machen würde. Ja, sogar einige Aufgaben explizit darauf angelegt sind, daß man eine wunderschöne mathematische Vereinfachung findet, die es erlaubt, auf Bignums zu verzichten.