Pell's equation: Difference between revisions
Content added Content deleted
(Ada version) |
|||
Line 834: | Line 834: | ||
x = 2,565,007,112,872,132,129,669,406,439,503,954,211,359,492,684,749,762,901,360,167,370,740,763,715,001,557,789,090,674,216,330,243,703,833,040,774,221,628,256,858,633,287,876,949,448,689,668,281,446,637,464,359,482,677,366,420,261,407,112,316,649,010,675,881,349,744,201 |
x = 2,565,007,112,872,132,129,669,406,439,503,954,211,359,492,684,749,762,901,360,167,370,740,763,715,001,557,789,090,674,216,330,243,703,833,040,774,221,628,256,858,633,287,876,949,448,689,668,281,446,637,464,359,482,677,366,420,261,407,112,316,649,010,675,881,349,744,201 |
||
y = 27,126,610,172,119,035,540,864,542,981,075,550,089,190,381,938,849,116,323,732,855,930,990,771,728,447,597,698,969,628,164,719,475,714,805,646,913,222,890,277,024,408,337,458,564,351,161,990,641,948,210,581,361,708,373,955,113,191,451,102,494,265,278,824,127,994,180 |
y = 27,126,610,172,119,035,540,864,542,981,075,550,089,190,381,938,849,116,323,732,855,930,990,771,728,447,597,698,969,628,164,719,475,714,805,646,913,222,890,277,024,408,337,458,564,351,161,990,641,948,210,581,361,708,373,955,113,191,451,102,494,265,278,824,127,994,180 |
||
</pre> |
|||
=={{header|jq}}== |
|||
{{trans|Wren}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
'''Preliminaries''' |
|||
<lang jq># If $j is 0, then an error condition is raised; |
|||
# otherwise, assuming infinite-precision integer arithmetic, |
|||
# if the input and $j are integers, then the result will be an integer. |
|||
def idivide($i; $j): |
|||
($i % $j) as $mod |
|||
| ($i - $mod) / $j ; |
|||
def idivide($j): |
|||
idivide(.; $j); |
|||
# input should be a non-negative integer for accuracy |
|||
# but may be any non-negative finite number |
|||
def isqrt: |
|||
def irt: |
|||
. as $x |
|||
| 1 | until(. > $x; . * 4) as $q |
|||
| {$q, $x, r: 0} |
|||
| until( .q <= 1; |
|||
.q |= idivide(4) |
|||
| .t = .x - .r - .q |
|||
| .r |= idivide(2) |
|||
| if .t >= 0 |
|||
then .x = .t |
|||
| .r += .q |
|||
else . |
|||
end) |
|||
| .r ; |
|||
if type == "number" and (isinfinite|not) and (isnan|not) and . >= 0 |
|||
then irt |
|||
else "isqrt requires a non-negative integer for accuracy" | error |
|||
end ;</lang> |
|||
'''The Task''' |
|||
<lang jq>def solvePell: |
|||
. as $n |
|||
| ($n|isqrt) as $x |
|||
| { $x, |
|||
y : $x, |
|||
z : 1, |
|||
r : ($x * 2), |
|||
v1 : 1, |
|||
v2 : 0, |
|||
f1 : 0, |
|||
f2 : 1 } |
|||
| until(.emit; |
|||
.y = .r*.z - .y |
|||
| .z = idivide($n - .y*.y; .z) |
|||
| .r = idivide(.x + .y; .z) |
|||
| .v1 as $t |
|||
| .v1 = .v2 |
|||
| .v2 = .r*.v2 + $t |
|||
| .f1 as $t |
|||
| .f1 = .f2 |
|||
| .f2 = .r*.f2 + $t |
|||
| (.v2 + .x*.f2) as $a |
|||
| .f2 as $b |
|||
| if ($a*$a - $n*$b*$b == 1) then .emit = [$a, $b] else . end |
|||
).emit ; |
|||
(61, 109, 181, 277) |
|||
| solvePell as $res |
|||
| "x² - \(.)y² = 1 for x = \($res[0]) and y = \($res[1])"</lang> |
|||
{{out}} |
|||
<pre> |
|||
x² - 61y² = 1 for x = 1766319049 and y = 226153980 |
|||
x² - 109y² = 1 for x = 158070671986249 and y = 15140424455100 |
|||
x² - 181y² = 1 for x = 2469645423824185801 and y = 183567298683461940 |
|||
x² - 277y² = 1 for x = 159150073798980475849 and y = 9562401173878027020 |
|||
</pre> |
</pre> |
||