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