zippel-gcd 0.5.0

Sparse multivariate polynomial GCD, cofactors and LCM over the rationals.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

use polycore::{Order, Ring};
use zippel_gcd::{
    gcd, gcd_with_algorithm, gcd_with_report, hu_monagan, hu_monagan_bivariate, huang_gao,
    huang_monagan, zippel, GcdAlgorithm,
};

#[test]
fn named_algorithms_recover_the_same_normalized_gcd() {
    let ring = Ring::new(["x", "y", "z"], Order::GRevLex);
    let h = ring.parse("(2*x+y+1)^2").unwrap();
    let a = &h * &ring.parse("-2/7*x^2*y*(x+z+2)").unwrap();
    let b = &h * &ring.parse("3/11*x*y^2*(y+z+3)").unwrap();
    let expected = (&h * &ring.parse("x*y").unwrap()).primitive();
    assert_eq!(gcd(&a, &b), expected);
    let (value, report) = gcd_with_report(&a, &b, GcdAlgorithm::HuangGao);
    assert_eq!(value, expected);
    assert_eq!(report.attempted, vec![GcdAlgorithm::HuangGao]);
    assert_eq!(zippel(&a, &b), expected);
    for algorithm in [huang_gao, huang_monagan, hu_monagan, hu_monagan_bivariate] {
        assert_eq!(algorithm(&a, &b).unwrap(), expected);
        assert_eq!(algorithm(&b, &a).unwrap(), expected);
    }
}

#[test]
fn direct_recovery_declines_while_aggregate_apis_fall_back() {
    let ring = Ring::new(["x"], Order::Lex);
    let f = ring.parse("x^65537+1").unwrap();
    for (direct, selected) in [
        (huang_gao as fn(_, _) -> _, GcdAlgorithm::HuangGao),
        (huang_monagan, GcdAlgorithm::HuangMonagan),
        (hu_monagan, GcdAlgorithm::HuMonagan),
        (hu_monagan_bivariate, GcdAlgorithm::HuMonaganBivariate),
    ] {
        assert!(direct(&f, &f).is_none(), "{selected:?} must not fall back");
        assert_eq!(gcd_with_algorithm(&f, &f, selected), f);
        let (value, report) = gcd_with_report(&f, &f, selected);
        assert_eq!(value, f);
        let expected = if selected == GcdAlgorithm::HuangGao {
            vec![selected, GcdAlgorithm::HuangMonagan, GcdAlgorithm::Zippel]
        } else {
            vec![selected, GcdAlgorithm::Zippel]
        };
        assert_eq!(report.attempted, expected);
    }
    assert_eq!(gcd(&f, &f), f);
    assert_eq!(zippel(&f, &f), f);
    assert_eq!(
        gcd_with_report(&f, &f, GcdAlgorithm::Zippel).1.attempted,
        vec![GcdAlgorithm::Zippel]
    );
}

#[test]
fn named_algorithms_preserve_zero_and_constant_conventions() {
    let ring = Ring::new(["x", "y"], Order::Lex);
    let zero = ring.parse("0").unwrap();
    let f = ring.parse("-6*x+12*y").unwrap();
    let constant = ring.parse("15").unwrap();
    for algorithm in [huang_gao, huang_monagan, hu_monagan, hu_monagan_bivariate] {
        assert_eq!(algorithm(&zero, &zero), Some(zero.clone()));
        assert_eq!(algorithm(&zero, &f), Some(f.primitive()));
        assert_eq!(algorithm(&f, &zero), Some(f.primitive()));
        assert_eq!(algorithm(&constant, &f), Some(ring.parse("1").unwrap()));
    }
    assert_eq!(zippel(&zero, &zero), zero);
    assert_eq!(zippel(&zero, &f), f.primitive());
    assert_eq!(zippel(&f, &zero), f.primitive());
    assert_eq!(zippel(&constant, &f), ring.parse("1").unwrap());
}