Potenzieren zur Basis 2 bei großer Input-Zahl

volkard

Ich finde nichts.
Ich fürchte, man muß sich ein char zahl="0000000000...0001"; machen und eine Schleife, die von hinten nach vorne geht und die Ziffer immer verdoppelt und ggfls noch den Übertrag auf die nächste Ziffer macht, und diese Schleife von einer Drumherumschleife 1000-mal aufrufen.

Bashar

Ich probier das heute abend mal, habe schon eine vage Vorstellung, wie es geht. Wie man die 1er-Stelle (also 2^1000 mod 10) bekommt ist ja klar, ich hoffe, dass die anderen Stellen dabei mehr oder weniger kostenlos mit abfallen.

Nirvana134

In diesem Fall ist es denke ich doch relativ unkompliziert wenn man 2¹⁰⁰⁰ ausrechnet, ich schau mir das mit Modulo mal an, aber ich glaub nicht dass das hier einen großen Vorteil bringt(außer dem Lerneffekt der nicht zu unterschätzen ist).

Kennt eigentlich jemand, weitere ähnliche Seiten wie Project Euler mit Programmieraufgaben?

Bashar

Puh, es ist wohl doch nicht so einfach, wie ich dachte. Im wollte jede Stelle berechnen, indem ich (alles mod 10) 2^N/10k = 2^(N-k)/5k berechne. Ich hatte gehofft, aus sowas wie 2^2 = 5 - 1 oder 2^4 = 3*5 + 1 eine Rekursion basteln zu können, so in der Art 2^n/5k = 2^(n-2)/5(k-1) - 2^(n-2)/5k bzw. 2^n/5k = 3*2^(n-4)/5(k-1) + 2^(n-4)/5k. Klappt aber nicht so richtig, ich vermute, weil man nicht vernachlässigen kann, dass sich da manchmal Brüche <0, die ich ignoriere, zu etwas >1 addieren.

Eine Big-Integer-Bibliothek scheint mir für dieses Problem ziemlich hoch gegriffen - man braucht die Zahl ja nicht in einer Form, mit der eine Maschine gut rechnen kann, sondern am besten in Dezimaldarstellung.

2¹⁰⁰⁰ hat ungefähr 300 dezimale Ziffern, und die Anzahl der Ziffern steigt linear mit dem Exponenten, also reden wir hier von etwa 150000 Rechenschritten, wenn man mit der Grundschulmethode, die Volkard anspricht, herangeht. Ich wäre erstaunt, wenn man darauf überhaupt warten müsste.

Ich rede da jetzt von ziffernweiser Berechnung. Mit 64-Bit-Integern kann man das noch auf ein 19tel zusammenstreichen, indem man Modulo 10¹⁹ rechnet; ich halte das aber nicht für notwendig.

icarus2

Ich habe leider keine Zeit ums auszuprobieren. Aber hat es noch keiner mit Schneller Exponentiation versucht? (Hatte ich irgendo geschrieben).

Ich frage mich nämlich, wie schnell das geht. Soweit ich weiss müsste das einigermassen effizient laufen.

Bashar

icarus2 schrieb:

Ich habe leider keine Zeit ums auszuprobieren. Aber hat es noch keiner mit Schneller Exponentiation versucht? (Hatte ich irgendo geschrieben).

Was soll das bringen? 2^1000 kannst du direkt hinschreiben, das ist eine 1 mit 1000 Nullen. Das schwierige ist das Berechnen der Quersumme in Dezimaldarstellung.

dot

Ist schon ne ziemliche Weile her bei mir, aber sollte man da nicht evtl. damit was anfangen können?

Edit: Oh verdammt das geht wohl doch eher nicht^^

icarus2

Bashar schrieb:

icarus2 schrieb:

Ich habe leider keine Zeit ums auszuprobieren. Aber hat es noch keiner mit Schneller Exponentiation versucht? (Hatte ich irgendo geschrieben).

Was soll das bringen? 2^1000 kannst du direkt hinschreiben, das ist eine 1 mit 1000 Nullen. Das schwierige ist das Berechnen der Quersumme in Dezimaldarstellung.

Mit der schnellen Exponentiation kannst du auch im Dezimalsystem schnell Potenzieren. Wenn du die Zahl berechnet hast musst du nur noch die einzelnen Stellen aufsummieren.

(Korrigiere mich, wenn ich da falsch liege).

Bashar

Schnelle Exponentiation ist die Rekursion a^2n = (aⁿ⁾2, a^2n+1 = a*a^2n, a^0 = 1, richtig? Geht denn das Multiplizieren im Dezimalsystem schneller als die Zahl 2^1000 vom Binär- ins Dezimalsystem umzurechnen?

icarus2

Bashar schrieb:

Schnelle Exponentiation ist die Rekursion a^2n = (aⁿ⁾2, a^2n+1 = a*a^2n, a^0 = 1, richtig? Geht denn das Multiplizieren im Dezimalsystem schneller als die Zahl 2^1000 vom Binär- ins Dezimalsystem umzurechnen?

Keine Ahnung. Aber wenn du mich so fragst schätze ich mal, dass das nicht schneller ist.

SeppJ

Ist das Umrechnen von 2^1000 nach Dezimal nicht äquivalent zur Berechnung von 2^1000 im Dezimalsystem? Was würdest du denn anders machen?

Bashar

Bei dem einen rechne ich im Binärsystem: Ich fange mit 2^1000 an und teile durch 10 bis ich bei 0 angekommen bin, merke mir dabei die anfallenden Reste. Bei dem anderen rechne ich im Dezimalsystem, und führe gemäß der schnellen Exponentiation Multiplikationen durch, bis ich bei 2^1000 bin.

icarus2

Bashar schrieb:

Bei dem einen rechne ich im Binärsystem: Ich fange mit 2^1000 an und teile durch 10 bis ich bei 0 angekommen bin, merke mir dabei die anfallenden Reste. Bei dem anderen rechne ich im Dezimalsystem, und führe gemäß der schnellen Exponentiation Multiplikationen durch, bis ich bei 2^1000 bin.

Bei der schnellen Exponentiation braucht man aber (wenn ich mir nichts falschens überlege) nur logarithmisch viele Multiplikationen. Da braucht man beim Umrechnen von binär zu dezimal doch mehr?

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

> (expt 2 1000)
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Und diese Ziffern wollt ihr addieren. Ob es sich wirklich lohnt, dafür grossartige Analysen anzustellen? Wahrscheinlich nicht, besonders wenn man bedenkt, wie viele Bignum-freundliche Aufgaben dort noch auftauchen werden.

Bashar

µ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.

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.