Float in Int abbilden

[BlackJack]

@spongebob.squarepants: Hey, *mein* Code war an der Stelle korrekt! Den hast *Du* kaputtgespielt als Du das ``/=`` ersetzt hast.

[spongebob.squarepants]

Ooooopppps Dann nehme ich alles zurück Sorry...
Mein Code, Dein Code - Code ist für alle da

Danke Euch für Eure Hilfe. Als Py-Newbie lerne ich so Einiges hier. Senile Konfusionen nicht ausgeschlossen dabei...

Grüsse

[numerix]

Mir ist immer noch nicht klar, ob deine letztendlich verwendete Python-Spezialversion in irgendeiner Form mit long's umgehen kann oder nicht.

Falls nicht, dann kannst du die ganze Sache IMHO vergessen, weil die Zähler und Nenner der benötigten Brüche unvermeidbar groß werden, wenn du am Ende wenigstens eine paar Nachkommastellen an Genauigkeit sicherstellen willst.

[spongebob.squarepants]

Ja, das befürchte ich leider auch und leider ist mir das auch noch nicht klar. Lt. Spec wird LONG ebenso nicht unterstützt, so dass LONGs wahrscheinlich nicht grösser als unsigned 32bit Int. Damit ist wirklich kein Staat zu machen...

Gerade kämpfe ich wieder mit den bekannten

