Datentyp problem

[titus2000]

Moin moin,

es geht darum, die kleinste Lösung einer Gleichung zu finden.
Im Prinzip macht das Programm das auch, jedoch werden auch Lösungen ausgegeben, die nicht stimmen, da Python nicht genügend Nachkommastellen berücksichtigt.
Das Programm ist sehr simpel, jedoch weiß ich nicht, welchen Datentyp ich nutzen sollte und wie ich den einfüge. Das Pythongiude hat mir nicht geholfen. Ich habe grade erst angefangen Python zu lernen.
Ziel des Algorithmus ist die Gleichung durch Ganzzahlen zu lösen.

x²-61y²=1

Code: Alles auswählen

from math import*
for x in range(1,10000000000000):
    if sqrt(((x*x-1)/61))==int(sqrt((x*x-1)/61)):
        print(x)

Code: Alles auswählen

>>> 
29718.0
335159612.0
425680601.0
516201590.0
579798235.0
670319224.0
760840213.0
824436858.0
851361202.0
914957847.0
1005478836.0
1032403180.0
1095999825.0
1122924169.0
1132672126.0
1159596470.0
1186520814.0
1223193115.0
1250117459.0
1277041803.0
1340638448.0
1367562792.0
1404235093.0
1431159437.0
1494756082.0
1521680426.0
1548604770.0
1585277071.0
1612201415.0
1648873716.0
1675798060.0
1702722404.0
1766319049.0

Hier stellt die letzte Zahl die richtige Lösung dar. Alle anderen sind aber einer bestimmten Nachkommastelle falsch.

Ich bin für jede Hilfe dankbar

Lg Alex

[Tom_H]

es geht darum, die kleinste Lösung einer Gleichung zu finden.
...
Ziel des Algorithmus ist die Gleichung durch Ganzzahlen zu lösen.
x²-61y²=1

Ähhh wozu braucht man da ein Programm?
x = 1, y = 0

mfg, Tom

P.S.: Damit Dein Progrämmchen funktioniert, solltest Du 61.0 statt 61 schreiben - sonst rechnet Python die Division mit Ganzzahlen.

[Hyperion]

P.S.: Damit Dein Progrämmchen funktioniert, solltest Du 61.0 statt 61 schreiben - sonst rechnet Python die Division mit Ganzzahlen.

Python3 nicht - und augenscheinlich nutzt der OP das.

[webspider]

Kanns sein, dass die vorgenommene Rechnung nicht passt? Allein dass die Gleichung x und y als Variablen nutzt, hier aber nur eine der beiden Variablen durchprobiert wird, macht mich stutzig.

[BlackJack]

@webspider: Der Python-Code enthält nicht die Formel sondern das was da nach `y` aufgelöst heraus kommt. Also zumindest den einen Teil davon.

[titus2000]

Kanns sein, dass die vorgenommene Rechnung nicht passt? Allein dass die Gleichung x und y als Variablen nutzt, hier aber nur eine der beiden Variablen durchprobiert wird, macht mich stutzig.

Das Programm tut genau das was es soll. Ziel ist es y zu erhalten. Dies mache ich jedoch nciht über eine Gleichsetzung, denn für x weiß ich, dass es ganzzahlig sein muss, also y-int(y)=0 sein muss.

es geht darum, die kleinste Lösung einer Gleichung zu finden.
...
Ziel des Algorithmus ist die Gleichung durch Ganzzahlen zu lösen.
x²-61y²=1

Ähhh wozu braucht man da ein Programm?
x = 1, y = 0

mfg, Tom

P.S.: Damit Dein Progrämmchen funktioniert, solltest Du 61.0 statt 61 schreiben - sonst rechnet Python die Division mit Ganzzahlen.

Die triviale lösung (1,0) ist für mich uninteressant. Ich will nur den richtigen Datentyp wählen, damit die unnötigen Lösungen nicht erscheinen.
Die letzte Zahl in meinem Shell-Auszug stellt die gewünschte dar.

Lg Alex

[anogayales]

Hilft hier vielleicht das http://docs.python.org/library/decimal.html decimal Modul?

Mit Ungenauigkeiten in der Auflösung deiner Zahlen wirst du immer kämpfen müssen. Normalerweise definiert man sich ein Epsilon, dass einem dabei hilf auf Gleichheit bei Gleitkommazahlen zu überprüfen:

Code: Alles auswählen

if math.fabs(y-int(y)) <= 10**-20:
    # found solution

Grüße,
anogayales

[titus2000]

Ich habe das Programm etwas umgeschrieben, damit es schneller arbeitet. Das Rundungsproblem bleibt jedoch erhaltn. Die Rechnung ist nur auf 8 Nachkommastellen genau. Ich bräuchte theoretisch eine mit unendlich vielen Nachkommastellen, um sicher zu gehen, dass tatsächlich eine Ganzzahl vorliegt. Wie erweitere ich denn meine Zahl so, dass sie die richtigen Werte ausgibt. Kennt ihr eine andere Programmiersprache, die mit solchen Problemen besser umgehen kann?

Neuer Code:

Code: Alles auswählen

from math import*
from decimal import*

