math.sqrt() ungenau für große Zahlen?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Redprince
User
Beiträge: 128
Registriert: Freitag 22. Oktober 2004, 09:22
Wohnort: Salzgitter
Kontaktdaten:

Guten Abend!

Ich versuche mich seit geraumer Zeit am Problem #66. Ich habe zur Bestimmung des x-Wertes die Gleichung umgeformt:

Code: Alles auswählen

x^2 - D * y^2 = 1
<=> x = sqrt(1 + D * y^2)
Ich inkrementiere nun solange y, bis ich ein ganzzahliges Ergebnis für x erhalte:

Code: Alles auswählen

from math import sqrt

D = 1000
store = 0
for d in xrange(2, D + 1):
	# continue if d is square
    if sqrt(d)**2 == d:
        continue
	y = 1
	while True:
		x = sqrt(1 + d * y**2)
		if int(x) == x:
			if x > store:
				store = x
				print "D = %i (x is %i, y is %i)" % (d, x, y)
			break
		y += 1
Für die Beispielfälle in der Problemstellung kriege ich auch schnell die richtigen Ergebnisse. Als Zielwert für D erhalte ich 617, wobei x = 1592796237, und y = 64123562. Das Ergebnis ist jedoch falsch, und ich habe mal kurz in der Shell überprüft:

Code: Alles auswählen

>>> x = 1592796237
>>> y = 64123562
>>> D = 617
>>> sqrt(1 + D * y**2)
1592796237.0
>>> x == _
True
>>> x**2 - D * y**2
421L
Jetzt stehe ich ziemlich auf dem Schlauch! Warum sind die Ergebnisse nicht äquivalent? Ich kann mir ja kaum vorstellen, dass math.sqrt() fehlerhaft ist, aber ich finde in meiner Umformung sowie der Überprüfung keinen Fehler. Ich würde mich freuen, wenn mich jemand erhellen könnte.

P.S.: Ich suche natürlich nicht die Lösung des eigentlichen Problems, sondern Hilfestellung hinsichtlich meines Ansatzes..
I am not part of the allesburner. I am the [url=http://allesburner.de]allesburner[/url].
Benutzeravatar
b.esser-wisser
User
Beiträge: 272
Registriert: Freitag 20. Februar 2009, 14:21
Wohnort: Bundeshauptstadt B.

Willkommen in der Welt der Fließkommazahlen - die 'Kommazahlen' in Python sind normalerweise C-'doubles', d.h die haben 16 signifikante Stellen (nicht Nachkommastellen) - da schießt schon dein y**2 drüber raus.

Zu deinem Problem
a) Finde/schreibe eine Wurzelzieh-routine für longs
b) Forme die Formel nicht um, berechne x**2 jedes mal

hth, Jörg
Wir haben schon 10% vom 21. Jahrhundert hinter uns!
Redprince
User
Beiträge: 128
Registriert: Freitag 22. Oktober 2004, 09:22
Wohnort: Salzgitter
Kontaktdaten:

Vielen Dank! Ich hatte mir etwas in dieser Richtung schon gedacht; immerhin ist es nicht an meinen Umformungskünsten gescheitert.. ;)
I am not part of the allesburner. I am the [url=http://allesburner.de]allesburner[/url].
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Redprince hat geschrieben:P.S.: Ich suche natürlich nicht die Lösung des eigentlichen Problems, sondern Hilfestellung hinsichtlich meines Ansatzes.
Möglicherweise kommst du mit deinem Algorithmus zum Ziel, wenn du das decimal-Modul einsetzt.

Ich habe für meine eigene Lösung von "Euler 66" einen anderen Weg gewählt. Das Stichwort lautet "Pellsche Gleichung" ...
Wenn man das anständig implementiert, ist die Laufzeit nahe Null.
Antworten