Pell's equation: Difference between revisions

=={{header|Rust}}==

<lang rust>

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);

}

</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 = 159150073798980475849 and y = 9562401173878027020

</pre>