sehr große Zahlen [Project Euler 20]

[bembulak]

Hallo mitsammen!

Ich stecke hier fest und komme irgendwie nicht weiter. Ich hoffe, ihr könnt mir helfen.
Hintergrund: wann immer mir langweilig ist, oder besser: wenn ich nicht weiß, was ich programmieren soll, versuche ich mich an den Aufgaben bei Project Euler. Sobald ich die Sachen mal vom Englischen einigermaßen eingedeutscht habe, heißt es meist für mich: Schulbank drücken. Ich muss oft einige Stunden Wikipedia & Co. bemühen, bis ich die Fragestellung überhaupt verstanden habe (ich bin leider kein Akademiker und kenne deshalb of Begriffe wie Palindrom, Primfaktorzerlegung,... nicht). Ich erwarte auch nicht, dass es mit steigendem Schwierigkeitsgrad einfacher wird, aber zumindest kann ich dann sagen, dass ich etwas dazugelernt habe.

Nun zu meinem "Problem", von dem ich nicht weiß, WO ich anfangen soll.
http://projecteuler.net/index.php?secti ... lems&id=20" onclick="window.open(this.href);return false;
Der Aufgabentext lautet:

n! means n × (n − 1) × ... × 3 × 2 × 1

Find the sum of the digits in the number 100!

Also, kurz "gedacht": ich multipliziere die Zahlen 1..100 miteinander und das Ergebnis ist die gesuchte Zahl.
Mir kommt es allerdings so vor, als würde das eine sehr, sehr große Zahl werden. Auch weiß ich, dass diese Aufgabe schon viele vor mir in anderen Sprachen gelöst haben.
Ergo müssen die Leute wissen, wie man mit Zahlen rechnet, die größer sind, als die Standardtypen ihrer Umgebung (C, Java, C++, ASM,...). Ich bezweifle, dass diese Leute alle irgendwelche Zusatzbibliotheken nutzen. Nein, das kann ich einfach nicht glauben.

Deshalb meine Frage an euch:
wie rechnet man mit Werten, die Größer sind, als die Standardtypen eurer Umgebung?
Wenn ich meinen Dokumenten und Erinnerungen glauben schenken darf, so ist ein Int64 die größte Zahl, die ich erfassen kann,
was bei weitem nicht ausreichen kann, wenn ich mir das von 1..100 überlege.

Könnte ihr mir einen Tipp geben? Danke und schöne Grüße,

[Teekeks]

Eine Möglichkeit wäre es mit einem array of byte zu arbeiten und da dann immer in jedes Byte die jeweilige stelle der Zahl zu speichern.

[Targion]

Eine Möglichkeit wäre es mit einem array of byte zu arbeiten und da dann immer in jedes Byte die jeweilige stelle der Zahl zu speichern.

Habe ich zu meiner Delphi-zeit mal so gemacht, in Kombination mit überladenen Operatoren.
Das wäre zumindest eine Funktionierende Lösung.

[Euklid]

Hallo,

Eine Möglichkeit wäre es mit einem array of byte zu arbeiten und da dann immer in jedes Byte die jeweilige stelle der Zahl zu speichern.

genau diese Umsetzung gibt es schon: Die GNURZ-Arithmetik funktioniert wie von dir beschrieben mit Arrays, vgl. http://forge.lazarusforum.de/projects/show/gnurz" onclick="window.open(this.href);return false;

Bebulak: Es geht in diesem Fall nach meiner Meinung einfacher, als die Zahlen tatsächlich auszumultiplizieren:

http://de.wikipedia.org/wiki/Stirling-Formel" onclick="window.open(this.href);return false;

Der über die Stirling-Formel berechenbare Wert stimmt für große n relativ gut mit n! überein.

Viele Grüße, Alexander

[corpsman]

lol, also eigentlich sollstdu die Project euler aufgaben ja ohne Hilfe hinbekommen.

aber 100! ist ja nicht so groß, dass kann man noch von "Hand" mit Strings nach rechnen.

