Das deutsche Python-Forum

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

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

Vielen Dank! Ich hatte mir etwas in dieser Richtung schon gedacht; immerhin ist es nicht an meinen Umformungskünsten gescheitert..

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.

Das deutsche Python-Forum

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

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

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