e auf 1000 Stellen berechnen

[lenzlein]

Hallo,
ich bin wirklich verzweifelt und ein absoluter Programmierlaie. Ich muss für einen Vortrag die Zahl e auf 1000 Stellen berechnen. Ich weiß, dass es hierzu schon ein Thema gab und auch eine Lösung http://www.python-forum.de/viewtopic.ph ... hl#p138542
Aber ich brauch für den Vortrag ein schlüssiges Programm, in dem man den Prozess sehen kann.
Ich habe bereits ein Programm von Basic, wo man den Anfang auf Python übertragen kann, aber den Rest kann ich nicht korrekt übersetzen:

Code: Alles auswählen

n=input('n=')
e=1.0
while n>0:
    e=1+(e/n)
    n=n-1
print e

Das ist ja relativ klar, da ich hier nur den Grenzwert von e nutze. Mein Problem ist, dass Python ja nun nicht nur 12 Stellen oder so rausgeben soll, sondern 1000. Im Basic sieht es folgendermaßen aus:

Code: Alles auswählen

DIM X (52)
FOR I=0 TO 52 X(I)=0
B=1E+5; X(0)=1
FOR N=144 TO 1 STEP -1
   FOR N=144 TO 1 STEP -1
       Q=INT(X(I)/N); R=X(I)-Q*N
       X(I)=Q; X(I+1)=X(I+1)*B*R
   NEXT I
   X(0)=X(0)+1
NEXT N
X(50)=X(50)+INT(X(51)/B+0.5)
FOR I=50 TO 1 STEP -1
   U=INT(X(I)/B); X(I)=X(I)-B*U; X(I-1)=X(I-1)+U
NEXT I
FOR I=0 TO 50 PRINT X(I);
END

Nun habe ich mich im Übersetzen versucht und es total vermasselt:

Code: Alles auswählen

x=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
for i in range(0,52,1):
    x[i]=0
b=1E+5
x[0]=1
for n in range(144,1,-1):
    for i in range(0,51,1):
        q=int(x[i]/n)
        r=x[i]-q*n
        x[i]=q
        x[i+1]=x[i+1]+b*r
    x[0]=x[0]+1
x[50]=x[50]+int(x[51]/b+0,5)
for i in range(50,0,-1):
    u=int(x[i]/b)
    x[i]=x[i]-b*u
    x[i-1]=x[i-1]+u

print x[i]

Bitte helft mir! Wie kann ich mein Programm umschreiben, damit ich meine gewünschten 1000 Stellen bekomme. Oder gibt es noch einen besseren Weg? Vielen Dank schonmal im Voraus.
Lg lenzlein

[numerix]

Pfui, sieht das gruselig aus!

Der von dir verlinkte Thread sollte eigentlich weiterhelfen. Dort kannst du sehen, wie man mit dem decimal-Modul arbeitet, mehr findest du in der Dokumentation der stdlib. Die Berechnung machst du dann am günstigsten über die Reihenentwicklung. Das ganze ist in weniger als 10 Zeilen erledigt.

[BlackJack]

@lenzlein: Der BASIC-Quelltext scheint mir fehlerhaft zu sein. Und die "Übersetzung" nach Python weist an den Stellen auch einige Unterschiede auf, die darauf hindeuten, dass der BASIC-Quelltext den Du da hast anders aussieht als der den Du uns zeigst. Ausserdem sieht's so aus, als wenn der Code nur 50 Stellen ausrechnen!?

[lenzlein]

also ich habe den Basic-Text aus meiner Quelle übernommen, der müsste so stimmen...Er berechnet zwar keine 1000 aber 250 Stellen...Das der von mir ins Python übersetzte Text nicht stimmt, ist klar, weil ich das irgendwie nicht hinbekommen habe. Wie funktioniert das mit der Reihenentwicklung? Ich weiß mit all dem nicht so viel anzufangen. LG lenzlein

[numerix]

Wie funktioniert das mit der Reihenentwicklung? Ich weiß mit all dem nicht so viel anzufangen. LG lenzlein

http://de.wikipedia.org/wiki/Eulersche_Zahl

[sma]

Der BASIC-Quelltext kann nicht stimmen, denn da ist 2x eine "FOR N" Schleife, die einmal mit "NEXT I" beendet wird. In dem Python Programm steht dort dann auch ein "for i". Und das ist nicht die einzige Abweichung von BASIC- und Python-Quelltext. Einmal sehe ich "*B*R" und einmal "+b*r". Außerdem ist im Python-Quelltext noch mindestens ein Fehler "0,5" statt "0.5".

Ich meine mich übrigens zu erinnern, dass ein "DIM X(N)" Platz für N+1 Elemente schafft, in Python müsste man also 53 und nicht 52 Elemente in x reservieren. Da ich das nicht abzählen werde, empfehle ich, da sowieso "[0] * 53" zu schreiben. Das "int(...)" nach einer Division mit "/" lässt sich in Python auch kürzer als Ganzzahldivision mit // schreiben (außer, wo das mit 0.5 gerundet werden soll, da sollte man dann "round()" benutzen.

