Pell's equation: Difference between revisions

Content added Content deleted

Inline

@@ Line 876: / Line 876: @@
 <lang python>import math
-def fun(a, b, c):
+def solvePell(n):
-    t = a[0]
-    a[0] = b[0]
-    b[0] = b[0] * c + t
-def solvePell(n, a, b):
     x = int(math.sqrt(n))
-    y = x
+    y, z, r = x, 1, x << 1
-    z = 1
+    e1, e2 = 1, 0
-    r = x << 1
+    f1, f2 = 0, 1
-    e1 = [1]
-    e2 = [0]
-    f1 = [0]
-    f2 = [1]
     while True:
         y = r * z - y
-        z = ((n - y * y) // z)
+        z = (n - y * y) // z
         r = (x + y) // z
-        fun(e1, e2, r)
-        fun(f1, f2, r)
-        a[0] = f2[0]
-        b[0] = e2[0]
-        fun(b, a, x)
-        if a[0] * a[0] - n * b[0] * b[0] == 1:
-            return
+        e1, e2 = e2, e1 + e2 * r
-x = [0]
+        f1, f2 = f2, f1 + f2 * r
-y = [0]
+        a, b = f2 * x + e2, f2
+        if a * a - n * b * b == 1:
+            return a, b
 for n in [61, 109, 181, 277]:
-    solvePell(n, x, y)
+    x, y = solvePell(n)
-    print("x^2 - %3d * y^2 = 1 for x = %27d and y = %25d" % (n, x[0], y[0]))</lang>
+    print("x^2 - %3d * y^2 = 1 for x = %27d and y = %25d" % (n, x, y))</lang>
 {{out}}
 <pre>x^2 -  61 * y^2 = 1 for x =                  1766319049 and y =                 226153980