1#!/usr/bin/env python
2
3import polypy
4import polypy_test
5
6polypy_test.init()
7
8def check_factorization(p, p_factors, expected_size):
9    mul = 1
10    for (factor, multiplicity) in p_factors:
11        mul = mul * (factor**multiplicity)
12    ok = (p == mul) and (expected_size == len(p_factors))
13    if (not ok):
14        print("p = {0}".format(p))
15        print("p_factors = {0}".format(p_factors))
16        print("expected_size = {0}".format(expected_size))
17        print("mul = {0}".format(mul))
18    polypy_test.check(ok)
19
20polypy_test.start("Square-Free Factorization")
21
22# polypy.trace_enable("polynomial")
23# polypy.trace_enable("factorization")
24# polypy.trace_enable("coefficient::gcd")
25#
26# x00 = polypy.Variable("x00")
27# x01 = polypy.Variable("x01")
28# x10 = polypy.Variable("x10")
29# x11 = polypy.Variable("x11")
30# x20 = polypy.Variable("x20")
31# x21 = polypy.Variable("x21")
32# x30 = polypy.Variable("x30")
33# x31 = polypy.Variable("x31")
34#
35# polypy.variable_order.set([x31, x30, x21, x20, x11])
36# p = (16*x30**4 + (32*x31**2)*x30**2 + (16*x31**4))*x20**8 + ((64*x30**4 + (128*x31**2)*x30**2 + (64*x31**4))*x21**2 + ((-64*x31)*x30**4 + (-128*x31**3)*x30**2 + (-64*x31**5))*x21 + (-32*x30**6 + (-32*x31**2)*x30**4 + (32*x31**4 - 128*x31**2)*x30**2 + (32*x31**6 - 128*x31**4)))*x20**6 + ((96*x30**4 + (192*x31**2)*x30**2 + (96*x31**4))*x21**4 + ((-192*x31)*x30**4 + (-384*x31**3)*x30**2 + (-192*x31**5))*x21**3 + (-32*x30**6 + (96*x31**2 - 128)*x30**4 + (288*x31**4 - 384*x31**2)*x30**2 + (160*x31**6 - 256*x31**4))*x21**2 + ((-64*x31)*x30**6 + (-192*x31**3 + 512*x31)*x30**4 + (-192*x31**5 + 768*x31**3)*x30**2 + (-64*x31**7 + 256*x31**5))*x21 + (16*x30**8 + (64*x31**2)*x30**6 + (96*x31**4 - 128*x31**2)*x30**4 + (64*x31**6 - 256*x31**4)*x30**2 + (16*x31**8 - 128*x31**6 + 256*x31**4)))*x20**4 + ((64*x30**4 + (128*x31**2)*x30**2 + (64*x31**4))*x21**6 + ((-192*x31)*x30**4 + (-384*x31**3)*x30**2 + (-192*x31**5))*x21**5 + (32*x30**6 + (288*x31**2 - 256)*x30**4 + (480*x31**4 - 384*x31**2)*x30**2 + (224*x31**6 - 128*x31**4))*x21**4 + ((-128*x31)*x30**6 + (-384*x31**3 + 768*x31)*x30**4 + (-384*x31**5 + 1024*x31**3)*x30**2 + (-128*x31**7 + 256*x31**5))*x21**3 + (32*x30**8 + (128*x31**2 - 128)*x30**6 + (192*x31**4 - 384*x31**2)*x30**4 + (128*x31**6 - 384*x31**4 - 512*x31**2)*x30**2 + (32*x31**8 - 128*x31**6))*x21**2)*x20**2 + ((16*x30**4 + (32*x31**2)*x30**2 + (16*x31**4))*x21**8 + ((-64*x31)*x30**4 + (-128*x31**3)*x30**2 + (-64*x31**5))*x21**7 + (32*x30**6 + (160*x31**2 - 128)*x30**4 + (224*x31**4 - 128*x31**2)*x30**2 + (96*x31**6))*x21**6 + ((-64*x31)*x30**6 + (-192*x31**3 + 256*x31)*x30**4 + (-192*x31**5 + 256*x31**3)*x30**2 + (-64*x31**7))*x21**5 + (16*x30**8 + (64*x31**2 - 128)*x30**6 + (96*x31**4 - 256*x31**2 + 256)*x30**4 + (64*x31**6 - 128*x31**4)*x30**2 + (16*x31**8))*x21**4)
37# p_factors = p.factor_square_free()
38
39x = polypy.Variable("x");
40y = polypy.Variable("y");
41z = polypy.Variable("z");
42
43polypy.variable_order.set([z, y, x])
44
45# polynomials and expected factors
46test1 = [(x + 1 - x, 0),
47         (x + 3 - x, 1),
48         (x + 1 - 1, 1),
49         (2*x      , 2),
50         (x + 1    , 1),
51         (2*x + 2  , 2),
52         (2*x + 1  , 1)]
53
54for (p, expected) in test1:
55    p_factors = p.factor_square_free()
56    check_factorization(p, p_factors, expected)
57
58test2 = [(x*y        , 2),
59         (x*y + y    , 2),
60         (x*y + 1    , 1),
61         (2*x*y + 1  , 1),
62         (2*x*y + 2  , 2),
63         (2*x*y + 2*y, 3)]
64
65for (p, expected) in test2:
66    p_factors = p.factor_square_free()
67    check_factorization(p, p_factors, expected)
68
69test3 = [( (x + 1)*(x + 2)**2*(x + 3)**3, 3),
70         ( (x + 1)*(y + 2)**2*(z + 3)**3, 3),
71         ( (z + 1)*(y + 2)**2*(x + 3)**3, 3)]
72
73for (p, expected) in test3:
74    p_factors = p.factor_square_free()
75    check_factorization(p, p_factors, expected)
76