Pell's equation: Difference between revisions
Content added Content deleted
(→{{header|Haskell}}: added solution) |
|||
| Line 436: | Line 436: | ||
x^2 - 277*y^2 = 1 for x = 159150073798980475849 and y = 9562401173878027020 |
x^2 - 277*y^2 = 1 for x = 159150073798980475849 and y = 9562401173878027020 |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
|||
{{trans|C#}} |
|||
<lang haskell>pell :: Integral a => a -> (a, a) |
|||
pell n = go (x, 1, x * 2, 1, 0, 0, 1) |
|||
where |
|||
x = floor $ sqrt $ fromIntegral n |
|||
go (y, z, r, e1, e2, f1, f2) = |
|||
let y' = r * z - y |
|||
z' = (n - y' * y') `div` z |
|||
r' = (x + y') `div` z' |
|||
(e1', e2') = (e2, e2 * r' + e1) |
|||
(f1', f2') = (f2, f2 * r' + f1) |
|||
(a, b) = (f2', e2') |
|||
(b', a') = (a, a * x + b) |
|||
in if a' * a' - n * b' * b' == 1 |
|||
then (a', b') |
|||
else go (y', z', r', e1', e2', f1', f2')</lang> |
|||
<pre>λ> mapM_ print $ pell <$> [61,109,181,277] |
|||
(1766319049,226153980) |
|||
(158070671986249,15140424455100) |
|||
(2469645423824185801,183567298683461940) |
|||
(159150073798980475849,9562401173878027020)</pre> |
|||
=={{header|J}}== |
=={{header|J}}== |
||