1#!/usr/bin/env python
2
3import polypy
4import polypy_test
5
6polypy_test.init()
7
8x = polypy.Variable("x");
9y = polypy.Variable("y");
10z = polypy.Variable("z");
11
12polypy.variable_order.set([z, y, x])
13
14def check_gcd(p, q, expected):
15    gcd = p.gcd(q)
16    ok = gcd == expected
17    if (not ok):
18        print("p = {0}".format(p))
19        print("q = {0}".format(q))
20        print("expected = {0}".format(expected))
21        print("gcd = {0}".format(gcd))
22    polypy_test.check(ok)
23
24def check_lcm(p, q, expected):
25    gcd = p.lcm(q)
26    ok = gcd == expected
27    if (not ok):
28        print("p = {0}".format(p))
29        print("q = {0}".format(q))
30        print("expected = {0}".format(expected))
31        print("gcd = {0}".format(gcd))
32    polypy_test.check(ok)
33
34polypy_test.start("GCD")
35
36# polypy.trace_enable("coefficient::gcd")
37# polypy.trace_enable("polynomial")
38# polypy.trace_enable("coefficient")
39# polypy.trace_enable("coefficient::order")
40# polypy.trace_enable("coefficient::reduce")
41
42polypy.variable_order.set([z, y, x])
43
44# p = ((1*z**68)*y**71 + (-2*z**48)*y**52 + (26896*z**118 + 26896*z**116 + 6724*z**114)*y**48 + (1*z**28)*y**33 + (-172200*z**59 - 86100*z**57)*y**24 + 275625)
45# q = ((-328*z**129 + 164*z**127 + 82*z**125)*y**95 + (656*z**109 - 328*z**107 - 164*z**105)*y**76 + (4410944*z**177 + 6616416*z**175 + 3308208*z**173 + 551368*z**171)*y**72 + (-525*z**68)*y**71 + (-328*z**89 + 164*z**87 + 82*z**85)*y**57 + (1050*z**48)*y**52 + (-42361200*z**118 - 42361200*z**116 - 10590300*z**114)*y**48 + (-525*z**28)*y**33 + (135607500*z**59 + 67803750*z**57)*y**24 - 144703125)
46# p.gcd(q)
47
48# Wrong gcd
49p = 4*z**4 + 4*z**2 + 1
50q = 2*z**2 + 1
51expected = 2*z**2 + 1;
52check_gcd(p, q, expected)
53
54# Wrong gcd
55p = 172200*z**39 + 86100*z**37
56q = 26896*z**78 + 26896*z**76 + 6724*z**74
57expected = 328*z**39 + 164*z**37
58check_gcd(p, q, expected)
59
60p = x*y + 1
61q = x*z + 1
62expected = 1
63check_gcd(p, q, expected)
64
65p = ((-1*z**23)*y**24 + (1*z**3)*y**5)
66q = ((1*z**68)*y**71 + (-2*z**48)*y**52 + (26896*z**118 + 26896*z**116 + 6724*z**114)*y**48 + (1*z**28)*y**33 + (-172200*z**59 - 86100*z**57)*y**24 + 275625)
67expected = 1
68check_gcd(p, q, expected)
69
70p = (1*z**68)*y**71 + (-2*z**48)*y**52 + (26896*z**118 + 26896*z**116 + 6724*z**114)*y**48 + (1*z**28)*y**33 + (-172200*z**59 - 86100*z**57)*y**24 + 275625
71q = (328*z**106)*y**71 + (-328*z**86)*y**52
72expected = 1
73check_gcd(p, q, expected)
74
75# An improved EZ-GCD algorithm for multivariate polynomials, Example 2
76p = y**4*z**2*x**4 + (y**2*z**2 + y**3*z**2 + 2*y**2*z**4 + y**3*z**4 + y**4*z**4)*x**3 + (2*y**2*z + y**3*z + 2*z**4 + 3*y*z**4 + 2*y**2*z**4 + y**3*z**4)*x**2 + (2*z + 2*y*z + 2*y*z**3 + y**2*z**3 + y**3*z**3)*x + 2*y
77q = y**2*z*x**5 + (2*z**3 + y*z**3 + y**2*z**3)*x**4 + (2 + 2*y**7*z**6)*x**3 + (4*y**5*z**5 + 4*y**5*z**8 + 2*y**6*z**8 + 2*y**7*z**8)*x**2 + (4*y**5*z**5 + 8*y**3*z**7 + 4*y**4*z**7 + 4*y**5*z**7)*x + 8*y**3*z**4
78expected =  ((1*z)*y**2)*x**2 + ((1*z**3)*y**2 + (1*z**3)*y + (2*z**3))*x + 2
79check_gcd(p, q, expected)
80
81# polypy.trace_enable("polynomial")
82# polypy.trace_enable("coefficient")
83# polypy.trace_enable("coefficient::reduce")
84
85p = ((1*z**4)*y**5 + (2*z**4))
86q = ((1*z**7)*y**8 + (1*z**7)*y**7 + (2*z**7)*y**3 + (2*z**7)*y**2)
87expected = y**5*z**4 + 2*z**4
88check_gcd(p, q, expected)
89
90p = (1*z)*x**2 + ((1*z**4)*y**3 + (1*z**4)*y**2)*x + ((1*z**6)*y**4)
91q = ((1*z**4)*y**5 + (2*z**4))*x**2 + ((1*z**7)*y**8 + (1*z**7)*y**7 + (2*z**7)*y**3 + (2*z**7)*y**2)*x + ((1*z**9)*y**9 + (2*z**9)*y**4)
92expected = y**4*z**6 + x*y**3*z**4 + x*y**2*z**4 + x**2*z
93check_gcd(p, q, expected)
94
95p = ((1*z**5)*y**3 - 1*y**2 + (1*z)*y)*x**3 + ((1*z**8)*y**6 + (1*z**8)*y**5 + (1*z**4 - 1*z**3)*y**4 + (1*z**4)*y**3 + (2*z**3))*x**2 + ((1*z**6)*y**8 + (1*z**10 + 1*z**6)*y**7 + (-1*z**5)*y**6 + (1*z**6)*y**5 + (2*z**6)*y**3 + (2*z**6)*y**2)*x + ((1*z**8)*y**9 + (2*z**8)*y**4)
96q = ((1*z**7 + 1*z)*y**9 + (-2*z**2)*y**8 + (1*z**3)*y**7 + (-2*z**11)*y**6 + (6*z**6)*y**5 + (-2*z**7)*y**4 + (4*z**6))*x**2 + ((1*z**10 + 1*z**4)*y**12 + (1*z**10 - 2*z**5 + 1*z**4)*y**11 + (1*z**6 - 2*z**5)*y**10 + (-2*z**14 + 1*z**6)*y**9 + (-2*z**14 + 6*z**9)*y**8 + (-2*z**10 + 6*z**9)*y**7 + (-2*z**10)*y**6 + (4*z**9)*y**3 + (4*z**9)*y**2)*x + ((1*z**12 + 1*z**6)*y**13 + (-2*z**7)*y**12 + (1*z**8)*y**11 + (-2*z**16)*y**10 + (6*z**11)*y**9 + (-2*z**12)*y**8 + (4*z**11)*y**4)
97expected = y**4*z**5 + x*y**3*z**3 + x*y**2*z**3 + x**2
98check_gcd(p, q, expected)
99
100# An improved EZ-GCD algorithm for multivariate polynomials, Example 1
101p = (x**2 + (y**2*z**3 + y**3*z**3)*x + y**4*z**5)*(x**3 + y**4*z**2*x + 2*y**3*z**4)
102q = (x**2 + (y**2*z**3 + y**3*z**3)*x + y**4*z**5)*(x**2 + y**3*z**3*x + y**5*z)
103expected = y**4*z**5 + x*y**3*z**3 + x*y**2*z**3 + x**2
104check_gcd(p, q, expected)
105
106p = (1*z**6)*y**6 + (-1*z)*y**5 + (1*z**2)*y**4
107q = (-1*z**9)*y**12 + (-2*z**9)*y**7
108expected = y**4*z
109check_gcd(p, q, expected)
110
111p = (2*z**11 - 2*z**5)
112q = (1*z**5)
113expected = (2*z**11 - 2*z**5)
114check_lcm(p, q, expected)
115