Datentyp problem

[BlackJack]

@Tom_H: `math.sqrt()` ist zwar schnell, führt aber leider zum falschen Ergebnis:

Code: Alles auswählen

In [488]: (851361202**2 - 1) % 61
Out[488]: 0L

In [489]: (851361202**2 - 1) / 61
Out[489]: 11882227807719423L

In [490]: math.sqrt((851361202**2 - 1) / 61)
Out[490]: 109005632.0

In [491]: decimal.Decimal((851361202**2 - 1) / 61).sqrt()
Out[491]: Decimal('109005631.9999999954130810415')

In [492]: int(_490)**2
Out[492]: 11882227807719424L

In [493]: int(_490)**2 == _489
Out[493]: False

Die 1766319049 von titus2000 sind schon das richtige Ergebnis.

Nachtrag: Mir fiel gerade auf, dass hier schon die Umwandlung in `float()` das Problem ist:

Code: Alles auswählen

In [499]: (851361202 ** 2 - 1) / 61
Out[499]: 11882227807719423L

In [500]: float((851361202 ** 2 - 1) / 61)
Out[500]: 11882227807719424.0

In [501]: _499 == _500
Out[501]: False

[frabron]

Ich finde es bemerkenswert, wie wenig trivial Mathematik mit Python ist. Man muss doch imo erheblichen Aufwand betreiben, um das richtige Modul zu finden, damit man ein richtiges Ergebnis bekommt. Ausserdem ist es schade, dass zwischen dem math-Modul und dem Decimal Modul Funktionen doppelt definiert sind, und dass beide Module nicht besser miteinander harmonieren, zumal bei decimal ja längst nicht alle math Funktionen vorhanden sind:

Code: Alles auswählen

>>> import decimal
>>> import math
>>> d = decimal.Decimal((851361202**2 - 1) / 61)
>>> d
Decimal('11882227807719423')
>>> d.sqrt()
Decimal('109005631.9999999954130810415')
>>> math.sqrt(d)
109005632.0
>>> 

Hier wäre es ja wünschenswert, dass bei math.sqrt auch ein Decimal wieder rauskommt, stattdessen ist man auf die Methode der Decimalklasse angewiesen.

Vielleicht kann ja jemand das hier mit einem aktuellerem Python als meinem (2.6) probieren:

Code: Alles auswählen

>>> e = decimal.Decimal().from_float(math.sqrt(d))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'Decimal' object has no attribute 'from_float'

[cofi]

`Decimal.from_float` gibt es eben erst ab Python2.7.

Man beachte: Es ist eine staticmethod, keine Exemplarmethode.

"richtiges Ergebnis" ist eben sehr abhaengig von den Anforderungen. Dass Python standardmaessig zu den schnellen aber ungenauen FP greift, sollte aber klar sein, decimal ist halt um Groessenordnungen langsamer.

The following functions are provided by this module. Except when explicitly noted otherwise, all return values are floats.

Ich nehme mal an, dass der Grund ist, das Interface hier einheitlich zu halten. Irgendwo schade, andererseits könnte man sich genauso darueber aergern, wenn es anders waere ..

[BlackJack]

Das `math`-Modul ist aus historischen Gründen halt nur ein relativ dünner Wrapper um die ``math.h``-Funktionen aus C. Wenn die Funktionen im `math`-Modul auch für alle möglichen anderen Typen funktionieren müssten, würden sie langsamer werden. Und vielleicht auch nicht mehr so gut für PyPy optimierbar. Die Leute wissen ja im allgemeinen um die Grenzen von `float` und wenn sie den Typ verwenden, wollen sie schnell, und nicht unbedingt genau.

@frabron: Was versprichst Du Dir vom `from_float()`? Der „Schaden“ ist ja schon vor dem Aufruf dieser (statischen) Methode passiert. Ein falsches Ergebnis nachträglich in ein `Decimal` umwandeln bringt da nichts.

Letztlich sehe ich das nicht unbedingt als spezifisches Python-Problem, denn genau die gleichen Probleme hat man in den anderen gängigen Programmiersprachen auch. Normalerweise wird mit dem Gleitkommazahlenformat gerechnet das der Prozessor direkt versteht, denn das ist schön schnell. Wenn man mehr Genauigkeit haben möchte, muss man sich nach alternativen Datentypen umschauen. Wenn man Glück hat, dann bietet die Sprache etwas in ihrer Standardbibliothek.

[gkuhl]