Traceback (innermost last):
File "G:\test\lib.py", line 83, in ?
print heron(Fraction(1024,1))
File "G:\test\lib.py", line 76, in heron
p_n = (p + (x / p)) / c
File "G:\test\lib.py", line 27, in __add__
return Fraction(self.nominator * other.nominator
OverflowError: integer multiplication

...

[numerix]

Gerade kämpfe ich wieder mit den bekannten

Traceback (innermost last):
File "G:\test\lib.py", line 83, in ?
print heron(Fraction(1024,1))
File "G:\test\lib.py", line 76, in heron
p_n = (p + (x / p)) / c
File "G:\test\lib.py", line 27, in __add__
return Fraction(self.nominator * other.nominator
OverflowError: integer multiplication

...

Wenn es keine Unterstützung für long's gibt, kannst du das Kämpfen aufgeben.

[spongebob.squarepants]

Und schon wieder ein Problem...

Code: Alles auswählen

def heron(x, n = 10):
	c = Fraction(1, 2)
# 	c = 0.5
 	p = x * c

	if x <= 0:
		return None

	while 1:
		if n == 0:
			break
		p_n = (p + (x / p)) * c
		if p_n == p:
			break
		p = p_n 
		n = n-1
	return p

Dies ist mein sicher suboptimaler, aber zunächst mal funktionierender Heron. Der auskommentierte Teil oben ist für die float Version, die es tut (anstelle dessen ist dann der c = Fraction... Teil zu kommentieren)

Die relativ leichte und überschaubare Aufgabe

print heron(Fraction(16,1))

führt zu:

Traceback (innermost last):
File "G:\test\lib.py", line 84, in ?
print heron(Fraction(16,1))
File "G:\test\lib.py", line 77, in heron
p_n = (p + (x / p)) * c
File "G:\test\lib.py", line 27, in __add__
return Fraction(self.nominator * other.nominator
OverflowError: integer multiplication

&%"&§%"§/!"§$§ !!!

[spongebob.squarepants]

Wenn es keine Unterstützung für long's gibt, kannst du das Kämpfen aufgeben.

Hmm. Zumindest die PC Version kann durchaus mit longs umgehen. So bringt

print long(1024)*1024*1024*1024

1099511627776

Ich habe jetzt mal für nominator und denominator einen long cast eingebaut und zumindest in der PC Version bleiben jetzt die Overflows aus. Was natürlich nichts über die Fähigkeiten des Chips sagt.

Trotzdem rechnet der Heron (s.o.) "Kagge" mit Fractions. Für Wurzel 16 kommt 768240/86329 raus...

[spongebob.squarepants]

Sehr merkwürdig... Der Heron konvergiert nicht mit den Fractions. Es entstehen unglaublich grosse Werte für Nominator und Denominator und die Operationen dauern ewig und 3 Tage. Ebenso der Newton.

Ich glaube, ich muss auf das schriftliche Verfahren zurückgreifen, was wirklich übelster Kleinkack-Programmier-Sch... ist...

[EyDu]

Wie sieht es mit einer binären Suche für die Wurzel aus? Das sollte sich relativ leicht implementieren lassen und besonders (rechen-)aufwendig ist das Verfahren auch nicht.

Die longs könntest du versuchen zu sparen, indem du sowohl Zähler und Nenner, wenn deren Werte "zu groß" werden, um x Bits nach rechts shiftests. Man müsste allerdings überprüfen, wie sich das dann auf die Genauigkeit und die Konvergenz auswirkt.

[numerix]

Das Heron-Verfahren ist definitiv der richtige Weg - man muss es nur richtig implementieren und schwer ist das nicht. Die geometrische Idee habe ich in einem früheren Beitrag ja schon geschildert. Als kleine Demo mit echten floats (ein bisschen Arbeit muss ja noch bleiben ...):

Code: Alles auswählen

def herondemo(x):    
    a = 0.5 * x # 1. Rechteckseite (= Startwert)
    for n in range(10):
        b = x / a # 2. Rechteckseite
        a = 0.5 * (a+b) # neuer Wert 1. Rechteckseite usw.
        print a

herondemo(16)

Ein Ablauf zeigt auch sehr deutlich die hohe Konvergenzgeschwindigkeit - 10 Iterationen sind für 6 Nkst. überhaupt nicht nötig, wenn der Startwert nicht völlig daneben liegt.

Aber wie gesagt: Wenn es mit den long's nicht klappt, dann wird es mit dem Heron nichts.

[spongebob.squarepants]

Nun, das ist (nicht so elegant) exakt auch "mein" Algorithmus. Und bei float konvergiert der ja auch. Nur nicht mit den Fractions zunächst mal...

[spongebob.squarepants]

Wie sieht es mit einer binären Suche für die Wurzel aus? Das sollte sich relativ leicht implementieren lassen und besonders (rechen-)aufwendig ist das Verfahren auch nicht.

Die longs könntest du versuchen zu sparen, indem du sowohl Zähler und Nenner, wenn deren Werte "zu groß" werden, um x Bits nach rechts shiftests. Man müsste allerdings überprüfen, wie sich das dann auf die Genauigkeit und die Konvergenz auswirkt.

Binary Search und Newton - ok für Floats. Ich bekomm's nur nicht mit diesen Rationals hin... Zu blöd...

[spongebob.squarepants]

herondemo übertragen auf die Fractions:

Code: Alles auswählen

def herondemo(x):  
	a = Fraction(1,2) * x # 1. Rechteckseite (= Startwert) 
	for n in range(10): 
		b = x / a # 2. Rechteckseite 
		a = Fraction(1,2) * (a+b) # neuer Wert 1. Rechteckseite usw. 
		print a 
	return a

print herondemo(Fraction(16,1))

gibt folgende Sequenz:


9/1
80/9
89/10
792/89
881/99
7840/881
8721/980
77608/8721
86329/9701
768240/86329
768240/86329

Gut, er konvergiert. Aber Wurzel(16) = 8,8...? Hmmmmnmm....

EDIT: Nonsens, weil add fehlerhaft war (s. nächstes Posting)

[spongebob.squarepants]

So, jetzt habe ich Blackjack doch erwischt:

@Blackjack: Schau Dir doch mal Zeile 28 [Edit: und 32] Deiner Source gaaaaanz genau an. Vielleicht gibts auch bei Dir ein Stofftier, das geduldig zuhört. Bei mir hat's geholfen

Und nun zu Herondemo: Nach Korrektur der add Funktion sieht der Algorithmus nach 4 Schritten so aus:

a: 8 1 b: 2 1 a+b: 10 1
a: 5 1 b: 16 5 a+b: 41 5
a: 41 10 b: 160 41 a+b: 3281 410
a: 3281 820 b: 13120 3281 a+b: 21523361 2690420
a: 21523361 5380840 b: 86093440 21523361 a+b: 926510094425921 115813761803240

Dargestellt jeweils Zähler und Nenner des entsprechenden Wertes, da die print Funktion wg. Overflow abkackt. Das Ganze nimmt in der Folge exorbitant grosse Werte an, die das Forum füllen würden, deswegen klemm ich mir das. Die Ausgabe erfolgt nach der Zeile b = x/a.

Ich bin noch beim Schauen, was das sein soll....

[str1442]

Was ich gerne erreichen würde, ist die sofortige Zuweisung eines Tupels bei

huhu = numerix("1.2345")

Das geht nicht

Gehen tut das schon:

Code: Alles auswählen

In [4]: class M(type):
    def __call__(cls, *args, **kwargs):
        erg = super(M, cls).__call__(*args, **kwargs)
        return erg.to_tuple()
   ...:     
   ...:     

In [8]: class A(object):
    __metaclass__ = M
    def __init__(self):
        self.a, self.b = 42, 14
    def to_tuple(self):
        return (self.a, self.b)
   ....:     
   ....:     

In [14]: a = A()

In [15]: print a
(42, 14)

In [16]: print type(a)
<type 'tuple'>

Aber das will man wirklich nicht .

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