Pell's equation: Difference between revisions
Content added Content deleted
Langurmonkey (talk | contribs) |
|||
Line 136: | Line 136: | ||
x^2 - 181 * y^2 = 1 for x = 2469645423824185801 nd y = 183567298683461940 |
x^2 - 181 * y^2 = 1 for x = 2469645423824185801 nd y = 183567298683461940 |
||
x^2 - 277 * y^2 = 1 for x = 11576121209304062921 nd y = 9562401173878027020</pre> |
x^2 - 277 * y^2 = 1 for x = 11576121209304062921 nd y = 9562401173878027020</pre> |
||
=={{header|C++}}== |
|||
{{trans|C}} |
|||
As with the C solution, the output for n = 277 is not correct because 64-bits is not enough to represent the value. |
|||
<lang cpp>#include <iomanip> |
|||
#include <iostream> |
|||
#include <tuple> |
|||
std::tuple<uint64_t, uint64_t> solvePell(int n) { |
|||
int x = (int)sqrt(n); |
|||
if (x * x == n) { |
|||
// n is a perfect square - no solution other than 1,0 |
|||
return std::make_pair(1, 0); |
|||
} |
|||
// there are non-trivial solutions |
|||
int y = x; |
|||
int z = 1; |
|||
int r = 2 * x; |
|||
std::tuple<uint64_t, uint64_t> e = std::make_pair(1, 0); |
|||
std::tuple<uint64_t, uint64_t> f = std::make_pair(0, 1); |
|||
uint64_t a = 0; |
|||
uint64_t b = 0; |
|||
while (true) { |
|||
y = r * z - y; |
|||
z = (n - y * y) / z; |
|||
r = (x + y) / z; |
|||
e = std::make_pair(std::get<1>(e), r * std::get<1>(e) + std::get<0>(e)); |
|||
f = std::make_pair(std::get<1>(f), r * std::get<1>(f) + std::get<0>(f)); |
|||
a = std::get<1>(e) + x * std::get<1>(f); |
|||
b = std::get<1>(f); |
|||
if (a * a - n * b * b == 1) { |
|||
break; |
|||
} |
|||
} |
|||
return std::make_pair(a, b); |
|||
} |
|||
void test(int n) { |
|||
auto r = solvePell(n); |
|||
std::cout << "x^2 - " << std::setw(3) << n << " * y^2 = 1 for x = " << std::setw(21) << std::get<0>(r) << " and y = " << std::setw(21) << std::get<1>(r) << '\n'; |
|||
} |
|||
int main() { |
|||
test(61); |
|||
test(109); |
|||
test(181); |
|||
test(277); |
|||
return 0; |
|||
}</lang> |
|||
{{out}} |
|||
<pre>x^2 - 61 * y^2 = 1 for x = 1766319049 and y = 226153980 |
|||
x^2 - 109 * y^2 = 1 for x = 158070671986249 and y = 15140424455100 |
|||
x^2 - 181 * y^2 = 1 for x = 2469645423824185801 and y = 183567298683461940 |
|||
x^2 - 277 * y^2 = 1 for x = 11576121209304062921 and y = 9562401173878027020</pre> |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |