Float in Int abbilden

[spongebob.squarepants]

Danke für den Einwurf, aber das habe ich schon abgehakt.

Zurück zur herondemo: Nach Korrektur von add und sub konvergiert der Algorithmus nun endlich, und zwar schon im vierten Schritt.

4.00000018584

Das Problem: Wenn der bis 10 durchläuft, sind die Zähler und Nenner so gross, dass kein Mensch die mehr verarbeiten kann. Die Frage ist nun, welches geeignete Abbruchkriterium man nun einbauen könnte, welches solche Riesenzahlen verhindert.... Einfach nur "Stellen zählen"?

Grüsse

[BlackJack]

@str1442: Und das hast Du wirklich auf einem Python 1.5 laufen lassen!? Glaub ich irgendwie nicht.

[spongebob.squarepants]

So, ich habe den Heron jetzt geknickt (wird zu fett) und bin auf binary search zurück. Das funktioniert. Hier der Code.

Code: Alles auswählen

def sqrt(x):
	a = Fraction(0)
	b = x
	for i in range(30):
		c = (a+b)/Fraction(2)
		if c*c > x:
			b=c
		else:
			a=c
#		print c
	return c

Genauigkeit ist nicht so gut wie bei Heron und er konvergiert auch langsamer. Aber die Zahlen werden nicht so monströs...

[EyDu]

Die Frage ist nun, welches geeignete Abbruchkriterium man nun einbauen könnte, welches solche Riesenzahlen verhindert.... Einfach nur "Stellen zählen"?

Hast du es mal mit dem Shiften aller Nenner und Zähler versucht, wenn eine Zahl zu groß wird?

Oder mutig abbrechen wenn Nenner oder Zähler größer wird als 2**x. Dann sparst du dir das zählen.

[numerix]

Zurück zur herondemo: Nach Korrektur von add und sub konvergiert der Algorithmus nun endlich, und zwar schon im vierten Schritt.

4.00000018584

Das Problem: Wenn der bis 10 durchläuft, sind die Zähler und Nenner so gross, dass kein Mensch die mehr verarbeiten kann. Die Frage ist nun, welches geeignete Abbruchkriterium man nun einbauen könnte, welches solche Riesenzahlen verhindert.... Einfach nur "Stellen zählen"?

So lange du long's verfügbar hast, ist es ziemlich egal, ob du 20 stellige oder 1000 stellige Ganzzahlen hast (die Berechnungen werden dann nur etwas langsamer); hast du keine long's, dann sind auch 20 Stellen schon zu viel.

Ein zwangsweises Abbruchkriterium wäre das, was EyDu vorgeschlagen hat: Mit maxint vergleichen (bzw. vor dem Quadrieren o.ä. mit dessen Wurzel) und aufhören, wenn es nicht reicht. Aber 6 Nkst lassen sich damit gewiss (aber nicht getestet) nicht erreichen.

Aber ist ja nun auch egal, nachdem du den Heron zu Grabe getragen hast.

[spongebob.squarepants]

Nein, so richtig abgeschrieben habe ich Heron noch nicht. Ich kriege bloss die "Monsterzahlen" nicht in den Griff.

Grüsse

[numerix]

Nein, so richtig abgeschrieben habe ich Heron noch nicht. Ich kriege bloss die "Monsterzahlen" nicht in den Griff.

Geht es dir jetzt um die Problematik des nicht verfügbaren long-Datentyps oder macht es für dich einen (problemschaffenden) Unterschied, ob Zähler/Nenner eines Bruchs 20 oder 500 Dezimalstellen haben? Falls letzteres der Fall ist: Wo ist das Problem?

[spongebob.squarepants]

Letzteres. Es sind nämlich nicht 500, sondern 50000 Schlicht und einfach kommt der Algorithmus nicht bis zur 10. Iteration, weil er vorher im Nirvana versackt (dauert Stunden). Und was rauskommt, ist nicht zu gebrauchen, weil keiner "teilt" das noch...

[numerix]

