Anonymous user
Pell's equation: Difference between revisions
→{{header|Go}}
(Add Swift) |
|||
Line 307:
</pre>
=={{header|Java}}==
<lang java>
import java.math.BigInteger;
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.List;
public class PellsEquation {
public static void main(String[] args) {
NumberFormat format = NumberFormat.getInstance();
for ( int n : new int[] {61, 109, 181, 277, 8941} ) {
BigInteger[] pell = pellsEquation(n);
System.out.printf("x^2 - %3d * y^2 = 1 for:%n x = %s%n y = %s%n%n", n, format.format(pell[0]), format.format(pell[1]));
}
}
private static final BigInteger[] pellsEquation(int n) {
int a0 = (int) Math.sqrt(n);
if ( a0*a0 == n ) {
throw new IllegalArgumentException("ERROR 102: Invalid n = " + n);
}
List<Integer> continuedFrac = continuedFraction(n);
int count = 0;
BigInteger ajm2 = BigInteger.ONE;
BigInteger ajm1 = new BigInteger(a0 + "");
BigInteger bjm2 = BigInteger.ZERO;
BigInteger bjm1 = BigInteger.ONE;
boolean stop = (continuedFrac.size() % 2 == 1);
if ( continuedFrac.size() == 2 ) {
stop = true;
}
while ( true ) {
count++;
BigInteger bn = new BigInteger(continuedFrac.get(count) + "");
BigInteger aj = bn.multiply(ajm1).add(ajm2);
BigInteger bj = bn.multiply(bjm1).add(bjm2);
if ( stop && (count == continuedFrac.size()-2 || continuedFrac.size() == 2) ) {
return new BigInteger[] {aj, bj};
}
else if (continuedFrac.size() % 2 == 0 && count == continuedFrac.size()-2 ) {
stop = true;
}
if ( count == continuedFrac.size()-1 ) {
count = 0;
}
ajm2 = ajm1;
ajm1 = aj;
bjm2 = bjm1;
bjm1 = bj;
}
}
private static final List<Integer> continuedFraction(int n) {
List<Integer> answer = new ArrayList<Integer>();
int a0 = (int) Math.sqrt(n);
answer.add(a0);
int a = -a0;
int aStart = a;
int b = 1;
int bStart = b;
while ( true ) {
//count++;
int[] values = iterateFrac(n, a, b);
answer.add(values[0]);
a = values[1];
b = values[2];
if (a == aStart && b == bStart) break;
}
return answer;
}
// array[0] = new part of cont frac
// array[1] = new a
// array[2] = new b
private static final int[] iterateFrac(int n, int a, int b) {
int x = (int) Math.floor((b * Math.sqrt(n) - b * a)/(n - a * a));
int[] answer = new int[3];
answer[0] = x;
answer[1] = -(b * a + x *(n - a * a)) / b;
answer[2] = (n - a * a) / b;
return answer;
}
}
</lang>
{{out}}
<pre>
x^2 - 61 * y^2 = 1 for:
x = 1,766,319,049
y = 226,153,980
x^2 - 109 * y^2 = 1 for:
x = 158,070,671,986,249
y = 15,140,424,455,100
x^2 - 181 * y^2 = 1 for:
x = 2,469,645,423,824,185,801
y = 183,567,298,683,461,940
x^2 - 277 * y^2 = 1 for:
x = 159,150,073,798,980,475,849
y = 9,562,401,173,878,027,020
x^2 - 8941 * y^2 = 1 for:
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
</pre>
=={{header|Julia}}==
| |||