1#!/usr/bin/env python
2
3import polypy
4import polypy_test
5
6polypy_test.init()
7
8def check_gcd_single(p, q):
9    global polypy_test
10    gcd = p.gcd(q)
11    ok = polypy_test.sympy_checker.check_gcd(p, q, gcd)
12    polypy_test.check(ok)
13
14def check_gcd(p, q):
15    check_gcd_single(p, q)
16    check_gcd_single(p, -q)
17    check_gcd_single(-p, q)
18    check_gcd_single(-p, -q)
19
20def check_extended_gcd_single(p, q):
21    global polypy_test
22    (gcd, u, v) = p.extended_gcd(q)
23    ok = polypy_test.sympy_checker.check_extended_gcd(p, q, gcd, u, v)
24    polypy_test.check(ok)
25
26def check_extended_gcd(p, q):
27    check_extended_gcd_single(p, q)
28    check_extended_gcd_single(p, -q)
29    check_extended_gcd_single(-p, q)
30    check_extended_gcd_single(-p, -q)
31
32polypy_test.start("GCD in Z_13 (Knuth)")
33
34# Example from Knuth (p 424)
35K = polypy.CoefficientRing(13)
36x = polypy.x.to_ring(K);
37
38p = x**8 + x**6 + 10*x**4 + 10*x**3 + 8*x**2 + 2*x + 8
39q = 3*x**6 + 5*x**4 + 9*x**2 + 4*x + 8
40check_gcd(p, q)
41
42polypy_test.start("Regressions (modular)")
43
44K = polypy.CoefficientRing(7);
45x = polypy.x.to_ring(K)
46
47p = 2*x
48q = 4*x
49check_gcd(p, q)
50
51p = 1*x**4 + 2*x**2 + (-2*x)
52q = 1*x**4 + 1*x**2 + 1*x + 3
53check_gcd(p, q)
54
55p = (-2*x**2) + 1*x
56q = (-2*x**2) + (-1*x)
57check_gcd(p, q)
58
59p = x
60q = x + 1
61check_extended_gcd(p, q)
62
63p = 1*x**2 + 1*x + (-2)
64q = 1*x**2 + (-3*x) + 2
65check_extended_gcd(p, q)
66
67p = 1*x**3 + (-2*x**2) + 1*x + (-1)
68q = 1*x**3 + (-1*x**2) + (-1*x) + (-2)
69check_extended_gcd(p, q)
70
71K = polypy.CoefficientRing(11);
72x = polypy.x.to_ring(K)
73
74p = 1*x**6 + (-3*x**5) + 3*x**4 + (-4*x**3) + 1*x**2 + (-1)
75q = 1*x**6 + (-3*x**5) + 3*x**4 + (-5*x**3) + (-4*x**2) + (-5*x) + (-2)
76check_gcd(p, q)
77
78polypy_test.start("Random (modular)")
79
80for prime in [7, 11, 13]:
81    K = polypy.CoefficientRing(prime)
82    for d in range(1, 10):
83        gcd_gold = polypy_test.random_upolynomial(K, d, 20, 1)
84        tmp = polypy_test.random_upolynomial(K, d, 20);
85        p = tmp*gcd_gold
86        q = (tmp-1)*gcd_gold
87        check_gcd(p, q)
88    for d in range(1, 10):
89        p = polypy_test.random_upolynomial(K, d, 20, 20)
90        q = polypy_test.random_upolynomial(K, d, 20, 20)
91        check_gcd(p, q);
92
93polypy_test.start("Random extended (modular)")
94
95for prime in [7, 11, 13]:
96    K = polypy.CoefficientRing(prime)
97    for d in range(1, 10):
98        p = polypy_test.random_upolynomial(K, d, 20, 20)
99        q = polypy_test.random_upolynomial(K, d, 20, 20)
100        d = polypy_test.random_upolynomial(K, 1, 20, 20)
101        check_extended_gcd(p*d, q*d);
102
103polypy_test.start("Regressions (Z)")
104
105x = polypy.x
106
107p = 5*x**6 + (-89*x**5) + 297*x**4 + 91*x**3 + (-298*x**2) + 12*x + 10
108q = 5*x**6 + (-89*x**5) + 297*x**4 + 90*x**3 + (-284*x**2) + 2*x + 8
109check_gcd(p, q)
110
111p = x**2 + 2*x + (-63)
112q = x**2 + 1*x + (-72)
113check_gcd(p, q)
114
115check_gcd(6*p, 9*q)
116
117p = 3*(x + 1)
118q = 6 + x - x
119check_gcd(p, q)
120
121polypy_test.start("Random (Z)")
122
123for d in range(1, 10):
124    gcd_gold = polypy_test.random_upolynomial(polypy.Z, d, 20)
125    tmp = polypy_test.random_upolynomial(polypy.Z, d, 20);
126    p = tmp*gcd_gold
127    q = (tmp-1)*gcd_gold
128    check_gcd(p, q)
129for d in range(1, 10):
130    p = polypy_test.random_upolynomial(polypy.Z, d, 20, 20)
131    q = polypy_test.random_upolynomial(polypy.Z, d, 20, 20)
132    check_gcd(p, q);
133
134