Arithmetische Probleme mit Java-Longs

Question

Ich habe zwei Gleichungen: x * x - D * y * y = 1 und x = sqrt(1 + D * y * y). Beide sind algebraische Manipulationen der anderen.

Gegeben D, muss ich für den kleinsten ganzzahligen Wert von x lösen, so dass y auch eine ganze Zahl ist. Ich durchlaufe mögliche y-Werte, stecke sie in die zweite Gleichung und teste, ob x eine ganze Zahl ist. Wenn es ist, gebe ich x zurück.

Das Problem, das ich habe, ist, wenn x, y und D in die erste Gleichung eingesetzt werden, ist es gleich nicht 1.

Dies sind einige problematische Werte:

1. x=335159612 y=42912791 D=61 
2. x=372326272 y=35662389 D=109 

Meine Intuition ist, dass Javas Math.sqrt Methode berechnet solch eine kleine Dezimalzahl nicht, aber BigDecimal hat keine Quadratwurzelmethode.

Ist meine Mathematik einfach falsch? Wenn nicht, was kann ich tun, um x und y genau zu berechnen?

Edit: Hier ist die Wurzel des Problems zusammen mit der Methode, die testet, ob ein Double eine natürliche Zahl ist.

public static void main(String[] args){ 
    long x = 335159612, D = 61, y = 42912791; 
    System.out.println(Math.sqrt(D * y * y + 2)); // 3.35159612E8 
    System.out.println(x * x - D * y * y); // 3 
} 

public static boolean isNatural(double d){ 
    return d == (int)d; 
} 

Answer 1

Seien Sie vorsichtig mit Genauigkeiten in ‚double‘ anzuwenden.

Gemäß IEEE 754-1985 liefert die doppelte Genauigkeit 16 Ziffern (15,9, um absolut präzise zu sein).

z. a) SQRT (112331965515990542) ist

335159611.99999999701634694576505237017910 

die, wenn sie in ein Doppel umgewandelt, 3.3515961199999999E8

b) SQRT (112331965515990543)

in Doppel

335159611.99999999850817347288252618840968 

die, wenn sie umgesetzt gibt, gibt 3.3515961199999999E8. Also, nach IEEE 754-1985 Definition, sind diese Werte gleich. Anscheinend werden weitere logische/mathematische Prüfungen im Allgemeinen ungenau sein.

Zur Überwindung dieser Einschränkung empfehle ich BigMath Paket von www.javasoft.ch

import ch.javasoft.math.BigMath; 
import java.math.BigDecimal; 

class Tester { 
    public static void main(String[] args) { 
     long D = 61L, y = 42912791L; 
     double a = Math.sqrt(D * y * y + 1); 
     double b = Math.sqrt(D * y * y + 2); 
     System.out.println(a); 
     System.out.println(b); 
     System.out.println(a == b); 

     BigDecimal bda = BigMath.sqrt(new BigDecimal(D * y * y + 1), 32); 
     BigDecimal bdb = BigMath.sqrt(new BigDecimal(D * y * y + 2), 32); 
     System.out.println(bda.toString()); 
     System.out.println(bdb.toString()); 
     System.out.println(bda.equals(bdb)); 
    } 
} 

Ergebnis:

3.35159612E8 
3.35159612E8 
true 
335159611.99999999701634694576505237017910 
335159611.99999999850817347288252618840968 
false 

---

P. S. ruinieren vollständig Ihren Glauben in Standard-Java-Mathe versuchen Sie dies:

System.out.println(0.9200000000000002); 
System.out.println(0.9200000000000001); 

Sie sehen:

0.9200000000000002 
0.9200000000000002 

Answer 2

Wenn sqrt das Problem ist, verwenden Sie stattdessen die erste Gleichung. Wenn x eine ganze Zahl ist, ist x^2 auch eine ganze Zahl; Wenn x keine Ganzzahl ist, dann ist x^2 auch keine ganze Zahl, solange Sie BigDecimals mit ausreichendem Maßstab für Ihre Berechnungen verwenden und nicht doppelt.

Answer 3

Diese Art von Diophantine Gleichungen ist bekannt als Pell-Gleichungen.
Wiki.
Mathworld.

Beide Links enthalten Hinweise - wie diese Gleichung mit fortlaufenden Brüchen zu lösen ist.

denke ich, es wäre schön, etwas Mathematik statt brutforce/