Ob der Algorithmus stimmt, habe ich mir nicht angeschaut, das ist nicht mein Fachgebiet.

Der Simpel-Algorithmus wäre aber dieser, wobei man jetzt sicherlich nachdenken kann, wie viele Fakultäten man denn aufeinander addieren muss, um auf die richtige Stellenzahl zu kommen. 1000 ist garantiert zu viel, aber es ging auch so schnell genug

Code: Alles auswählen

import decimal
decimal.getcontext().prec = 1000

e = decimal.Decimal(1)
f = decimal.Decimal(1)
for k in range(1, 1000):
    f *= k
    e += 1 / f
print(e)

Stefan

[numerix]

1000 ist garantiert zu viel

450.

[lenzlein]

also das im Basic Programm mit dem N und dem I ist korrekt übernommen und das ist aus einem Buch...also weiß ich nicht was daran falsch ist...mit dem *b*R hast du Recht. Das habe ich falsch notiert, es ist +B*R. Das mit der 0.5 hab ich geändert und den Rest auch...eigentlich sollten dann 250 Stellen rauskommen aber das passiert bei mir nicht
@Stefan: Kannst du mir vielleicht dein Programm kurz erklären. Also den Hintergrund. Wäre voll lieb!
LG lenzlein

[sma]

Ich habe einfach die Formel für e, die Summe der Kehrwerte der Fakultäten von 1 bis N, mit Hilfe des Datentyps decimal implementiert. Der hat im Gegensatz zu Pythons "normalem" Fließkommadatentyp eine einstellbare Genauigkeit. Und da habe ich 1000 Stellen gewählt.

Hier ist noch mal der selbe Algorithmus ohne Division sondern mit Brüchen, was deutlich effizienter ist. Rationale Zahlen haben den Vorteil, dass sie exakt und dennoch effizienter als Dezimalzahlen vom Computer repräsentiert werden können. Das Ergebnis gebe ich dann als 1001-stellige Ganzzahl aus. Der Punkt nach der 2 kann man sich ja denken.

Code: Alles auswählen

from fractions import Fraction

e = Fraction(1)
f = 1
for k in range(1, 500):
    f *= k
    e += Fraction(1, f)
print(int(e * 10**1000))

In Python muss man sich jedenfalls nicht so quälen wie in Basic, weil es (wie in jeder vernünftigen Programmiersprache) Ganzzahlen beliebiger Genauigkeit und darauf basierend rationale Zahlen (Brüche) gibt.

Stefan

[Darii]

Mich würde interessieren, wie Blackjack in dem verlinkten Thread auf 0,18 Sekunden kommt.

@sma: Die Brüche sind in Python leider nicht so schön implementiert. Da das ganze in C implementiert ist, kann man nicht beliebige Datentypen in Zähler und Nenner reinschieben. Das scheitert selbst schon an `complex`(und complex selbst kommt mit Fraction nicht zurecht). Im Endeffekt darf man sich das wieder alles selbst implementieren.

[numerix]

Mich würde interessieren, wie Blackjack in dem verlinkten Thread auf 0,18 Sekunden kommt.

Brauchst halt die richtige Hardware ...

Ich vermute, er hat es nicht mittels Fraction gemacht, sondern die nötige Bruchrechnung selbst implementiert und nur mit ints gearbeitet. Damit geht das in nullkommanix.

[lenzlein]

vielen lieben Dank für die Hilfe!

[BlackJack]

@Darii: Wie numerix schon vermutet hat, habe ich nur mit ganzen Zahlen gearbeitet und die "Bruchrechnung" selbst implementiert. Die Anführungszeichen, weil ich keine Brüche als Objekte modelliert habe oder so; die Addition findet schon als Dezimalbruch statt.

Die eins über den Bruchstrichen wird dabei als 10^n dargestellt, wobei n von der Anzahl der gewünschten Nachkommastellen abhängt. Das Stichwort hier ist Fixpunktdarstellung.

Und was sich von Summand zu Summand verändert ist die Fakultät unter dem Bruchstrich um den jeweils nächsten Faktor. Die braucht man also nicht für jeden Summanden neu berechnen, sondern kann den Wert vom letzten Summanden als Ausgang nehmen.

Einen superfetten Rechner braucht man da also IMHO nicht, um so eine "Traumzeit" hinzubekommen. Ich habe bei meinem Prozessor jedenfalls mehr auf Energieeffizienz Wert gelegt als auf Rechenleistung.

Edit: Ich hab's gerade mal auf einem EeePC mit einem auf 630 Mhz getakteten Prozessor laufen lassen: 0.192 Sekunden.