60 lines
1.6 KiB
Plaintext
60 lines
1.6 KiB
Plaintext
use num_bigint::{ToBigInt, BigInt};
|
|
use num_traits::{Zero, One};
|
|
//use std::mem::replace in the loop if you want this to be more efficient
|
|
|
|
fn main() {
|
|
test(61u64);
|
|
test(109u64);
|
|
test(181u64);
|
|
test(277u64);
|
|
}
|
|
|
|
struct Pair {
|
|
v1: BigInt,
|
|
v2: BigInt,
|
|
}
|
|
|
|
impl Pair {
|
|
pub fn make_pair(a: &BigInt, b: &BigInt) -> Pair {
|
|
Pair {
|
|
v1: a.clone(),
|
|
v2: b.clone(),
|
|
}
|
|
}
|
|
|
|
}
|
|
|
|
fn solve_pell(n: u64) -> Pair{
|
|
let x: BigInt = ((n as f64).sqrt()).to_bigint().unwrap();
|
|
if x.clone() * x.clone() == n.to_bigint().unwrap() {
|
|
Pair::make_pair(&One::one(), &Zero::zero())
|
|
} else {
|
|
let mut y: BigInt = x.clone();
|
|
let mut z: BigInt = One::one();
|
|
let mut r: BigInt = ( &z + &z) * x.clone();
|
|
let mut e: Pair = Pair::make_pair(&One::one(), &Zero::zero());
|
|
let mut f: Pair = Pair::make_pair(&Zero::zero() ,&One::one());
|
|
let mut a: BigInt = Zero::zero();
|
|
let mut b: BigInt = Zero::zero();
|
|
while &a * &a - n * &b * &b != One::one() {
|
|
//println!("{} {} {}", y, z, r);
|
|
y = &r * &z - &y;
|
|
z = (n - &y * &y) / &z;
|
|
r = (&x + &y) / &z;
|
|
|
|
e = Pair::make_pair(&e.v2, &(&r * &e.v2 + &e.v1));
|
|
f = Pair::make_pair(&f.v2, &(&r * &f.v2 + &f.v1));
|
|
a = &e.v2 + &x * &f.v2;
|
|
b = f.v2.clone();
|
|
}
|
|
let pa = &a;
|
|
let pb = &b;
|
|
Pair::make_pair(&pa.clone(), &pb.clone())
|
|
}
|
|
}
|
|
|
|
fn test(n: u64) {
|
|
let r: Pair = solve_pell(n);
|
|
println!("x^2 - {} * y^2 = 1 for x = {} and y = {}", n, r.v1, r.v2);
|
|
}
|