/*
Copyright 2025 Owain Davies
SPDX-License-Identifier: Apache-2.0 OR MIT
*/
use crate::{Arbi, Digit};
impl Arbi {
/// Return the greatest common divisor of `self` and `other`.
///
/// The return value is always positive, except when both `self` and `other`
/// are zero, in which case this function returns zero. That is, we define
/// \\( \text{gcd}(0,0) \equiv 0 \\).
pub fn gcd_ref(&self, other: &Self) -> Self {
// We have a choice between Binary GCD and Knuth Algorithm L (Lehmer).
// Preliminary benchmarks show that Binary GCD outperforms L, sometimes
// by a factor of 3-4. However, when one input is very small and the
// other large, algorithm L might outperform the other. In the future,
// it might be useful to choose the algorithm based on input sizes.
self.gcd_ref_b_optimized(other)
}
}
impl Arbi {
pub(crate) fn gcd_ref_b_optimized(&self, other: &Self) -> Self {
if self.is_zero() {
return other.abs_ref();
}
if other.is_zero() {
return self.abs_ref();
}
let mut u = self.abs_ref();
let mut v = other.abs_ref();
let uz = u.trailing_zeros().unwrap_or(0);
let vz = v.trailing_zeros().unwrap_or(0);
let k = core::cmp::min(uz, vz);
u >>= uz;
v >>= vz;
loop {
if u > v {
core::mem::swap(&mut u, &mut v);
}
v -= &u;
if v == 0 {
return u << k;
}
v >>= v.trailing_zeros().unwrap_or(0);
}
}
// Knuth Algorithm B
#[allow(dead_code)]
pub(crate) fn gcd_ref_b(&self, other: &Self) -> Self {
if self.is_zero() {
return other.abs_ref();
}
if other.is_zero() {
return self.abs_ref();
}
let mut u = self.abs_ref();
let mut v = other.abs_ref();
// Ensure u >= v
if u < v {
core::mem::swap(&mut u, &mut v);
}
Self::gcd_knuth_algo_b(u, v)
}
fn gcd_knuth_algo_b(mut u: Self, mut v: Self) -> Self {
/* B1. [Find power of 2.]
* Set k <- 0, then repeatedly set k <- k + 1, u <- u/2, v <- v/2,
* zero or more times until u and v are not both even.
*/
let u_trailing = u.trailing_zeros().unwrap_or(0);
let v_trailing = v.trailing_zeros().unwrap_or(0);
let k = core::cmp::min(u_trailing, v_trailing);
u >>= k;
v >>= k;
/* B2. [Initialize.]
* If u is odd, set t <- -v and go to B4. Otherwise, set t <- u.
*/
let mut t = if u.is_odd() { -&v } else { u.clone() };
loop {
/* B3. [Halve t.] Set t <- t/2.
* B4. [Is t even?] If t is even, go back to B3.
*/
if let Some(trailing) = t.trailing_zeros() {
t >>= trailing;
}
/* B5. [Reset max(u,v).]
* If t > 0, set u <- t; otherwise set v <- -t.
*/
if t > 0 {
u = core::mem::take(&mut t);
} else {
t.negate_mut();
v = core::mem::take(&mut t);
}
/* B6. [Subtract.]
* Set t <- u - v. If t != 0, go back to B3.
* Otherwise, algorithm terminates with u * 2^k as the output.
*/
t = &u - &v;
if t.is_zero() {
break;
}
}
u << k
}
}
#[allow(dead_code)]
impl Arbi {
fn gcd_ref_l(&self, other: &Self) -> Self {
if self.is_zero() {
return other.abs_ref();
}
if other.is_zero() {
return self.abs_ref();
}
let mut u = self.abs_ref();
let mut v = other.abs_ref();
/* Ensure u >= v >= 0 */
if u < v {
core::mem::swap(&mut u, &mut v);
}
Self::gcd_lehmer(&mut u, &mut v)
}
fn gcd_lehmer(u: &mut Self, v: &mut Self) -> Self {
loop {
let u_len = u.vec.len();
let v_len = v.vec.len();
/* L1. [Initialize.] If v is small enough to be represented as a
* single-precision value, calculate gcd(u,v) by Algorithm A and
* terminate the computation.
*/
if v.is_zero() {
return core::mem::take(u);
}
// TODO: 2? 1? Single-precision division algo instead?
if v_len <= 2 {
return Self::gcd_euclidean(u, v);
}
/* Otherwise, let uhat be the p leading digits of u and let vhat be
* the corresponding digits of v
*/
let p = 2;
let k = u_len.saturating_sub(p);
let mut uhat = Self::get_leading_digits(&u.vec, k);
let mut vhat = Self::get_leading_digits(&v.vec, k);
/* Set A <- 1, B <- 0, C <- 0, D <- 1 */
let (mut a, mut b, mut c, mut d): (u64, u64, u64, u64) =
(1, 0, 0, 1);
loop {
/* L2. [Test quotient.] */
/* Division by zero in this step is taken to mean "Go directly
* to L4".
*/
if vhat + c == 0 || vhat + d == 0 {
break;
}
/* Set q <- floor((uhat + A)/(vhat + C))
* If q != floor((uhat + B) / (vhat + D), go to step L4.
*/
let q = (uhat + a) / (vhat + c);
if q != (uhat + b) / (vhat + d) {
break;
}
/* L3. [Emulate Euclid.]
* Set T <- A - qC, A <- C, C <- T,
* T <- B - qD, B <- D, D <- T,
* T <- uhat - q * vhat,
* uhat <- vhat,
* vhat <- T,
* and go back to step L2.
*/
if q * c > a || q * d > b || q * vhat > uhat {
// TODO: have test case for q * d > b but not others
break;
}
let mut t = a - q * c;
a = c;
c = t;
t = b - q * d;
b = d;
d = t;
t = uhat - q * vhat;
uhat = vhat;
vhat = t;
}
/* L4. [Multiprecision step.]
* If B = 0, set t <- u mod v, u <- v, v <- t.
* Otherwise, set t <- Au, t <- t + Bv, w <- Cu, w <- w + Dv,
* u <- t, v <- w.
* Go back to step L1.
*/
if b == 0 {
let t = &*u % &*v;
*u = core::mem::take(v);
*v = t;
} else {
// TODO: need test case
let t = a * &*u + b * &*v;
let w = c * &*u + d * &*v;
*u = t;
*v = w;
}
}
}
fn get_leading_digits(digits: &[Digit], k: usize) -> u64 {
let n = digits.len();
if k >= n {
return 0;
}
let mut ret = digits[n - 1] as u64;
if n > k + 1 {
ret = (ret << Digit::BITS) | (digits[n - 2] as u64);
}
if ret > 0 {
let leading_zeros = ret.leading_zeros();
if leading_zeros > 0 && n > k + 2 {
// TODO: is this needed? Need test case
ret <<= leading_zeros;
let digit = digits[n - 3] as u64;
ret |= digit >> (Digit::BITS - leading_zeros);
}
}
ret
}
/* Euclidean Algorithm */
fn gcd_euclidean(a: &mut Self, b: &mut Self) -> Self {
while !b.is_zero() {
let r = &*a % &*b;
*a = core::mem::take(b);
*b = r;
}
core::mem::take(a)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::util::test::{get_seedable_rng, get_uniform_die, Distribution};
use crate::{SDDigit, SDigit, SQDigit};
fn gcd_primitive<T>(mut a: T, mut b: T) -> T
where
T: Copy + PartialEq + std::ops::Rem<Output = T> + Default,
{
let zero = T::default();
while b != zero {
let temp = b;
b = a % b;
a = temp;
}
a
}
fn abs_primitive<T>(x: T) -> T
where
T: Copy + PartialOrd + std::ops::Neg<Output = T> + Default,
{
if x < T::default() {
-x
} else {
x
}
}
#[test]
fn smoke() {
let (mut rng, _) = get_seedable_rng();
let small = get_uniform_die(-100i16, 100i16);
let sd = get_uniform_die(SDigit::MIN, SDigit::MAX); // i32
let sdd = get_uniform_die(SDDigit::MIN, SDDigit::MAX); // i64
let sqd = get_uniform_die(SQDigit::MIN, SQDigit::MAX); // i128
for _ in 0..20000 {
// (i32,i32)
let (a, b) = (sd.sample(&mut rng), sd.sample(&mut rng));
let (arbi_a, arbi_b) = (Arbi::from(a), Arbi::from(b));
let expected = abs_primitive(gcd_primitive(a, b));
let actual = Arbi::gcd_ref(&arbi_a, &arbi_b);
assert_eq!(
actual, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a, b, expected, actual
);
let actual_2 = Arbi::gcd_ref_l(&arbi_a, &arbi_b);
assert_eq!(actual, actual_2);
// (i64,i64)
let (a, b) = (sdd.sample(&mut rng), sdd.sample(&mut rng));
let (arbi_a, arbi_b) = (Arbi::from(a), Arbi::from(b));
let expected = abs_primitive(gcd_primitive(a, b));
let actual = Arbi::gcd_ref(&arbi_a, &arbi_b);
assert_eq!(
actual, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a, b, expected, actual
);
let actual_2 = Arbi::gcd_ref_l(&arbi_a, &arbi_b);
assert_eq!(actual, actual_2);
// (i128,i28)
let (a, b) = (sqd.sample(&mut rng), sqd.sample(&mut rng));
let (arbi_a, arbi_b) = (Arbi::from(a), Arbi::from(b));
let expected = abs_primitive(gcd_primitive(a, b));
let actual = Arbi::gcd_ref(&arbi_a, &arbi_b);
assert_eq!(
actual, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a, b, expected, actual
);
let actual_2 = Arbi::gcd_ref_l(&arbi_a, &arbi_b);
assert_eq!(actual, actual_2);
// (i32,i64)
let (a, b) = (sd.sample(&mut rng), sdd.sample(&mut rng));
let (arbi_a, arbi_b) = (Arbi::from(a), Arbi::from(b));
let expected = abs_primitive(gcd_primitive(a as SDDigit, b));
let actual = Arbi::gcd_ref(&arbi_a, &arbi_b);
assert_eq!(
actual, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a, b, expected, actual
);
let actual_2 = Arbi::gcd_ref_l(&arbi_a, &arbi_b);
assert_eq!(actual, actual_2);
// (i32,i128)
let (a, b) = (sd.sample(&mut rng), sqd.sample(&mut rng));
let (arbi_a, arbi_b) = (Arbi::from(a), Arbi::from(b));
let expected = abs_primitive(gcd_primitive(a as SQDigit, b));
let actual = Arbi::gcd_ref(&arbi_a, &arbi_b);
assert_eq!(
actual, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a, b, expected, actual
);
let actual_2 = Arbi::gcd_ref_l(&arbi_a, &arbi_b);
assert_eq!(actual, actual_2);
// (i64, i128)
let (a, b) = (sdd.sample(&mut rng), sqd.sample(&mut rng));
let (arbi_a, arbi_b) = (Arbi::from(a), Arbi::from(b));
let expected = abs_primitive(gcd_primitive(a as SQDigit, b));
let actual = Arbi::gcd_ref(&arbi_a, &arbi_b);
assert_eq!(
actual, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a, b, expected, actual
);
let actual_2 = Arbi::gcd_ref_l(&arbi_a, &arbi_b);
assert_eq!(actual, actual_2);
// (small,small)
let (a, b) = (small.sample(&mut rng), small.sample(&mut rng));
let (arbi_a, arbi_b) = (Arbi::from(a), Arbi::from(b));
let expected = abs_primitive(gcd_primitive(a, b));
let actual = Arbi::gcd_ref(&arbi_a, &arbi_b);
assert_eq!(
actual, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a, b, expected, actual
);
let actual_2 = Arbi::gcd_ref_l(&arbi_a, &arbi_b);
assert_eq!(actual, actual_2);
// (small,i64)
let (a, b) = (small.sample(&mut rng), sdd.sample(&mut rng));
let (arbi_a, arbi_b) = (Arbi::from(a), Arbi::from(b));
let expected = abs_primitive(gcd_primitive(a as SDDigit, b));
let actual = Arbi::gcd_ref(&arbi_a, &arbi_b);
assert_eq!(
actual, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a, b, expected, actual
);
let actual_2 = Arbi::gcd_ref_l(&arbi_a, &arbi_b);
assert_eq!(actual, actual_2);
// (small,i128)
let (a, b) = (small.sample(&mut rng), sqd.sample(&mut rng));
let (arbi_a, arbi_b) = (Arbi::from(a), Arbi::from(b));
let expected = abs_primitive(gcd_primitive(a as SQDigit, b));
let actual = Arbi::gcd_ref(&arbi_a, &arbi_b);
assert_eq!(
actual, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a, b, expected, actual
);
let actual_2 = Arbi::gcd_ref_l(&arbi_a, &arbi_b);
assert_eq!(actual, actual_2);
}
}
#[test]
fn test_edge_cases() {
let zero = Arbi::from(0);
let five = Arbi::from(5);
assert_eq!(Arbi::gcd_ref(&zero, &five), five);
assert_eq!(Arbi::gcd_ref(&five, &zero), five);
assert_eq!(Arbi::gcd_ref(&zero, &zero), zero);
let neg_five = Arbi::from(-5);
let ten = Arbi::from(10);
let neg_ten = Arbi::from(-10);
assert_eq!(Arbi::gcd_ref(&neg_five, &ten), 5);
assert_eq!(Arbi::gcd_ref(&five, &neg_ten), 5);
assert_eq!(Arbi::gcd_ref(&neg_five, &neg_ten), 5);
let big = Arbi::from(123456789i64);
assert_eq!(Arbi::gcd_ref(&big, &big), big);
let neg_big = Arbi::from(-123456789i64);
assert_eq!(Arbi::gcd_ref(&neg_big, &neg_big), big);
}
#[test]
fn test_properties() {
let (mut rng, _) = get_seedable_rng();
let die = get_uniform_die(SDDigit::MIN, SDDigit::MAX);
for _ in 0..1000 {
let a = die.sample(&mut rng);
let b = die.sample(&mut rng);
let c = die.sample(&mut rng);
let arbi_a = Arbi::from(a);
let arbi_b = Arbi::from(b);
let arbi_c = Arbi::from(c);
// gcd(a, b) = gcd(b, a)
let gcd_ab = Arbi::gcd_ref(&arbi_a, &arbi_b);
let gcd_ba = Arbi::gcd_ref(&arbi_b, &arbi_a);
assert_eq!(
gcd_ab, gcd_ba,
"GCD is not commutative for {} and {}",
a, b
);
// gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)
let gcd_bc = Arbi::gcd_ref(&arbi_b, &arbi_c);
let gcd_a_gcd_bc = Arbi::gcd_ref(&arbi_a, &gcd_bc);
let gcd_ab = Arbi::gcd_ref(&arbi_a, &arbi_b);
let gcd_gcd_ab_c = Arbi::gcd_ref(&gcd_ab, &arbi_c);
assert_eq!(
gcd_a_gcd_bc, gcd_gcd_ab_c,
"GCD is not associative for {}, {}, {}",
a, b, c
);
// gcd(a, 0) = |a|
let gcd_a_zero = Arbi::gcd_ref(&arbi_a, &Arbi::from(0));
assert_eq!(
gcd_a_zero,
arbi_a.abs_ref(),
"gcd({}, 0) should equal |{}|",
a,
a
);
}
}
}
/* These test cases were generated using a Python script to test larger numbers */
#[cfg(test)]
mod tests_large {
use super::*;
#[test]
fn test_gcd_verified_batch_1() {
let test_cases = [
("22085171274584251068220058297048190502231511442703016540537311174952066671152719385774967038392956009579710555484006169911044413488743841759366536433266973257732416563360853842887544368317045011677816725828993240921934540900950296115651007450246908303630997502063485224883578887239928991355247359305826830811276358213283498391463398406274449635745336915141997325393473729446729034496090191587266682728243962108883470249794108612304268801637934959134797999615451321709906954808535390828809781362771026047869508328638565454902609644843470783191761", "98212351283718216447766261301919183603930296084528438372851619208380738321366179857856881142390817206256485659632166462179267794568328001168976710235543186364960548427915515451222405241750396209382233495895690903528358", "23"),
("6791780693697098792150699728548952012546438608989890088916167694859698542976577513671578226981176901560537475122876327023187516535469374423865554303268232485865365939530090646158", "722536380562024150736547305011324438500854863939394459873558021508836894923291898155007178812688760697190702424676146260400670146544158545113158982817942476434626371301030502801763771180817356950014034429847626246754865309672253789512067079385781564517854725311202741481958268307173761397778087532651544345584748146216452294300770331151854342691145222931340990915181300770311059302784112480393914558491307720201421613738166458291930467095303881328425276011883934590318114737023583651161088514649481093697259776878631507725940428240269396858382917412425079204", "2"),
("93884712154996500849710458413714140894784098501347300070588152606328942036777203877641825301268205762323271249122088921982784334266705553150437972077977280061759230791557242726424375372815243211405655983730700542324202672525520924903784609144662114095816169927419338596122868243667106221203838433858230386197694023188383923894304283085758473669855958461046432406157382498814034367134420676088798612716782008017649968363109191707961107295285285054315377775806041182584578852937026566", "1562181390222806863590387638402086775711813704462961686865577046889764620661079661936472300304265307209137895271910782597296576376511401331074855034969659860282283083231060515144694395635654541568881866425206234565410273744493017129856596910800730973850667654241820075819148183108293628802990725752183805965026970", "2"),
("3714362183793325886520979056918426114069585137494000054157654950768268183224171869665894580308217044970599649996836275644184296055874554895863700513851", "27198962733982848539628853206806053562046109670664373572409338418378796717804071492952889917345883468092297915408451184766461064974886736675263771544205386739033689903271825285697600711338776168714367428821787360634147162372427437487233454139343117339712740311924904180912840200122278196649465247513986293603780006344940622326148382642834949401603686532083861159550235717591217282174503798382762492964981941877255311883220961467007293779599269722946158980818626731586542419756786943140978401782233183357024524992989046", "1"),
("86149751484293223699184782215934819409269663289093412855461121908378133245176938196170933507519013562789320708156188324932958865409435080071210138140573133511822272914653240549486579052394313398", "38422229178850235426875964134807377125584367040774064273645457419362632411028720115228437387220334189657601380061152159172757963422818383494331756702905802244979189235298388484719829393956011630763240323435138446600881159660612427177674064313896622309439177618718768461854277454292531421447622372497781676484995089709113306797714587231300444588532358108025945026303800138056363637811536634530432503143645281932670152823478577301634791253485605253624117968671908964690250523563304882399382755915040920179886712554505102151205976932268072155852918110628896740308455431816129396236072688451", "1"),
("31048152900361616636908008917235500074031001569732525834282167088822745107392194160672658506881649343128014928826158714395682200753535976502923984563456340296999816108781488164620197544627780024611343278629838098374025204041476137397195151406260160964997389723553797700863050218599963114039066746", "4355075771406148596123094285215699286519493147360896617893390184775388772404546703918292388239918794620886585718670799861890835391857652960940144629317228121567856292291137686947276520581589321678359690687400236281253074956036716029254953068876975639378", "14"),
("2132270904447907854343929812390699744225268069762727392434701285618936372522707494360531442219606608101804627177142982988113733891037545626720248942891599078607194313640248927593060317291097836", "35789449564187073652176132140410386177617709361539071142708760963783837846374932345547839642973545997901457428245074098871537695441127137753530469878703522950773898107297854718540878427504105396674595656997063427716609360488486249207946798503615740955035707680886976211472201804196432657441398113222127904331617452099173050669964025728322330496169408084682063555188663511269563866263682068421684296598922202444939674231038243667976343327549390030157716480645263005672771775744384174323335704435551062758861337082523618826771542757423709831259558379371187136729549410", "2"),
("17156565221448056865567025431062969720341970566616030150019575564380885120651802571316410789439943957725512066028901861961720648669682986497009012214598914708749640411573300948437005783750043080663841283521444877699625022449672567724", "13018998400017703938897972758344370277428186856224290134434876549101050149277974379453036396384383616713199890739732294453621095653749935563249691702444599039387187427033995743748822760465661017682891485535959747934017334407710230234260609433136635000062404779189963615662478278791689581229867661240945516350568227", "1"),
("37478652051819829454834350438611802048320615304786507220795838154011833873392673805565255855736094355646489123063508665613877648482666669805641349019456513590769439752878416742638882405460042862303620950056819552001878560896218356868255335682", "21942956525674681750291947911409178909418249634274580715710210588537098847269545929689342022998858251174639725468907283591466420755467439028297502236038121511093886311975378893306212801460375232945715201960021691818252814314171251110071420197835639496452643996900799206315852749170827693387025106230144367673619894426683159925461742851653935471827215277143176705539655085264768330647016928783250284267702415097122493", "1"),
("165510033403141181694954017454433578633357140141187654799565387620348538197542550572326477936821795656183362197731381712502947239364603992192110874009890715337309642701936227164039085652274689784145773390368568591019652153187631777095704128026381938928417629331366252390976291633887636807515", "451908529371799016271409637632022377823983846891151547012441889562162210315958746289203261582524207954425925982021452890254869395053295793858240821953454311386301922178267175444232787744730760367488513231744501568090116216102354392446647672759166492179780976773885135422396789950593579330", "15"),
("608127484977537994286885310838512665322165080770435591518793860867235932901628814458882195398557835081787343005779284933235847340811436199391770749577607860705114661877912955381340541821648472706806606969911891557361835904900527662107973014537034772941631622807182182229816985780129466514816206118531202385297290889254498131288379933319402643854480934297671559079639904233968477084656095114685786866033020347353278582144542367444107220857657380821296710791079376036093386408639344507171592536020613549080424952555677058808785193885684970958568289670887639361625686", "41457985358860477592238694358104270319345051150472809726819567064461133845384081268040224731676166256210164668314139116480693427250832997032608402295381082343165968433973084983134885714454299660363843131668197730008033738153490419241215249546450771812381226068771153087687", "1"),
("250411675777463220296652898299517600251182293458178938584406355970463272756626744964291547016811655930738225892421094260007450040796270592732464573432282840195742408290157910465029880810974006860", "53485199331799626804405056905863712839797076840431351727302538280336813457500291541144583663096648912984356013488184787255685957307988293593071594410549805387412438153468352411803834740204356895321821711314889822169255000035402673203668253240274050243378426178466579352576733346615241859601833530462535738457778056962242182513781728390644499936592651780886038488399984000863752830924047984495672353678884149763661342677808468889433", "1"),
("3848429442735684171073595011143130001535817073606105066226126639870231787621416913400845158821446924995884942397503718938228359388164758794425839101172848133214553376551918188015257928720962759268720462180042569091088698813040459038690642836224517721868939642114384007720604802666816689888031107696485434736909", "369102026682757509719539410306215513925679167497078053005302442470763857241838700851323697324184819847023880028837012493068916728847177103242094609387530699430182479856105635937526397987270506409119800368098461360618530349469915372138447037615523276762015898946295323780581299516627867808992908708188251", "1"),
("11086825909570280904890688585008923224658041990329512799323873259327937620576873112026424205024288188780436264712657524355661668054622756926152480505669502665189231198071259818742251926555975576063628393727766389971193349257537206283584712980732781694003390508506588151119944381226001977454041466392220481141877672852423115639688267974050188885479824864544523258968983832504285173380844103787159926527624118573102393310866067459925021124598739305033103183531457997173153793574782874613478", "201393041424072775652551944633785042140904322013076145222086589628787731436995748502863140992580270665526831565831910505235677190220308705398457578047257540669540221660735323436128517463508902850361705818576433662857039894201581379175468333229228210851212002783016066441659560679420586503763403988462118254827595232715430553555803248338019982545570284291200539443416948717816873038936465032110176596986329967942136650301620734651247892114055664169619889233884870726226108867780708022047839615600822005009113903680038960498", "2"),
("790778058625915532903243564507568894947245588927757447556142165939675591645338502811638174583373514684659953740319801135324717072343259282012119549623306376709523092420493804327972099582451379326084325901170872559187568405892922948208337930561806946432746882901421953085618940477283117444728013097617453460777639643368566367494342497396094493638868193774638266977608937452955326376004659687372871408185359411268503507061406427307649542413332727391375558219134765434211235293177567761132600339389703539887286", "12175749410972951195514513260678426810626984471260368753340678900827068692406197476638749227234274343498267316843716188832970768862496918658111863499765751021934095864", "6"),
("4394212539479314442645021550150846238077629608018037953315503593762175320432279445286824748154885569786784870095443295653256763466905689448494996627102960281570519867284705970979429177172633828036020105657098799449320584716545160631460188755309106565229924701192423924137872989092632570413696209835930270237512590873291427901666983441488639403270804743304123262781363940662208809948698244652791653879772392179358011015438746304311557194056456354581396902396163800965841738698098805390783217907226833166549357497042764352434675227708277348722890764487430282538643702461562950358196298088180739699216887", "246625009964684042102391582728054868112398376081337841204286109227302064152976950721790105214362894827097369690699019561189845989286396011999429323021249134871059818032187359487111004112406581144492779466665235470977108703111318614199417162306636571254093505714132224170867086518846427898367899727499637775079718912630912747177374564055272752991845819315371837635570731965305172853124387564081349882770888412978977907274509624185829966015751804188154151437075667863236074936258056552398702051324248012214096642001074", "1"),
("155787960126585213981981977270887446102004402590763528579191277617830938595941284315880549702200599778059959821230342848639114488170354956757559443845514934677519117003387769701107819912708529352865856470765885134365743391369913", "12952568715101372642450275724047055129650762345609447804739944750738010885426689433418834907786458638907969251920518179391385401114542350511113208212909610049607858747857702850868104125682059958979542367517828145445637395710929961923115856937830960383572503964806876475697563443931915501257970873812259314476051196963936", "1"),
("7357948379635418191678349711593325282169596626896123041313805544383608536117472040342215637411465322943882536841068626823707690549971424182061272371133412930596644506018540414031203744602863346217836225219622194128355861077737016043213354101572176718323101889569234705533900455413939980267623132527415986999567332724964446594805627361520507918884152679140633974392796357198893657865789", "46712049359878676917802223205895383816290076729424870235305490475119090669436282589574026625731893216179956002307338087245819106501341103660513005504663837434811678371036295038692630394689437009003053981222280498198466471682675146742662189304248922824581627193052104960516349137478957915125025429130630285230880354093180466917525859752211056621749879636808174500996773616035206717239105278755464268992617426458997861882213186354", "1"),
("135265345351021944632165401778449809106033134784603904887517364633861107301505759124236735189492064852729527005959130993602315999246723037401162883144801519289744866907637167615827679373256512875132891387533027049135365852335028245053654338379128958488915559997992149863353407273836105311912382660625993467379526155102", "581464283049303485738624341897774500924421183205969271618312454576891295690044934722595739899005749260163564964157972404260029971690945000407737582272185919956421359759011634231110196731665870259264692597707634171122463375987979266554290919409084592564280620539803351817577873842042152582816182047972998484125368338967694269290876388885234574318496245237195200178427427986693870726474045937877077167501711112310266342049844530463934937828911912992246133870698", "2"),
("2665302247150539963829531040283328396827080493923130244343819297016124488186630228132377552376646121998996566446611449456832574360428204052401389231627", "4421015628051695843870630328518593939657583934083854625756121347969802170919817300675381240858509256224536346063852517868395759593520363144222146278773705219565730740012076940570652404537258730839486962969688649237816774135411563470498506186384207050276830003936487720647669438051243125079122225896620187955233339828990491974034430914594515771526258321506423888571309518434727154627086285254203730072446796566055697933862786558045968752860816263344211243931982944857588462758957706502608479443015648309066887346381737805190112938982151617090471621503601720", "1"),
("1713120728716950466609913469915000029384762041512409450577800001340120879586168472336304039472212706880105568739689484709311596952786269512630289706813857623237719765433791279896844249251999841724877327246117137451515804801737858491993", "8100816234467592091392623926303596566012237377789494320897852524471539533286524103137410556516534667449537524732732654638288330338184755595464651340612591603036899191017500291173518177094978578", "3"),
("1017548496200888814808841339315074685001731575078060848430317286696905670818114026598898428020786289490558633323516270516501003614327516508460699742120072048660353828330431381297", "26283980860822122812133576806957979763056944296367065402201093468666674372072590948750459369101430302726144779006641271798303201745064240878241706301188764699152294308318303278179179427508232303110627189104946152321418464076175802984414944956602002276831016063249421340782322307010524645012675157924584863364318091326246769488291347001558626822587", "1"),
("137645826825495631898347343054752794656724857492981957948489837831966544651985924217033572964131343113030593784337738115905206470849435635601628293143076376707392480270742999583271928499613759369484429322321550228178110702438374665963670569901139793886315281757003563511977602483873940749653765833685709667233437768073635491067564979878488787502214973183538444191819563110012991900954855930885609343027332144257300716748351144524363237526749451390319498366162473519228296819277323", "2208089337522267215005837367286076245662582308744248301419670459826051383828427842376463745592983691070147868901193578682079142395163633304460332911409446525509148271097859249044420436448736427685917665353417984181307084178417388409133839415353533460108227491453325680522256045365407217811366017518199468329388982971765727316915926017699720101618424165777795464425421698177444456445268", "113"),
("466136261528094197884304322944270649402264531615955579829286753413415395738830365114595201324950641144044902337863279570432748484427729953384576290618511528071585985365836485280015592173508987213857799961500847809311361716712292551111979932473348575464650095228998311003969516777361787426282935966381240839146594091426004240655410888003842012360412217181417943695864897406657694803224749409118994891412292568789828647029673711905432115034832201406740345061805607393972887673898353474016175344994646410251650564107307965083625462252219298341459631039490346294405211928246038787", "36448590498636643314849635977578029635759291959019515303313312782063130257955936696168967477928330345279611056061817309992885129177401975328655012508786936973681693739669227000797797280055526093562685657208776100414083244864747445665758419667032293092089587870617187076040032687657649457558183880201059388", "1"),
("400007296225223890151679139082288180528467650843379344881824164691131101025668168314521453250854562778993152655041097911124793614745543688101372059083797839734960271825576039177372015676209845145258345819028159302811299928348360045600339679577552919726", "598273403818207134074359699304482859214083832996406716239515107208019398253054694476246223689434464168282390012085038967516152334529906136605276674557514982401188448976260946584285936398775382529080956965133096227221269402766886647071038935444176198241778481360723661679435460990464936222097973195083385238695", "1"),
];
for (a_str, b_str, expected_str) in test_cases {
let a = Arbi::from_str_radix(a_str, 10).unwrap();
let b = Arbi::from_str_radix(b_str, 10).unwrap();
let expected = Arbi::from_str_radix(expected_str, 10).unwrap();
let result = a.gcd_ref(&b);
assert_eq!(
result, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a_str, b_str, expected_str, result
);
let result_b = a.gcd_ref_l(&b);
assert_eq!(result, result_b);
// Test commutativity
let result_rev = b.gcd_ref(&a);
assert_eq!(
result_rev, expected,
"GCD not commutative: gcd({}, {}) != gcd({}, {})",
b_str, a_str, a_str, b_str
);
let result_b = b.gcd_ref_l(&a);
assert_eq!(result_rev, result_b);
}
}
#[test]
fn test_gcd_verified_batch_2() {
let test_cases = [
("14109945323656010954628143155346032641103291092518504228313399053945366081315806119605474991210089783185815928191156418374951073517388633710938357836916584310246727965359468107364878390092876872502570723850315379665849592096948254370290040778285660470703477319571191374279228718256932162440272775145812126036393453470258979287954546533449325613807639663195655121145176455477974172907070404610411419970584224508463562863274525343403811235290144348600255237825367248726922144075062145270127444296107970156632514797360764536261623", "73934447555526617447693943855883664374913499610396975512879710321092364466189612887645968400626502129016221968802910711043766156849627320610865165102668071061759581089087173683392136393839567896262126894359508759921445204149836783566247545039262188640810607323973435787745676840245106016", "1"),
("25041182538096607145226517284058700875634955587029938705804650260347434218205867473463072720052846949577463150908653325619840194199823313179650584657905206478724827", "3649128615638321789179982503383665734270623874075304447145596692621847780200619737902358441636719745308574925776267529863157219294783739924306452936973518202475377395087431277333807", "1"),
("51992675445828589817457777716399271718655865636046627565814461844884724673817872890457799755896373646204770002583375997949170255035136523698309764790447547373607055233183586213246610489517413631831640835678547463579120178823380492631066803001921438931749971201643228846420983900489120831985025757309397909850517727888083193430305656337760887369521332791999869466740076097325071206969519647079672348477204678266527077648243527127907511163136542650227295803227444017730575055967256373192095518779771621772296690186024974685473614493190417985721876167259970369", "6696969212402194459053619187636759956529599093426794715324510082927901083563049905160366154911308266057257206821702062196927919872816375411336054110993673424058313620", "1"),
("978308804945982113747869823242174428651504080616486825443418588930360582795476061483213670525736324294203830760180375519781569277331299734447366435231037328638761814602475025914494058854584820969420818044158234687938910082572395087560351821677014775007145503343618313543139764414058601716856934360132711220750720618885050123281279886418368019002819701980762495502391312895757413090591093048614057411390694783071926312859862822309356329104200450813462720062524169", "20918634097694614483224994643952097597253249512251254004776387550698206380267846740170551287962948882387844552608941287722453248513615781087687962544331315046053668214693872427714690939887657322142395015442240591630417835708248557094110574598098587276944342474225495611616159685292315952566620755857277349692893538975286211561654661859188512986000510096506517493855655687096860199061062977735463214110097333853668059059807788320360363632368613124556003842004470030072433071868735377914589702879647744863368488840262734266130", "1"),
("1274104931524439799584902311204411844737259712218291669991599689719180355321321595859448870838376856976548303652277352915608720410510026256122751346353193441485346080443671703748196662130758790433536518946578764101463404164206941734959743328657659321779185749299887503716748682966466237846574891503784159435820055077557778800294249557183949948721986732108645900725470925599139135992035944084638623375536377235203377216653493040814660713051261862392944229906044510158614151450183083385612769791801987950922452864638227955912101906239021673149403697", "24487414963906529601430290406222270434175530495437864205223787355867460395919478214617493986255538764815673685872961997375548748586504732986090621373355407739613672234529062261617665712243168855389733269577252004704719600267288071484320670489347913690921889506789453931712676051017758896844268068995706679096504633838906285104435507458037455266788115990847014111782658795929197022599294502385644496134522411413046957763150711658081488405701635261707555571740155199428202185163741080583763122698", "1"),
("44907430814177916584426402257928324914345335879143626377047546435223859860498692482934556039445925133078565211764714069357295236513759683617508788366536560012505256005155321302549083950991225050649281464364647938718103693218985280633205666699111075264387214286293975061241029312773243118867161496372754353474771121312900964638759807637449083367482011745833784170230291742625194794304204828409053864508019934835839", "894807264", "3"),
("138997866280112809603213381631934990704207175033296126543978363823984001031998637720543620222949528313934218524759406989711601801596947655733981645312311348562389094120326094461156036147700586229747024943910144441994937056234144893192902112209154893149720452250230516800592710867482309619323955079853674566023348016685349084434055982861324544589828247132976768500977147390574443863845173564355874939494939160799970316150993", "429979714", "1"),
("53593883463707865180583280392928239721482143836090040118870722583578341711332150240171173922163729166723034274446173677921356821417415978296957621726006039371190965686946738934754057113429140087793089138095684647636525428732655585554130597153547381896984850037405459803381480958540831322746949984614889419616060034425765028498099187759596475468829330953653193087001014495010756845119366978705", "498165816", "1"),
("14017677292479237072738949485216930706822750995035021540931558233968029238193443362828943152387267052606952519008890811531003595291977305994538601257093069997879735203706689807294362344374196331838316902208841320481289598344409704439567652443067433358698103592979998761004327667992417510342532137000520076803166115612654773487582757908347834252725255152261933958327798483395490215763084002760717453493276700885907759820056505230354820682472", "927981408", "8"),
("1451487767798250846285258475572150801781273906115894678123506277635534079912928838570366089075841089873871358779985645926305038365939763695592232929744950246136628156876704059700128500501090615436112804641907608070666592034032926500237800813615613019539203030423805267768516436266940183387857146682946969072537075053809879669794078897703395958770516476785007781744278907742700664597673294325067537986839", "561296426", "1"),
("5041322386149101841037285676089350178194499053455945037422315926726311391780676752506664440215869201812917685465932207428229917989792302325374226701262499559787694730148624359481722222602710928706391684757519283441684727167619500260425458701914279146940728941129600328503086505641280642965322863801908402429385272813420330340270033071323989044763949349376126724078191567371186811415424628486138407947017142633278057808828749946084781159723160", "749987148", "12"),
("39096435697558437978696425476735214112160007110734513842343087407934543314936622250283558310743600558986456447546407031795184704091854277148480834451556601445833462311469734997633168129118851697521342954966648745525696332048561624304018550996004287538974683368165638104986438266086562870840153915222877628630849745275952493821574761", "906698074", "1"),
("15274273425721310546961401966064654485012327118993322520839028066346109759555605085020652871480207974078738636115828167941885582154580024143593919165271562556906936648049454414822365905593230772382667620749097466746515147688068282373635725331716344653266569724166838148715709458346894943677809282269087628857965382", "476954731", "11"),
("38085036634036062122680299170366871443063234331604958007743259748223229857851939292774148272204025105090935439426206468841676515555894833520764918612177572627326848147417646487119789924855782783625488432952524210737953611740174619001163454927406854711907969485888541290810519017730524619899693389527370", "860345543", "1"),
("35961583041802171139722828684890343683317617898953526251293770362917271613105335919294069416365281364427337355873877339440911929646456122222234768968044894974170360838516025551928120309961076933529635689130985484752178874756109219875046940171654873971206129547737385905575530217050009204218128775457416944439111028204045339451238581210972538888097913923332252325304784851625207877", "949863986", "1"),
("8058417076812889555766857295647073804999341991074043751355071188083682495258146137849340462906529907639000046452477949258277590362448346696652001033126979320397690459661969764497522171253551380613658219338704832337321463099151970848487195114575429411038783569410819", "20405270", "1"),
("45029022500593477870075330396913187181098952891890079533858261720311642758604543023683912012401176737262305077395931331362917176070566761445404487203713950180604276490711787789812844453837360800564588480828763841025167887205275131671321049371497594916228056970288624171094847786235836918268846974454396225830233861766432234702365417330498524037040239589474574168319854254678288407903891811376824717045183844441624973898226532", "575583373", "1"),
("3097499661433885547723321075017912144085986254910758665360734926334336417946416025635888087491319921992562758749523211163215968767251947048114421704848736889231811082471166613002052929373738528369075164259179689822027953402077970249322321870759399088169741348264", "370228864", "8"),
("1814893378363124710238005809951580789418344710383070493738039706102613545874202211731395719335283748289738778692407859016416802408713390967541915499713552818583035247204924640056689679995696696966802606340422365971410172317112784500073182911687365107712314463773453423535265789426323", "67753685", "1"),
("155073969817720496517263432234013103746457589697981483620143238849509514931924027096512772046107267015073100620691927432944692671357288727407246308558210988465813222041727700889059965493323949035151815922128443769341861312359731555988315879762534764249804", "929643818", "2"),
("198542876903212802255957669924902207327450299149445266245436280919472924255368953113204990830254779384046070135645724518591279630035432572803418133417887179860773863946248863985671531347489693045379859392511089183793652758119998634978424792100313349731424395067701759582828537333219364065027137533100046084228000005940321324931865899544827626622984605655700608525704906034", "84747225", "1"),
("119689393627777600119190967088942908045603712177878788888067147812646379663784080167169049800498005697516202574339538672370190878457999571195612044555303377570595163848138695415471780030078380687529500098342919007564790775624776265804387910700544139823692942548352380371875278710551931454958014148107992038394245467398288313485375773086244180590302377994811488203166203473185249835796948699370775367514678729003769541329305967943288485215", "436164914", "1"),
("497829461622075691477845333828992700526921382314473714004028391186651267573819032332306682385880104986900489215717641488377676501686063828487923356361660117283552056398128622584681744831048051191867058398587504578407508702500800978104486940667561778772869635412461029552369675", "27824236", "1"),
("230562425030396345435067214913478484608123185757865454749968411878623828251565646159296651587441589348310525288111582203603886204785974722627847558372576600202031889433762506217116106520257296470055958288523542692107964513559731862467945136529405190021018277996337522897185609285131272057212358397164969841859625786004507936826281421163329257555100388929988927319812591815871299", "94264588", "11"),
("5028408324609045065578787582003173233203209918084924262462904314790313196660103644170976376916403079442553797418524640426333144671216065038269618614926185469210928261319192664652608483802766601454856636179456217393357903419098618023695986161403146393189464142588447725268537604010740859075405392723276977891522604425233455762602425331776178437080497004114451721224240179204115671722999", "862925205", "1"),
];
for (a_str, b_str, expected_str) in test_cases {
let a = Arbi::from_str_radix(a_str, 10).unwrap();
let b = Arbi::from_str_radix(b_str, 10).unwrap();
let expected = Arbi::from_str_radix(expected_str, 10).unwrap();
let result = a.gcd_ref(&b);
assert_eq!(
result, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a_str, b_str, expected_str, result
);
let result_b = a.gcd_ref_l(&b);
assert_eq!(result, result_b);
// Test commutativity
let result_rev = b.gcd_ref(&a);
assert_eq!(
result_rev, expected,
"GCD not commutative: gcd({}, {}) != gcd({}, {})",
b_str, a_str, a_str, b_str
);
let result_b = b.gcd_ref_l(&a);
assert_eq!(result_rev, result_b);
}
}
#[test]
fn test_gcd_verified_batch_3() {
let test_cases = [
("5160746985516828080488874950643837909618925423549186729877177543292093032173668171671995106361967560170905707106050846383038569923490033866777014450643090445670308759166678013809889653079644098714455563095555303533162501529657678607708313419228053620206726845429015699015497133650", "464520347", "1"),
("19528373032072949322064004220271488834628466003584448776477576866688465821605084441149569197505143118559736111964266029064955096237517505698007168243733497177507544869997547550238672540738333962619463613733231252102528983781630442248609226034637477462774774931786653220569866828697640820996229416004273954106728583588622014130480661867355750032196829158599121437807793285247304783828770093114462908864221985670580807211117851636870137", "325155442", "1"),
("738453989829891765514347434250240391696395953159522370402004854595780417197990025643242295869612837171400708379483548641514363788766446839672012959486891975253744117467870502858266627102531548452975518114307903419657269754248269699709822294734123807286227322972511989534902843940133408337124919954499605691822633168069595952816607617", "518558051", "1"),
("445921041907526158970263604153843892504024208272423774107348484610612518700713280993579905299476561888412941715586312488067797826120297148054429791004766594368463643818063971129414350701117714927199323132290926503959298624407035096696486611403561837590749975681955135971615232002928776026294285016847243617733305903690952071769386184785673", "259564055", "1"),
("7491697125162803266776615742844785699321050986507011128143580820853976144055660880361912802574496023842852061714911728215033260717193593502502513118948637644161379378030201503195501788608348515706354676690614103098670699188532563324523781685954279", "96689474", "1"),
("55213970774324510299478046898216203619608871777363092441300193790394368", "12194330274671844653834364178879555881830461494785043558043581873536608354764709453594945715091765512343073949692994620685343654997219864477696", "55213970774324510299478046898216203619608871777363092441300193790394368"),
("248661618204893321077691124073410420050228075398673858720231988446579748506266687766528", "6393341031047152089869511126616404594173128996177860916959553453312761321102879990006386899074031556935325554936640763689877454191182408307282280448", "248661618204893321077691124073410420050228075398673858720231988446579748506266687766528"),
("130370302485407109521180524058200202307293977194619920040712988758680403184853549195737432064", "248661618204893321077691124073410420050228075398673858720231988446579748506266687766528", "248661618204893321077691124073410420050228075398673858720231988446579748506266687766528"),
("10633823966279326983230456482242756608", "65185151242703554760590262029100101153646988597309960020356494379340201592426774597868716032", "10633823966279326983230456482242756608"),
("85070591730234615865843651857942052864", "5043456793138493339171717132818382567050206626619577173497381555743452386751642958261026080625269202023248382759272448", "85070591730234615865843651857942052864"),
("315216049571155833698232320801148910440637914163723573343586347233965774171977684891314130039079325126453023922454528", "803469022129495137770981046170581301261101496891396417650688", "803469022129495137770981046170581301261101496891396417650688"),
("62165404551223330269422781018352605012557018849668464680057997111644937126566671941632", "19701003098197239606139520050071806902539869635232723333974146702122860885748605305707133127442457820403313995153408", "62165404551223330269422781018352605012557018849668464680057997111644937126566671941632"),
("226156424291633194186662080095093570025917938800079226639565593765455331328", "174224571863520493293247799005065324265472", "174224571863520493293247799005065324265472"),
("254629497041810760783555711051172270131433549208242031329517556169297662470417088272924672", "587135645693458306972370149197334256843920637227079967676822742883052256278652110865924749596192175757983744", "254629497041810760783555711051172270131433549208242031329517556169297662470417088272924672"),
("2187250724783011924372502227117621365353169430893212436425770606409952999199375923223513177023053824", "6393341031047152089869511126616404594173128996177860916959553453312761321102879990006386899074031556935325554936640763689877454191182408307282280448", "2187250724783011924372502227117621365353169430893212436425770606409952999199375923223513177023053824"),
("4925250774549309901534880012517951725634967408808180833493536675530715221437151326426783281860614455100828498788352", "14134776518227074636666380005943348126619871175004951664972849610340958208", "14134776518227074636666380005943348126619871175004951664972849610340958208"),
("1353842624082429130653522550851115089568572790710847937094960732721983060451965636249987502980536903367866802227247837807116288", "726838724295606890549323807888004534353641360687318060281490199180639288113397923326191050713763565560762521606266177933534601628614656", "1353842624082429130653522550851115089568572790710847937094960732721983060451965636249987502980536903367866802227247837807116288"),
("10576895500643977583230644928524336637254474927428499508554380724390492659780981533203027367035444557561459392400373732868096", "1461501637330902918203684832716283019655932542976", "1461501637330902918203684832716283019655932542976"),
("46768052394588893382517914646921056628989841375232", "713623846352979940529142984724747568191373312", "713623846352979940529142984724747568191373312"),
("4074071952668972172536891376818756322102936787331872501272280898708762599526673412366794752", "3978585891278293137243057985174566720803649206378781739523711815145275976100267004264448", "3978585891278293137243057985174566720803649206378781739523711815145275976100267004264448"),
("35735732648540721974249770395900151238961362084583185089491946038813478307223909759889439262319932877268813135720", "123767659416897134642523595029702962827622278439288104456289178963695461454287687461080496957303182160296865006640", "871603235330261511567067570631711005828325904502028904621754781434475080663997799021693640544388606762653978920"),
("483596489993662896915390886002450157658051421281195285740191122670995468681200583487949793429625466666684214914976", "247695763167485874029834356245157397824855606022075634159610087221729386397688103737730382000539873170740695444256", "11795036341308851144277826487864637991659790762955982579029051772463304114175623987510970571454279674797175973536"),
("2115635289268765252682750095354732435172397864028891121111546288366636745382778423888701055575798745905801096700232349904678", "1127362749298926812848247455656155000057263913703976583568090409717861795117466703387058693974647082593402660525383328322908", "7320537333109914369144463997767240260112103335740107685507080582583518150113420151864017493341864172684432860554437196902"),
("13984876183891182562519970366734259721396072280831458679024641671977899490739192046857680118462619764495962768122805618086621164778450958", "12796359794325359681852550788824832549606037809372694485339827932149749392376087906898103904428969359581291711341830636379542878819942378", "39617212985527429355580652596980905726334482381958806456160457994271669945436804665319207134455013497155701892699166056902609531950286"),
("10185767763004224204842390369263544532112043757965032309979415741152", "7600937250282046705623592813244403834264515065617122100663031344528", "25592381314080965338799975802169709879678501904434754547686974224"),
];
for (a_str, b_str, expected_str) in test_cases {
let a = Arbi::from_str_radix(a_str, 10).unwrap();
let b = Arbi::from_str_radix(b_str, 10).unwrap();
let expected = Arbi::from_str_radix(expected_str, 10).unwrap();
let result = a.gcd_ref(&b);
assert_eq!(
result, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a_str, b_str, expected_str, result
);
let result_b = a.gcd_ref_l(&b);
assert_eq!(result, result_b);
// Test commutativity
let result_rev = b.gcd_ref(&a);
assert_eq!(
result_rev, expected,
"GCD not commutative: gcd({}, {}) != gcd({}, {})",
b_str, a_str, a_str, b_str
);
let result_b = b.gcd_ref_l(&a);
assert_eq!(result_rev, result_b);
}
}
#[test]
fn test_gcd_verified_batch_4() {
let test_cases = [
("17409072045822577360344135531740660935410875218853424840745063091441458103046816046202114394502625125781043214948645031529319054411386787782380753271250", "2367633798231870521006802432316729887215879029764065778341328580436038302014366982283487557652357017106221877233015724287987391399948603138403782444890", "139272576366580618882753084253925287483287001750827398725960504731531664824374528369616915156021001006248345719589160252234552435291094302259046026170"),
("14763459322781447505459400376786693979751585879712924086299497529012536747472887972414714817706144485963424921691387585205920425586507126121344017488992", "7569400754476928593900794260979618523516702929852812773060335597502190451034828155348222427722218147464298370867194482245408353796471873985943331000712", "62557031028734947057031357528757177880303329998783576636862277665307359099461389713621672956381968160861970007166896547482713667739436975090440752072"),
("1125148525917923331264412285731208486631017857572968247962160573337021379", "1237434224023785333773488053553671248025966686536462024235370080655787260", "2291544859303306173654607506580872681529567938030485230065500149362569"),
("5091625368479315061494277968707720025951574494374642464012145621860341997100993380422340408170035427307749963060828491008", "4807543266375318942183438425389263543816937290825842669882712604331653387820680445033969484109046326213326145379323038720", "21852469392615086100833811024496652471895169503753830317648693656052969944639456568336224927768392391878755206269650176"),
("20837766978058538802035102860143812044417522676338549008858779555118261683513867587453768524981429700734", "53864946665504262066698582883574363814164249794064680607866975908818774482547285168875591187125198997649", "68097277706073656215800989739032065504632427046858003296924116193196933606254469240044995179677874839"),
("218610576827514110494028790114510026095154541884462472529754964457649278037382214847313155770259488699611312", "198249787809265247261741794956786053076488187493262536362767982473848609984880930131141832438715712791314180", "1071620474644677012225631324090735422035071283747365061420367472831614108026383406114280175344409258331428"),
("756780040628908657641111876124082890364371618854724860274640192727557559884031380877812753716698571125829", "612999563042619576618387862887025262572979258173439033909897520769104336044981496461803384777673102045743", "773013320356392908724322651812137783824690111189708743896465978271253891607795077505426714725943382151"),
("9037079274285910275590168458741710377246637274388986575870428385670181353951322044511", "3545005837164160940201789707441027547686645230963881806879335949207916608385065408248", "13428052413500609621976476164549346771540322844560158359391424050029987152973732607"),
("13169148742919171318513037058774787324941788867576010250255247694768938283731845042086964390987387536809887852033799494416361527243205430", "13329097917934383925620482853010918345082782254631589322120696047336982068554499030452393108286829490698267056714371957911297092351422500", "53316391671737535702481931412043673380331129018526357288482784189347928274217996121809572433147317962793068226857487831645188369405690"),
("601441915117409087098286964763389321524835530095977396303728525407100", "481153532093927269678629571810711457219868424076781917042982820325680", "120288383023481817419657392952677864304967106019195479260745705081420"),
("4505624293500098796006316436397966083468340215614176428653274823221210645972222274218919411921224655042250631238296270626099238162468959", "2445338822998388802715969741840849516998910505477616285917260142680546066459951933510601101475559218996293627830773447653898476649775051", "5000692889567257265267831782905622734149101238195534327029161845972486843476384322107568714673945233121254862639618502359710586195859"),
("6233453960882541402138186615809981524446326199552520361438087225059497083672818485345744403999504759035599901288787114981081869416607132", "14318687131901737363070562561002844589627753487675036311420543458400267359566432420313027940567900053182193915512736929391690151923503412", "26081397325868374067523793371589880855423958993943599838653084623679904115785851403120269472801275142408367787819192949711639620989988"),
("141881421432603285128873905695175317623191489135707553147462843849436", "139659896044827659578839345585125599706335672499971004820519271137806", "148101692518375036668970674003314527790387775715769888462904847442"),
("303011058368708763433246909995725159509023607716638006062875327872256", "389416555481660871756008724174193662025268620854585562479242120585829", "1183636946752768607161120742170801404332123467643117211183106749501"),
("76195924420772978778976630821086482082259083928308521661549989510123598007063397834843116593402050888751266", "107359568027555931555817180043415214582711942665582456645181783935034962502457635493205076484921947504921484", "163160437731847920297594498546223730368863134750125314050428243062363164897352029624931727180732443016598"),
("558290227771437963207824999482852679294374691819509898854767874965984160958284608798004953827919061578543200220275541643913607944513864077374746154140665758799526108579085633", "558290227771437963207824999482852679294374691819509898854767874965984160958284608798004953827919061578543200220275541643913607944513864077374746154140665758799526108579085634", "1"),
("51571557994641870573755551853462397288666708682598502847994582959478593360851047939002990209362792400697050498177107340", "51571557994641870573755551853462397288666708682598502847994582959478593360851047939002990209362792400697050498177107341", "1"),
("2892883486959688895458692113687383744604620382925017096307392611824103634592578539298967654453366903057453925022154813938483334104677168257713040649921014346288357882334000842409645400524704039638208140737539654469753469515216783", "2892883486959688895458692113687383744604620382925017096307392611824103634592578539298967654453366903057453925022154813938483334104677168257713040649921014346288357882334000842409645400524704039638208140737539654469753469515216784", "1"),
("233830897421515434716756280227698703750923076792850608242649989070476502933003610853372030835629834661197646383093052242177253050038679786112", "233830897421515434716756280227698703750923076792850608242649989070476502933003610853372030835629834661197646383093052242177253050038679786113", "1"),
("3145813434958539158702427155941051793832294998112834160463987683070335437987658382199637782425193190418194463547908", "3145813434958539158702427155941051793832294998112834160463987683070335437987658382199637782425193190418194463547909", "1"),
("2583536720895424703547288473094956929841276449505623382388362863896449817719551049802341636256087729933057739423879397026294496894134629476661174405243979011477178433892832282754286329229674456944421794593551736757019690030525677317", "2583536720895424703547288473094956929841276449505623382388362863896449817719551049802341636256087729933057739423879397026294496894134629476661174405243979011477178433892832282754286329229674456944421794593551736757019690030525677318", "1"),
("1913280398699967251773695253849718638716538700117539593673241662036635511195811858270215622894296101292126518686777126501230", "1913280398699967251773695253849718638716538700117539593673241662036635511195811858270215622894296101292126518686777126501231", "1"),
("600991079658203554427055450107893523311389442525084842649391174246035165995179221488929167220872875145", "600991079658203554427055450107893523311389442525084842649391174246035165995179221488929167220872875146", "1"),
("13997199015909124522065789230968021506512239533029957226391466582916842101364428369710370261628884528457880378209", "13997199015909124522065789230968021506512239533029957226391466582916842101364428369710370261628884528457880378210", "1"),
("1321467825163101833689628549256546217611088087139902496572567848931565095533084849265923965882269004463049313690820710810362058057977343394949395356902958633226331027874674257108310719641725832113617992225424115200254614715233670", "1321467825163101833689628549256546217611088087139902496572567848931565095533084849265923965882269004463049313690820710810362058057977343394949395356902958633226331027874674257108310719641725832113617992225424115200254614715233671", "1"),
];
for (a_str, b_str, expected_str) in test_cases {
let a = Arbi::from_str_radix(a_str, 10).unwrap();
let b = Arbi::from_str_radix(b_str, 10).unwrap();
let expected = Arbi::from_str_radix(expected_str, 10).unwrap();
let result = a.gcd_ref(&b);
assert_eq!(
result, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a_str, b_str, expected_str, result
);
let result_b = a.gcd_ref_l(&b);
assert_eq!(result, result_b);
// Test commutativity
let result_rev = b.gcd_ref(&a);
assert_eq!(
result_rev, expected,
"GCD not commutative: gcd({}, {}) != gcd({}, {})",
b_str, a_str, a_str, b_str
);
let result_b = b.gcd_ref_l(&a);
assert_eq!(result_rev, result_b);
}
}
#[test]
fn test_gcd_verified_batch_5() {
let test_cases = [
("46677283812833826070676221918252139956950099498923401049074160322952685922559842756871187892287830502680542726386931936601943364682736336256922936684235109327133028735247711342637", "46677283812833826070676221918252139956950099498923401049074160322952685922559842756871187892287830502680542726386931936601943364682736336256922936684235109327133028735247711342638", "1"),
("27196247974170414798450802960811687409678342989834884494663360447533268190144950478139295398960540510814258627007142804075079543036894883931032235781879539652477313940948925316210024602725583291817118789236562", "27196247974170414798450802960811687409678342989834884494663360447533268190144950478139295398960540510814258627007142804075079543036894883931032235781879539652477313940948925316210024602725583291817118789236563", "1"),
("532332866586432904973789037559511667629667770110952418838468592075530286487665972445150120969594004531618001562023413150783647672360519196117413924389503399925393853672816635971964671666788737943906952665567520280771721925896", "532332866586432904973789037559511667629667770110952418838468592075530286487665972445150120969594004531618001562023413150783647672360519196117413924389503399925393853672816635971964671666788737943906952665567520280771721925897", "1"),
("694869366310638839419037350998944462498843978452512689784688787597889043142861087167236990114284176187559272393825982843103606899701311678974135820420515583335737552054495121", "694869366310638839419037350998944462498843978452512689784688787597889043142861087167236990114284176187559272393825982843103606899701311678974135820420515583335737552054495122", "1"),
("49652950893808254508401538584759178666522626233136780433369086495969674851799632974210412657497876790465137910504393371454706682488481194427373456699661154", "49652950893808254508401538584759178666522626233136780433369086495969674851799632974210412657497876790465137910504393371454706682488481194427373456699661155", "1"),
("14551895656707004047323129321847340454932586612041127540082753332658", "29103791313414008094646258643694680909865173224082255080165506665317", "1"),
("14551895656707004047323129321847340454932586612041127540082753332658", "43655686970121012141969387965542021364797759836123382620248259997976", "2"),
("14551895656707004047323129321847340454932586612041127540082753332658", "14551895656707004047323129321847340454932586612041127540082753332881", "1"),
("81326782553190298146056975447742602495300164774916113467512687147811102236313955070207407771813328669399476980997119525387470731062074609262485700318011607193288226191550803153", "162653565106380596292113950895485204990600329549832226935025374295622204472627910140414815543626657338798953961994239050774941462124149218524971400636023214386576452383101606307", "1"),
("81326782553190298146056975447742602495300164774916113467512687147811102236313955070207407771813328669399476980997119525387470731062074609262485700318011607193288226191550803153", "243980347659570894438170926343227807485900494324748340402538061443433306708941865210622223315439986008198430942991358576162412193186223827787457100954034821579864678574652409461", "1"),
("81326782553190298146056975447742602495300164774916113467512687147811102236313955070207407771813328669399476980997119525387470731062074609262485700318011607193288226191550803153", "81326782553190298146056975447742602495300164774916113467512687147811102236313955070207407771813328669399476980997119525387470731062074609262485700318011607193288226191550803396", "1"),
("32629312288429842407082695607812119664013871809052801493961109823355397338237205292565353450821216661305145", "65258624576859684814165391215624239328027743618105602987922219646710794676474410585130706901642433322610291", "1"),
("32629312288429842407082695607812119664013871809052801493961109823355397338237205292565353450821216661305145", "97887936865289527221248086823436358992041615427158404481883329470066192014711615877696060352463649983915437", "1"),
("32629312288429842407082695607812119664013871809052801493961109823355397338237205292565353450821216661305145", "32629312288429842407082695607812119664013871809052801493961109823355397338237205292565353450821216661305751", "1"),
("172218237295197717137960039332996759933711003365649973859823158524627142886174419411449314819737763343760235300678655907120187122764438035567356472327194542888590248075143009", "344436474590395434275920078665993519867422006731299947719646317049254285772348838822898629639475526687520470601357311814240374245528876071134712944654389085777180496150286019", "1"),
("172218237295197717137960039332996759933711003365649973859823158524627142886174419411449314819737763343760235300678655907120187122764438035567356472327194542888590248075143009", "516654711885593151413880117998990279801133010096949921579469475573881428658523258234347944459213290031280705902035967721360561368293314106702069416981583628665770744225429029", "1"),
("172218237295197717137960039332996759933711003365649973859823158524627142886174419411449314819737763343760235300678655907120187122764438035567356472327194542888590248075143009", "172218237295197717137960039332996759933711003365649973859823158524627142886174419411449314819737763343760235300678655907120187122764438035567356472327194542888590248075143436", "1"),
("935495743379731158224399891002744351242571110632602326343558404928949096185305010451225997312163823739624053149546709196824", "1870991486759462316448799782005488702485142221265204652687116809857898192370610020902451994624327647479248106299093418393649", "1"),
("935495743379731158224399891002744351242571110632602326343558404928949096185305010451225997312163823739624053149546709196824", "2806487230139193474673199673008233053727713331897806979030675214786847288555915031353677991936491471218872159448640127590474", "2"),
("935495743379731158224399891002744351242571110632602326343558404928949096185305010451225997312163823739624053149546709196824", "935495743379731158224399891002744351242571110632602326343558404928949096185305010451225997312163823739624053149546709196972", "4"),
("117210821124286395871558708272089657664442509583211084080703627816691652786558449964146814892120273382457011089342747581923017390673", "234421642248572791743117416544179315328885019166422168161407255633383305573116899928293629784240546764914022178685495163846034781347", "1"),
("117210821124286395871558708272089657664442509583211084080703627816691652786558449964146814892120273382457011089342747581923017390673", "351632463372859187614676124816268972993327528749633252242110883450074958359675349892440444676360820147371033268028242745769052172021", "1"),
("117210821124286395871558708272089657664442509583211084080703627816691652786558449964146814892120273382457011089342747581923017390673", "117210821124286395871558708272089657664442509583211084080703627816691652786558449964146814892120273382457011089342747581923017391336", "3"),
("1465427435858034530975257309915454572314503392628684073079873199328920216", "2930854871716069061950514619830909144629006785257368146159746398657840433", "1"),
("1465427435858034530975257309915454572314503392628684073079873199328920216", "4396282307574103592925771929746363716943510177886052219239619597986760650", "2"),
];
for (a_str, b_str, expected_str) in test_cases {
let a = Arbi::from_str_radix(a_str, 10).unwrap();
let b = Arbi::from_str_radix(b_str, 10).unwrap();
let expected = Arbi::from_str_radix(expected_str, 10).unwrap();
let result = a.gcd_ref(&b);
assert_eq!(
result, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a_str, b_str, expected_str, result
);
let result_b = a.gcd_ref_l(&b);
assert_eq!(result, result_b);
// Test commutativity
let result_rev = b.gcd_ref(&a);
assert_eq!(
result_rev, expected,
"GCD not commutative: gcd({}, {}) != gcd({}, {})",
b_str, a_str, a_str, b_str
);
let result_b = b.gcd_ref_l(&a);
assert_eq!(result_rev, result_b);
}
}
#[test]
fn test_gcd_verified_batch_6() {
let test_cases = [
("1465427435858034530975257309915454572314503392628684073079873199328920216", "1465427435858034530975257309915454572314503392628684073079873199328920412", "4"),
("23552760966392138520026622522179399493389774451598806659426567185922", "47105521932784277040053245044358798986779548903197613318853134371845", "1"),
("23552760966392138520026622522179399493389774451598806659426567185922", "70658282899176415560079867566538198480169323354796419978279701557768", "2"),
("23552760966392138520026622522179399493389774451598806659426567185922", "23552760966392138520026622522179399493389774451598806659426567186115", "1"),
("1502522809575174610975661628052607200332551981866312281774165144400286343012428025840513628623068299623368838596883919600966546636460367396186390629245181641996321310565542388341", "3005045619150349221951323256105214400665103963732624563548330288800572686024856051681027257246136599246737677193767839201933093272920734792372781258490363283992642621131084776683", "1"),
("1502522809575174610975661628052607200332551981866312281774165144400286343012428025840513628623068299623368838596883919600966546636460367396186390629245181641996321310565542388341", "4507568428725523832926984884157821600997655945598936845322495433200859029037284077521540885869204898870106515790651758802899639909381102188559171887735544925988963931696627165025", "1"),
("1502522809575174610975661628052607200332551981866312281774165144400286343012428025840513628623068299623368838596883919600966546636460367396186390629245181641996321310565542388341", "1502522809575174610975661628052607200332551981866312281774165144400286343012428025840513628623068299623368838596883919600966546636460367396186390629245181641996321310565542388462", "121"),
("8524551564001360132735894541579644347974340540027493741581281024908793018382881687635702207327060587273323419848462129195904800288576926199805001907491627212113092485151191910", "17049103128002720265471789083159288695948681080054987483162562049817586036765763375271404414654121174546646839696924258391809600577153852399610003814983254424226184970302383821", "1"),
("8524551564001360132735894541579644347974340540027493741581281024908793018382881687635702207327060587273323419848462129195904800288576926199805001907491627212113092485151191910", "25573654692004080398207683624738933043923021620082481224743843074726379055148645062907106621981181761819970259545386387587714400865730778599415005722474881636339277455453575732", "2"),
("8524551564001360132735894541579644347974340540027493741581281024908793018382881687635702207327060587273323419848462129195904800288576926199805001907491627212113092485151191910", "8524551564001360132735894541579644347974340540027493741581281024908793018382881687635702207327060587273323419848462129195904800288576926199805001907491627212113092485151192575", "35"),
("9249432227064849599617900657776121457140334957045141759302577051470499262752881401601590205654893514238791437828941", "18498864454129699199235801315552242914280669914090283518605154102940998525505762803203180411309787028477582875657883", "1"),
("9249432227064849599617900657776121457140334957045141759302577051470499262752881401601590205654893514238791437828941", "27748296681194548798853701973328364371421004871135425277907731154411497788258644204804770616964680542716374313486825", "1"),
("9249432227064849599617900657776121457140334957045141759302577051470499262752881401601590205654893514238791437828941", "9249432227064849599617900657776121457140334957045141759302577051470499262752881401601590205654893514238791437829721", "1"),
("304080511477604908875536974001346814246672005745199257383068122397731543181776575146176693926460041636974683", "608161022955209817751073948002693628493344011490398514766136244795463086363553150292353387852920083273949367", "1"),
("304080511477604908875536974001346814246672005745199257383068122397731543181776575146176693926460041636974683", "912241534432814726626610922004040442740016017235597772149204367193194629545329725438530081779380124910924051", "1"),
("304080511477604908875536974001346814246672005745199257383068122397731543181776575146176693926460041636974683", "304080511477604908875536974001346814246672005745199257383068122397731543181776575146176693926460041636974951", "1"),
("14045687869572843773162890664883102395848098212066479656849356425090146870620993145587535010204106513337816385817032507084751402163605035373318425", "28091375739145687546325781329766204791696196424132959313698712850180293741241986291175070020408213026675632771634065014169502804327210070746636851", "1"),
("14045687869572843773162890664883102395848098212066479656849356425090146870620993145587535010204106513337816385817032507084751402163605035373318425", "42137063608718531319488671994649307187544294636199438970548069275270440611862979436762605030612319540013449157451097521254254206490815106119955277", "1"),
("14045687869572843773162890664883102395848098212066479656849356425090146870620993145587535010204106513337816385817032507084751402163605035373318425", "14045687869572843773162890664883102395848098212066479656849356425090146870620993145587535010204106513337816385817032507084751402163605035373319096", "1"),
("2657020107410398924161467562056974690654835984339963648195652820363687761627287418785351533263838721423998283575179222513448157060426323790993026294976558715510627559", "5314040214820797848322935124113949381309671968679927296391305640727375523254574837570703066527677442847996567150358445026896314120852647581986052589953117431021255119", "1"),
("2657020107410398924161467562056974690654835984339963648195652820363687761627287418785351533263838721423998283575179222513448157060426323790993026294976558715510627559", "7971060322231196772484402686170924071964507953019890944586958461091063284881862256356054599791516164271994850725537667540344471181278971372979078884929676146531882679", "1"),
("2657020107410398924161467562056974690654835984339963648195652820363687761627287418785351533263838721423998283575179222513448157060426323790993026294976558715510627559", "2657020107410398924161467562056974690654835984339963648195652820363687761627287418785351533263838721423998283575179222513448157060426323790993026294976558715510628119", "1"),
("2867515490111205111122030021136053916788612828523195239484698521019552873578343320943764003523226218542459235739981931741259664692461857", "5735030980222410222244060042272107833577225657046390478969397042039105747156686641887528007046452437084918471479963863482519329384923715", "1"),
("2867515490111205111122030021136053916788612828523195239484698521019552873578343320943764003523226218542459235739981931741259664692461857", "8602546470333615333366090063408161750365838485569585718454095563058658620735029962831292010569678655627377707219945795223778994077385573", "1"),
("2867515490111205111122030021136053916788612828523195239484698521019552873578343320943764003523226218542459235739981931741259664692461857", "2867515490111205111122030021136053916788612828523195239484698521019552873578343320943764003523226218542459235739981931741259664692462542", "1"),
];
for (a_str, b_str, expected_str) in test_cases {
let a = Arbi::from_str_radix(a_str, 10).unwrap();
let b = Arbi::from_str_radix(b_str, 10).unwrap();
let expected = Arbi::from_str_radix(expected_str, 10).unwrap();
let result = a.gcd_ref(&b);
assert_eq!(
result, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a_str, b_str, expected_str, result
);
let result_b = a.gcd_ref_l(&b);
assert_eq!(result, result_b);
// Test commutativity
let result_rev = b.gcd_ref(&a);
assert_eq!(
result_rev, expected,
"GCD not commutative: gcd({}, {}) != gcd({}, {})",
b_str, a_str, a_str, b_str
);
let result_b = b.gcd_ref_l(&a);
assert_eq!(result_rev, result_b);
}
}
#[test]
fn test_gcd_verified_batch_7() {
let test_cases = [
("72057594037927935", "178405961588244985132285746181186892047843327", "127"),
("1125899906842623", "5070602400912917605986812821503", "3"),
("147573952589676412927", "1361129467683753853853498429727072845823", "1"),
("604462909807314587353087", "288230376151711743", "1"),
("1393796574908163946345982392040522594123775", "590295810358705651711", "1"),
("2251799813685247", "151115727451828646838271", "1"),
("20769187434139310514121985316880383", "324518553658426726783156020576255", "63"),
("158456325028528675187087900671", "144115188075855871", "1"),
("680564733841876926926749214863536422911", "2722258935367507707706996859454145691647", "1"),
("43556142965880123323311949751266331066367", "340282366920938463463374607431768211455", "1"),
("254009469304496138953700587030105277296317930631505651980435390141779398577740762734149733914274815265007714519763866635394129827552823040823903807668577372235454805517130192828433482793173310401", "214795229656467036569041495335763506287851318108798188479136522677818011630098676729545624269195276343510698499623303241878637299504592178828316729660428321692637226294714091396301476466582946201", "1"),
("215258701546227201372660350417770904843165471954991098358768847433090810511934065464202525562529863317236835311945818184933162378329358873714186854749463468917489239450172196875460689", "455695316875697125171786528040066496948333874588994584849356459543566690956027306731956841151333906666270555874359020390405797401701507439811223732562622389930181368349761290697667185", "1"),
("33843041840437345127931576916779479906804566896154769921989925245414799974226730490165213020807315444283981392025329480821578988063073", "228579654140629741077530330678840591118649845265206700031637760129071591749237643029343793968580294084937471357118585246875794693010349", "3"),
("107388682404147565039290006354780850021278551388457073208763521218793538598801933985894049223999409316975954367667555719235", "489012970003129991003652518615934785280500181543412290523812092213116465994969326074390910711797313438852775952657500049559", "1"),
("463496215161111214368858849694768278557794457947475156889430350431518569436731381686053156298348820039840462353398361975455484900516732736795", "6051959972391486057369329734663075045884269688612673482119817255244517953809069276629011815588370985315774489543693759952346210840992935908873", "1"),
("327510004372764619246237393013636443920005123594289959348475789998876973166647475731721033638537870667043757197543634538397708688410724538265842863997008486187795271638022669065678749184047", "3392185408223017696595659026519017326213976568691756148765753068148178423140672366985931247026353788476991445478767863253707897296024372049844684940472993270567396455296066218443873800188273", "1"),
("537102413751187269024250887229779521191517772195826725567820847994538057473777873709953450799931087002181056479024820387600334655315040105639956626492032946001565", "880143269911545843233976937740495261256925021035908195339842261562397303912607740746733053668169677028941034236873296433711754294894235025448943241048774049097195", "5"),
("23118760914975734426995100801500295293720302235271555385339740797900472410837676207694985957953658085258162673864880593811936357194249612686690155963246968741", "7429359858224959927192748452822869883694606807147389471196063630074710270406953732015642650940014241739246838677520434493195806984850136749346991041186402373", "1"),
("114921753328512263819670301904737002001840727464995508374418087635642055121917383426013619333270656945923707345236995182800914374600297033523255340961993282893286965661", "81987333965449898898026751255520019225178583180981034672686234883987388373498014928232503187531626831228156649402796901763792692081598436641700933325316682256361333367", "1"),
("48546490056090369940134548532773210926775734966714629552583238606677429082868907320803715674619782248555843759010654393011017412162791327361733874444292231406562708396580871160667243830961008542259814436339392640624555", "26725162656304485460637922065549976698036261211136442221918059995577638425068059844634563126464647526600658556597547510545688756800005010195851711475317939892039229817234601612155453787211659218785312405174124892387657", "1"),
("25360957360521529731570315604445803331033947304169828597528912029493522799708326007174253620910220192392824654409240495417190896546809929835669768838591790911", "2345218696179829097449865680057050482098497883916866512877458554105894420016668152048018070528683065500099391539622425164621287131416697333026175433186398837", "1"),
("37538853239316770929284524710836375553800208077422140726715343796392066140403551710762337625697574104237337541270132596388305557708745775", "51982631733347687458442023120664986810841917670302449780976085939484591182518638109662422806135945034161145139900814565937463222163533615", "5"),
("632352421941981930847427929918761672508690312644854794303286652480502435246435451197327021958038397200456562040598573728047932288851604730858266053271397759051389946950790175510326832662570480409572042619930189", "209688400472536745714366116155727993388573994382787016340380369239241458162416793726386394973591578235953158878953431518227148155587145547241210845834278380567107647138762751843465943478531993937666340363605123", "21"),
("41253812563752872998630386524967195895066869722676952538979346692636103728946321386758252138807764880176027872551665028699793529707", "35390500812472426298822243580318104711179541430067851247116043098419074569518024322771712687986983387382912342211024928798087898809", "1"),
("114086372955833530668085580081621444462520063251745848832044727399885640387081351486131161354740109761651293310543015594889487381808343296855597024483247398252350437633106026266360037", "139345853243257457072391197982854074402522139287819252356826881137801054283084041214194289464121571898558496773246222132622620824698551552407513158311889471444170846447345096987658941", "1"),
];
for (a_str, b_str, expected_str) in test_cases {
let a = Arbi::from_str_radix(a_str, 10).unwrap();
let b = Arbi::from_str_radix(b_str, 10).unwrap();
let expected = Arbi::from_str_radix(expected_str, 10).unwrap();
let result = a.gcd_ref(&b);
assert_eq!(
result, expected,
"GCD mismatch: gcd({}, {}) expected {} got {}",
a_str, b_str, expected_str, result
);
let result_b = a.gcd_ref_l(&b);
assert_eq!(result, result_b);
// Test commutativity
let result_rev = b.gcd_ref(&a);
assert_eq!(
result_rev, expected,
"GCD not commutative: gcd({}, {}) != gcd({}, {})",
b_str, a_str, a_str, b_str
);
let result_b = b.gcd_ref_l(&a);
assert_eq!(result_rev, result_b);
}
}
}