Mach dir einfach eine AddString und MulString. Dann geht das relativ Fix, ( Mul String kannst du z.b. mit meiner Vedischen Multiplikation demo machen,

Damn, nu hab ich ja doch geholfen...

[bembulak]

Eine Möglichkeit wäre es mit einem array of byte zu arbeiten und da dann immer in jedes Byte die jeweilige stelle der Zahl zu speichern.

Habe ich zu meiner Delphi-zeit mal so gemacht, in Kombination mit überladenen Operatoren.
Das wäre zumindest eine Funktionierende Lösung.

genau diese Umsetzung gibt es schon: Die GNURZ-Arithmetik funktioniert wie von dir beschrieben mit Arrays, vgl. http://forge.lazarusforum.de/projects/show/gnurz" onclick="window.open(this.href);return false;

Aha, danke. Jetzt habe ich wieder was dazugelernt!
Ich darf also annehmen, dass es in vielen Sprachen (und auch Libs) so gelöst wird, wenn es zu ominös großen Zahlen kommt?

Es geht in diesem Fall nach meiner Meinung einfacher, als die Zahlen tatsächlich auszumultiplizieren:
http://de.wikipedia.org/wiki/Stirling-Formel" onclick="window.open(this.href);return false;

Danke. Einfach finde ich diese Formel jedoch nicht - um ehrlich zu sein: ich verstehe kein Wort. Ich müsste für jedes Wort dieses Artikels wiederum 1-2 Wochen investieren, um die Grundlagen zu verstehen.

lol, also eigentlich sollstdu die Project euler aufgaben ja ohne Hilfe hinbekommen.

So lol-ig finde ich das gar nicht. Nicht jeder ist ein geborenes Mathegenie und möchte es dennoch lernen.
Zum Einen habe ich wie gesagt keinen akademischen Hintergrund (ja nicht mal "Abi") und die Beispiele übersteigen teilweise doch, was man bis zum 15. Lebensjahr so in der Schule lernt (und als Azubi lernt man davon auch nichts). Zum Anderen habe ich nicht um eine Lösung gebeten, sondern um einen Fingerzeig.

Damn, nu hab ich ja doch geholfen...

Na, dazu sind Foren doch da. Und es war ja keine vorgekaute Lösung, sondern ein Wink in welche Richtung ich mich bewegen könnte.

Danke für eure Zeit und die Tips. Ich werde mal sehen, in wie weit ich das hinbekomme.

[corpsman]

Übrigens hast du die frage von Projekt euler falsch verstanden.

Die wollen nicht die 100! haben, sondern die Quersumme davon :

als sei 100! = 1000000 dann wäre die Quersumme 1
sei 100! = 123345 dann wäre die Quersumme 1+2+3+3+4+5 = 18

[bembulak]

Die wollen nicht die 100! haben, sondern die Quersumme davon
als sei 100! = 1000000 dann wäre die Quersumme 1
sei 100! = 123345 dann wäre die Quersumme 1+2+3+3+4+5 = 18

Steht dieses ! für die Quersumme?
Hm, in der Aufgabenstellung steht aber doch n! means n × (n − 1) × ... × 3 × 2 × 1 und ich interpetiere das "x" als Multiplikationszeichen.
Also 1 * 2 * 3 * .... * 100
Aber ich lasse mich gerne eines Besseren belehren. Nur, wenn ich 1 + 2 + .... + 100 rechne, kommt zwar ein schön niedriger Wert raus, aber stimmen tut er trotzdem nicht (laut ProjectEuler).

[indianer-frank]

Das ist doch wohl so zu verstehen, daß die dezimale Quersumme gerechnet werden soll, also
für 4 ist 4! = 24 , QS = 6
und für 5: 5! = 120, QS = 3.

Code: Alles auswählen

(11:04) gp > 100!
%1 = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

QS=?

Ansonsten findet man zB bei Knuth und anderen eine einfache Formel für die Multiplizität einer Primzahl als Divisior in n!. Wegen 10 = 5*2 sollte man sollte man sich dabei auf die Multiplizität von 5 konzentrieren.

[corpsman]

um es nochmals deutlich zu machen, mein Beispiel war wohl zu abstrakt.

! ist der Mathematische Operator Fakultät, und bedeutet, alle zahlen bis runter zur 2 multiplizieren

also

4! = 2*3*4 = 24

Die Quersumme ist wie indianer-frank auch schon schreibt 24.

Und ich weis das Project Euler die Quersumme von 100! haben will, da ich das ja schließlich schon vor Ewigkeiten so berechnet hab

Du must also nur 2*3*4*5*...*100 machen, egal wie, ob nun mit Mathematischen Tricks oder nicht, und dann davon die Quersumme berechnen, der Wert ist übrigens erstaunlich gering ( zumindest im Vergleich zu 100! )

Projekt Euler ist es hierbei egal ob du das Effizient rechnest oder nicht, ich habe mir damals auch keine große mühe gemacht die Zahl besonders elegant zu berechnen, oder die Quersumme anders zu konstruieren. Ich hab schließlich auch calc
Generell bei den Project euler Aufgaben empfiehlt es sich aber eine Funktionale Programmiersprache zu nehmen, die lösen viele der Probleme schon ohne das man was machen mus .

So muss man in irgend einer Aufgabe die Primfaktor Zerlegung von ( n über k ) = Binomialkoeffizienten Berechnen, und da kommen für mittelgroße n schon sehr große Zahlen raus, bei genauerer Betrachtung reicht es aber nur die Primfaktoren von n zu testen, und so spart man sich gigantisch viel Rechenzeit. Haskal hat das automatisch erkannt und der source lief von Anfang an in unter 1 ms, die FPC variante musste erst speziel darauf hin optimiert werden ....

[bembulak]

! ist der Mathematische Operator Fakultät, und bedeutet, alle zahlen bis runter zur 2 multiplizieren

Ok, zumindest das habe ich verstanden. 6! = 2*3*4*5*6 = 720

4! = 2*3*4 = 24
Die Quersumme ist wie indianer-frank auch schon schreibt 24.

Du must also nur 2*3*4*5*...*100 machen
...
...
und dann davon die Quersumme berechnen

Ich dachte das Ergebnis von 2*3*....*100 wäre schon die Quersumme. Sorry, aber jetzt steh' ich erst recht auf der Leitung.

Aber, ich wiederhole hier noch mal, in der Hoffnung, dass mir der Knopf doch noch aufgeht:
! steht für Fakultät, ja?
6! wäre demnach 720, ja?
Und die Quersumme von 6! demnach 9, oder wie?
Wenn ich jetzt 100! habe, ist das IMHO ein sehr, sehr große zahl! Wenn ich von dieser Zahl jetzt wieder die Quersumme bilde, sollte ich das haben, was eigentlich gefordert ist?

[Euklid]

! steht für Fakultät, ja?
6! wäre demnach 720, ja?
Und die Quersumme von 6! demnach 9, oder wie?

genau!

[quoteWenn ich jetzt 100! habe, ist das IMHO ein sehr, sehr große zahl! Wenn ich von dieser Zahl jetzt wieder die Quersumme bilde, sollte ich das haben, was eigentlich gefordert ist?[/quote]

Ja, ich denke schon.

Viele Grüße, Euklid

[corpsman]

das hast du vollkommen richtig verstanden.

Als Tipp Speichere deine Zahl in einen String.

Wenn ich dir nun verrate das das Ergebniss <= 1000 ist, so weist du das die ein ganz normaler String Reicht, da ja das bedeutet das der String 10^1000 als maximalen wert haben kann. Und 100^100 hat gerade mal 200 Stellen, und ist definitiv obere Schranke für dein Problem.

Wenn du das dann in deinem String hast, kannst du einfach hergehen und in etwa so was machen :

Code: Alles auswählen

var i:Integer;
e:Integer;
zahlString:String;
begin
zahlstring := Berechne 100!
e := 0;
for i := 1 to length(zahlstring) do
e := e + ord(zahlstring[i])-49;
showmessage(inttostr(e));

[bembulak]

Danke an alle!
Ich habe jetzt den für mich entscheidenden Punkt erreicht:
ich habe das ganze Problem verstanden und muss es jetzt "nur" noch umsetzen,
was mir vergleichsweise einfach erscheint.