From afb0ccaa49a0cca001d854594e09125a58434123 Mon Sep 17 00:00:00 2001 From: Richard Kreckel Date: Sun, 28 Jan 2018 19:59:54 +0100 Subject: [PATCH] [CHECK] Add some more factorization exams. Add the 15 multivariate polynomials from P. S. Wang's paper "An Improved Multivariate Polynomial Factoring Algorithm" as exams. Don't add them as benchmarks since timings vary considerably depending on internal choice of variables. In any case, this should never take hours. (But before 630db9a0b0 it did, occasionally.) --- check/exam_factor.cpp | 82 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 82 insertions(+) diff --git a/check/exam_factor.cpp b/check/exam_factor.cpp index f7e50b9b..e5241808 100644 --- a/check/exam_factor.cpp +++ b/check/exam_factor.cpp @@ -182,6 +182,87 @@ static unsigned exam_factor3() return result; } +static unsigned check_factor_expanded(const ex& e) +{ + ex ee = e.expand(); + ex answer = factor(ee); + if ( answer.expand() != ee || (!is_a(answer) && !is_a(answer)) ) { + clog << "factorization of " << e << " == " << ee << " gave wrong result: " << answer << endl; + return 1; + } + return 0; +} + +static unsigned exam_factor_wang() +{ + // these 15 polynomials are from the appendix of P.S.Wang, + // "An Improved Multivariate Polynomial Factoring Algorithm" + unsigned result = 0; + ex e; + symbol x("x"), y("y"), z("z"), u("u"); + + e = ex("(z+x*y+10)*(x*z+y+30)*(y*z+x+20)", lst{x, y, z}); + result += check_factor_expanded(e); + + e = ex("(x^3*(z+y)+y-11)*(x^2*(z^2+y^2)+y+90)", lst{x, y, z}); + result += check_factor_expanded(e); + + e = ex("(y*z^3+x*y*z+y^2+x^3)*(x*(z^4+1)+z+x^3*y^2)", lst{x, y, z}); + result += check_factor_expanded(e); + + e = ex("(z^2-x^3*y+3)*(z^2+x*y^3)*(z^2+x^3*y^4)*(y^4*z^2+x^2*z+5)", lst{x, y, z}); + result += check_factor_expanded(e); + + e = ex("(z^2+x^3*y^4+u^2)*((y^2+x)*z^2+3*u^2*x^3*y^4*z+19*y^2)*(u^2*y^4*z^2+x^2*z+5)", lst{u, x, y, z}); + result += check_factor_expanded(e); + + e = ex("(w^4*z^3-x*y^2*z^2-w^4*x^5*y^6-w^2*x^3*y)*(-x^5*z^3+y*z+x^2*y^3)" + "*(w^4*z^6+y^2*z^3-w^2*x^2*y^2*z^2+x^5*z-x^4*y^2-w^3*x^3*y)", lst{w, x, y, z}); + result += check_factor_expanded(e); + + e = ex("(z+y+x-3)^3*(z+y+x-2)^2", lst{x, y, z}); + result += check_factor_expanded(e); + + e = ex("(-15*y^2*z^16+29*w^4*x^12*y^12*z^3+21*x^3*z^2+3*w^15*y^20)" + "*(-z^31-w^12*z^20+y^18-y^14+x^2*y^2+x^21+w^2)", lst{w, x, y, z}); + result += check_factor_expanded(e); + + e = ex("u^4*x*z^2*(6*w^2*y^3*z^2+18*u^2*w^3*x*z^2+15*u*z^2+10*u^2*w*x*y^3)" + "*(-44*u*w*x*y^4*z^4-25*u^2*w^3*y*z^4+8*u*w*x^3*z^4-32*u^2*w^4*y^4*z^3" + "+48*u^2*x^2*y^3*z^3-12*y^3*z^2+2*u^2*w*x^2*y^2-11*u*w^2*x^3*y-4*w^2*x)", lst{u, w, x, y, z}); + result += check_factor_expanded(e); + + e = ex("(31*u^2*x*z+35*w^2*y^2+6*x*y+40*w*x^2)*(u^2*w^2*x*y^2*z^2+24*u^2*w*x*y^2*z^2" + "+12*u^2*x*y^2*z^2+24*u^2*x^2*y*z^2+43*w*x*y*z^2+31*w^2*y*z^2+8*u^2*w^2*z^2" + "+44*u*w^2*z^2+37*u^2*y^2*z+41*y^2*z+12*w*x^2*y*z+21*u^2*w*x*y*z+23*x*y*z" + "+47*u^2*w^2*z+13*u*w^2*x^2*y^2+22*x*y^2+42*u^2*w^2*y^2+29*w^2*y^2+27*u*w^2*x^2*y" + "+37*w^2*x*z+39*u*w*x*z+43*u*x^2*y+24*x*y+9*u^2*w*x^2+22*u^2*w^2)", lst{u, w, x, y, z}); + result += check_factor_expanded(e); + + e = ex("x*y*(-13*u^3*w^2*x*y*z^3+w^3*z^3+4*u*x*y^2+47*x*y)" + "*(43*u*x^3*y^3*z^3+36*u^2*w^3*x*y*z^3+14*w^3*x^3*y^3*z^2-29*w^3*x*y^3*z^2" + "-20*u^2*w^2*x^2*y^2*z^2+36*u^2*w*x*y^3*z-48*u*x^3*y^2*z+5*u*w*x^2*y^3" + "+36*u*w^2*y^3-9*u*w*y^3-23*u*w*x^3*y^2+46*u*x^3*y^2+8*x*y^2+31*u^2*w^3*y^2" + "-9*u^2*y^2+45*x^3-46*u^2*w*x)", lst{u, w, x, y, z}); + result += check_factor_expanded(e); + + e = ex("(z+y+x-3)^3", lst{x, y, z}); + result += check_factor_expanded(e); + + e = ex("(3*z^3+2*w*z-9*y^3-y^2+45*x^3)*(w^2*z^3+47*x*y-w^2)", lst{w, x, y, z}); + result += check_factor_expanded(e); + + e = ex("(-18*x^4*y^5+22*y^5-26*x^3*y^4-38*x^2*y^4+29*x^2*y^3-41*x^4*y^2+37*x^4)" + "*(33*x^5*y^6+11*y^2+35*x^3*y-22*x^4)", lst{x, y, z}); + result += check_factor_expanded(e); + + e = ex("x^6*y^3*z^2*(3*z^3+2*w*z-8*x*y^2+14*w^2*y^2-y^2+18*x^3*y)" + "*(-12*w^2*x*y*z^3+w^2*z^3+3*x*y^2+29*x-w^2)", lst{w, x, y, z}); + result += check_factor_expanded(e); + + return result; +} + static unsigned check_factorization(const exvector& factors) { ex e = dynallocate(factors); @@ -218,6 +299,7 @@ unsigned exam_factor() result += exam_factor1(); cout << '.' << flush; result += exam_factor2(); cout << '.' << flush; result += exam_factor3(); cout << '.' << flush; + result += exam_factor_wang(); cout << '.' << flush; result += factor_integer_content_bug(); cout << '.' << flush; -- 2.25.4