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