for y in range(1,10000000000000):
    x=sqrt(61*y*y+1)            
    if fabs(x-int(x)) <= 10**-20:
        print(y)

Shell-Ausgabe:

Code: Alles auswählen

>>> 
42912791
54502816
66092841
74235557
85825582
97415607
105558323
109005632
117148348
128738373
132185682
140328398
143775707
145023805
148471114
151918423
156613830
160061139
163508448
171651164
175098473
179793880
183241189
191383905
194831214
198278523
202973930
206421239
211116646
214563955
218011264
226153980

Das letzte Ergebnis ist das eigentlich erwünschte.

Vielen Dank für eure Hilfen.

Lg Alex

[frabron]

Du solltest decimal auch nutzen, importieren alleine bringt nix. Hast du denn den Teil im Handbuch gelesen und verstanden, der sich mit Zahlen beschäftigt? Und nur so nebenbei (wenn du Decimal nicht nutzen willst): floats haben eine is_integer() - Methode. Das sollte dir dein "if fabs()" Konstrukt sparen und deutlich effizienter sein.

[titus2000]

Hey,

Wenn ich also meine Variable habe und
is_integer(y)
implementiere, dann gibt er einen boolschen Ausdruck, mit dem meine if Funktion arbeiten kann. Doch ist das ja eigentlich für mich 2. rangig.
gelesen habe ich den Teil, doch verstehen tu ichs nicht, da ich nicht sehe, wie man damit rechnet.

Ich habe mir gedacht, dass:
x=decimal(sqrt(61*y*y+1))
zu einem Ergebnis kommt, doch scheint dam nicht so zu sein. Ich blicke da nicht so ganz durch. Wär echt super, wenn ihr das für Einsteiger verständlich formulieren könntet. Dafür wäre ich euch sehr dankbar.

Viele Grüße
Alex

[EyDu]

Hallo.

Wenn du mit dem decimal-Modul rechnen willst, dann muss du die Zahlen natürlich auch entsprechend umwandeln. Wie das geht, ist in der Dokumentation beschrieben. Bei der besagten Zeile

Code: Alles auswählen

x=decimal(sqrt(61*y*y+1))

rechnest du mit y als float, ziehst die Quadratwurzel und probierst das Ergebnis dann in decimal zu wandeln. Das macht natürlich überhaupt keinen Sinn, da die gesamte Berechnung mittels weniger Nachkommastellen durchgeführt wird.

Eine andere Programmiersprache wird dir hier auch nicht weiterhelfen, da es sich um ein allgemeines mathematisches Problem handelt. Vielleicht solltes du noch einen Blick auf das fractions-Modul werfen. Damit kannst du, wenn deine Berechnungen wirklich so einfach sind, leicht heraufinden, ob es sich um eine Ganzzahl handelt oder nicht.

[frabron]

Ergänzend dazu noch vielleicht folgender Linkt: http://www.doughellmann.com/PyMOTW/numeric.html

[BlackJack]

@titus2000: Also ich würde das ja so umschreiben das ausschliesslich mit ganzen Zahlen gearbeitet wird. Alleine die `math.sqrt()`-Funktion mit einem sofortigem `int()` könnte man verwenden um sich das schreiben einer eigenen Wurzelfunktion zu sparen. Aber auch nur wenn sichergestellt ist, dass die Argumente nicht so gross werden können, dass dadurch wieder Ungenauigkeiten entstehen.

Das mit `is_integer()` hast Du anscheinend falsch verstanden: Da musst Du nichts implementieren, `float`-Objekte haben diese Methode schon. Damit sparst Du die unnötige zweite Rechnung.

Die Dokumentation zu `decimal` hast Du offensichtlich nicht gelesen. Der erste Abschnitt ist mit „Quick-start Tutorial“ überschrieben, und Du kannst mir nicht erzählen nach dessen Lektüre hättest Du gedacht das ein einfaches ``import decimal`` ausreicht um irgend etwas zu ändern.

[Tom_H]

...Das letzte Ergebnis ist das eigentlich erwünschte.

Die richtige (kleinste nichttriviale) Lösung lautet IMHO: x = 851361202, y= 109005632

Wie BlackJack schon anmerkte: Integer-Aufgaben löst man mit Integers.

Code: Alles auswählen

from math import sqrt

x = 1
search = True
while search:
    x += 1
    t = x * x - 1
    if (t % 61) == 0:
        if sqrt(t / 61).is_integer():
            print x, int(sqrt(t / 61))
            search = False

Die sqrt-Funktion aus der math-library ist (bei CPython unter Win64) so schnell, das "einfache" Umgehungsversuche eher langsamer werden.
Bei anderen Implementierungen könnte man hier ggf. noch zwei Sachen ändern:
- Test auf Quadratzahlen (nach Fermat) - das dürfte sich aber nur bei BCD-Mathematik lohnen, weil sonst die Maskiererei zuviel Zeit braucht.
- Integer-SQRT mit einem kleinen Newton und entsprechend frühem Abbruchkriterium.

mfg, Tom

[Hyperion]

Das sieht mir nach einem Fall für `itertools.count` aus. Damit kann man sich die Boolsche Variable und den manuellen Zähler sparen.

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