Letzteres. Es sind nämlich nicht 500, sondern 50000 Schlicht und einfach kommt der Algorithmus nicht bis zur 10. Iteration, weil er vorher im Nirvana versackt (dauert Stunden).

Darauf hatte ich in einem früheren Post schon einmal hingewiesen: Das Problem ist ab einem bestimmten Punkt die Rechenzeit. Aber das lässt sich ja dadurch beheben, dass du eben nicht 10 Iterationen machst, sondern z.B. nur 5. Danach kannst du prüfen, wie genau dein Ergebnis ist und ggf. mittels Bisektion an der 5./6. Nachkommastelle noch ein bisschen feilen. Oder eben noch eine 6. Iteration anhängen. Das sollte dann in jedem Fall für 6 Nkst. ausreichen.

Und was rauskommt, ist nicht zu gebrauchen, weil keiner "teilt" das noch...

Das kommt ganz darauf an, wie man es anstellt: https://www.spoj.pl/ranks/SQRT2/lang=PYTH

[spongebob.squarepants]

Danke. Aber ich bleibe erst mal bei binary search...

Möglicherweise gibt es noch eine andere Variante: Ich habe eine Uralt-Version von Decimal.py (0.0. gefunden, der leider noch das DIV fehlt. Alles andere konnte ich ersetzen, so dass das Dingens jetzt wirklich auf einer komplett unfähigen 1.5.2 läuft.

Das löst aber nicht mein SQRT Problem, wollte es nur mal anmerken.

[spongebob.squarepants]

Hallo Freunde,

um die Sache mal versöhnlich abzuschliessen: Ich bin jetzt mal weg von den rationalen Brüchen und habe eine gefundene FixedPoint.py Version "entkernt" und unter 1.5.2 zum Laufen gebracht. Und - auch der Heron sprengt jetzt nicht mehr sämtliche Grenzen.

Anbei das Modul. Da gibt es sicher noch zu optimieren, aber es scheint erst mal zu funktionieren. Für evtl. Nachnutzer.

http://paste.pocoo.org/show/119227/

Und: Der Chip/das Modul unterstützt long, so dass ich ziemlich aus dem Schneider bin. Vielen Dank für die freundliche und kompetente Hilfe. Werde gerne hierher zurückkommen bei weiteren Problemen.

Grüsse

[numerix]

Hallo Freunde,

um die Sache mal versöhnlich abzuschliessen: Ich bin jetzt mal weg von den rationalen Brüchen und habe eine gefundene FixedPoint.py Version "entkernt" und unter 1.5.2 zum Laufen gebracht. Und - auch der Heron sprengt jetzt nicht mehr sämtliche Grenzen.

Anbei das Modul. Da gibt es sicher noch zu optimieren, aber es scheint erst mal zu funktionieren. Für evtl. Nachnutzer.

http://paste.pocoo.org/show/119227/

Und: Der Chip/das Modul unterstützt long, so dass ich ziemlich aus dem Schneider bin. Vielen Dank für die freundliche und kompetente Hilfe. Werde gerne hierher zurückkommen bei weiteren Problemen.

Grüsse

Freut mich, dass du dein Ziel erreicht hast. Hätte ich nach den zahlreichen Problemen mit den long's eigentlich nicht mehr erwartet.

Das Modul, das du da aufgetrieben hast, ist vermutlich eine Vorstufe des jetzigen decimal-Moduls - sieht man sich Autor und Datum an, dann passt das ganz gut.

[spongebob.squarepants]

Ja, nach Bekunden des Autors von Decimal, der Fixedpoint archiviert hat, ist "Fixedpoint nahezu vollständig in Decimal aufgegangen".

Ich hatte zunächst auch einen Port von Decimal probiert, aber recht schnell aufgegeben: Zuviele neuere syntaktische Konstrukte, die nur mühsam auf 1.5.2 zurückzubringen waren. Bin ganz zufrieden mit der Lib, obwohl die für Euch bestimmt amateurhaft aussieht

Grüsse