Ich finde es bemerkenswert, wie wenig trivial Mathematik mit Python ist. Man muss doch imo erheblichen Aufwand betreiben, um das richtige Modul zu finden, damit man ein richtiges Ergebnis bekommt.

...die gleichen Probleme hat man in den anderen gängigen Programmiersprachen auch. [...] Wenn man mehr Genauigkeit haben möchte, muss man sich nach alternativen Datentypen umschauen.

Ich würde das eher unabhängig vom Computer betrachten. Rechnen mit reellen Zahlen kann immer dazu führen, dass man als Ergebnis irrationale Zahlen bekommt, die sich nicht mehr vollständig darstellen lassen. Selbst wenn du das Problem auf Papier lösen willst musst du dich entscheiden wie viele Kommastellen du mitnehmen willst.

[frabron]

Yup, ich wollte das Problem auch nicht auf Python reduzieren. Ich bin mir bewusst, dass das in anderen Sprachen auch so ähnlich ist. Bei meiner fast täglichen Arbeit mit Koordinaten komme ich auch prima mit den floats aus. Dennoch ist das eine Problematik, die imo für viele erst einmal nicht offensichtlich ist. Als ich meine Klasse für das Rechnen mit Gewichten geschrieben habe, musste ich letztendlich auch auf das Decimal Modul zurückgreifen. Das Umrechnen in die SI Basiseinheit hat da auch zu Rundungsfehlern mit den "normalen" Floats geführt, so dass Vergleiche nicht so einfach möglich waren.

[Tom_H]

@Tom_H: `math.sqrt()` ist zwar schnell, führt aber leider zum falschen Ergebnis:

Na gut - dann eben zu Fuß (super-einfachst-Version mit Newton) ....
Das war wahrscheinlich auch der eigentliche Inhalt der Aufgabe - die Schüler sollten mal "etwas zum Kauen" bekommen.

Code: Alles auswählen

x = 1
while True:
    x += 1
    temp = x * x - 1
    if (temp % 61) == 0:
        temp = temp / 61
        yap1 = temp / 2.0
        while True:
            yap2 = (yap1 + temp / yap1) / 2.0
            if (yap1 - yap2) < 0.8:
                break
            yap1 = yap2
        y = int(yap2)
        if y * y == temp:
            print x, y
            break

>> 1766319049 226153980

mfg, Tom

[Hyperion]

Rettet nicht viel, aber ein wenig

Code: Alles auswählen

for x in itertools.count(2):
    temp = x * x - 1
    # usw...

Außerdem regt es problembaer auf

[titus2000]

Moin moin,

Ich trau mich kaum zu fragen, wenn das schon so super einfach ist, doch erschließt sich mir der Sinn von yap1 und yap 2 nicht. Ist das das Newtonverfahren. Ich kenne das nur aus der Analysis. Wäre klasse,w enn du mir den Code erklären könntest, ich werkel schon länger an dem decimal-Modul rum, doch ist das aber ner gewissen Nachkommastelle nicht mehr genau.

Lg Alex

[Tom_H]

Ich trau mich kaum zu fragen, wenn das schon so super einfach ist, doch erschließt sich mir der Sinn von yap1 und yap 2 nicht. Ist das das Newtonverfahren.

Genau das isser - wobei der hier zum Zweizeiler verkommt.
gesucht: y = sqrt(t) das ist gleichbedeutend mit: y² = t oder: y² - t = 0
Man muß also die Nullstellen von y² - t suchen.
Ver-Newtoned gibt das: yn+1 = (yn + t / yn) / 2

Für n=1: yapprox_2 = (yapprox_1 + t / yapprox_1) / 2
Jetzt machst Du noch aus yapprox_2 die Kurzform yap2 und "recyclest" in der Schleife die Indizes: ~1 ist immer der alte und ~2 ist immer der neue Wert
...damit sollte es lesbar sein.

Beim Abbruchkriterium "(yap1 - yap2) < 0.8" hätte ich auch 1.0 hinschreiben können. 0.8 schien mir im Sinne von Rechenfehlern sicherer. So eine einfache Parabel konvergiert auch so schön schnell und Narrensicher, daß das wurscht ist.
Wichtig ist noch, daß der Startwert rechts von der Nullstelle liegt. Damit werden die Näherungswerte stetig fallend und man kann auf Vorzeichenspiele und Fallunterscheidungen verzichten.

mfg, Tom

[anogayales]

Ich kenn das ganze als Heron-Verfahren: http://de.wikipedia.org/wiki/Heron-Verfahren
Ein Spezialfall vom Newton-Verfahren.

Grüße,
anogayales