Pell's equation: Difference between revisions
Content added Content deleted
(init J) |
|||
Line 438: | Line 438: | ||
=={{header|J}}== |
=={{header|J}}== |
||
<lang J>NB. sqrt representation for continued fraction |
|||
sqrt_cf =: 3 : 0 |
|||
rep=. '' [ 'm d'=. 0 1 [ a =. a0=. <. %: y |
|||
while. a ~: +: a0 do. |
|||
rep=. rep , a=. <. (a0+m) % d=. d %~ y - *: m=. m -~ a*d |
|||
end. a0;rep |
|||
) |
|||
NB. find x,y such that x^2 - n*y^2 = 1 using continued fractions |
|||
pell =: 3 : 0 |
|||
n =. 1 [ 'a0 as' =. x: &.> sqrt_cf y |
|||
while. 1 do. cs =. 2 x: (+%)/\ a0, n$as NB. convergents |
|||
if. # sols =. I. 1 = (*: cs) +/ . * 1 , -y do. cs {~ {. sols return. end. |
|||
n =. +: n |
|||
end. |
|||
) |
|||
</lang> |
|||
Check that task is actually solved |
|||
<lang J>verify =: 3 : 0 |
|||
assert. 1 = (*: xy) +/ . * 1 _61 [ echo 61 ; xy =. pell 61 |
|||
assert. 1 = (*: xy) +/ . * 1 _109 [ echo 109 ; xy =. pell 109 |
|||
assert. 1 = (*: xy) +/ . * 1 _181 [ echo 181 ; xy =. pell 181 |
|||
assert. 1 = (*: xy) +/ . * 1 _277 [ echo 277 ; xy =. pell 277 |
|||
) |
|||
</lang> |
|||
{{out}} |
|||
<pre> verify '' |
|||
┌──┬────────────────────┐ |
|||
│61│1766319049 226153980│ |
|||
└──┴────────────────────┘ |
|||
┌───┬──────────────────────────────┐ |
|||
│109│158070671986249 15140424455100│ |
|||
└───┴──────────────────────────────┘ |
|||
┌───┬──────────────────────────────────────┐ |
|||
│181│2469645423824185801 183567298683461940│ |
|||
└───┴──────────────────────────────────────┘ |
|||
┌───┬─────────────────────────────────────────┐ |
|||
│277│159150073798980475849 9562401173878027020│ |
|||
└───┴─────────────────────────────────────────┘ |
|||
</pre> |
|||
=={{header|Java}}== |
=={{header|Java}}== |