1 /*
2 Copyright (C) 2020 Daniel Schultz
3
4 This file is part of FLINT.
5
6 FLINT is free software: you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License (LGPL) as published
8 by the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version. See <https://www.gnu.org/licenses/>.
10 */
11
12 #include "fmpz_mpoly_factor.h"
13
check_omega(slong lower,slong upper,const fmpz_mpoly_t p,const fmpz_mpoly_ctx_t ctx)14 void check_omega(slong lower, slong upper, const fmpz_mpoly_t p, const fmpz_mpoly_ctx_t ctx)
15 {
16 slong i;
17 fmpz_mpoly_t q;
18 fmpz_mpoly_factor_t g, h;
19 fmpz_t omega;
20
21 fmpz_init(omega);
22 fmpz_mpoly_factor_init(g, ctx);
23 fmpz_mpoly_factor_init(h, ctx);
24 fmpz_mpoly_init(q, ctx);
25
26 if (!fmpz_mpoly_factor(g, p, ctx))
27 {
28 flint_printf("check factorization could be computed\n");
29 flint_abort();
30 }
31
32 for (i = 0; i < g->num; i++)
33 {
34 if (g->poly[i].length < 1 || fmpz_sgn(g->poly[i].coeffs + 0) <= 0)
35 {
36 flint_printf("factorization is not unit normal\n");
37 flint_abort();
38 }
39 }
40
41 fmpz_zero(omega);
42 for (i = 0; i < g->num; i++)
43 fmpz_add(omega, omega, g->exp + i);
44
45 if (fmpz_cmp_si(omega, lower) < 0 || fmpz_cmp_si(omega, upper) > 0)
46 {
47 flint_printf("factorization has wrong number of factors\n");
48 flint_abort();
49 }
50
51 fmpz_mpoly_factor_expand(q, g, ctx);
52 if (!fmpz_mpoly_equal(q, p, ctx))
53 {
54 flint_printf("factorization does not match original polynomial\n");
55 flint_abort();
56 }
57
58 for (i = 0; i < g->num; i++)
59 {
60 fmpz_mpoly_factor(h, g->poly + i, ctx);
61 if (h->num != 1 || !fmpz_is_one(h->exp + 0))
62 {
63 flint_printf("FAIL:\nfactor is reducible\n");
64 flint_abort();
65 }
66 }
67
68 fmpz_mpoly_clear(q, ctx);
69 fmpz_mpoly_factor_clear(g, ctx);
70 fmpz_mpoly_factor_clear(h, ctx);
71 fmpz_clear(omega);
72 }
73
74
75 int
main(void)76 main(void)
77 {
78 slong i, j, tmul = 25;
79 FLINT_TEST_INIT(state);
80
81 flint_printf("factor....");
82 fflush(stdout);
83
84 {
85 fmpz_mpoly_ctx_t ctx;
86 fmpz_mpoly_t f;
87
88 fmpz_mpoly_ctx_init(ctx, 8, ORD_LEX);
89 fmpz_mpoly_init(f, ctx);
90
91 fmpz_mpoly_set_str_pretty(f,
92 "x1^809*x2^75*x3^384*x4^324*x5^74*x6^788*x7^83*x8^414+"
93 "x1^805*x2^343*x3^595*x4^246*x5^32*x6^90*x7^473*x8^591+"
94 "x1^718*x2^108*x3^680*x4^368*x5^358*x8^276+"
95 "x1^683*x2^533*x4^649*x5^619*x6^136*x7^223*x8^610+"
96 "x2^617*x3^777*x4^799*x5^443*x6^545*x7^166*x8^216+"
97 "x1^485*x2^646*x3^424*x4^265*x5^416*x6^400*x7^278+"
98 "x1^336*x2^149*x3^361*x4^691*x5^629*x6^282*x7^530*x8^259+"
99 "x1^266*x3^258*x5^422*x6^637*x7^244*x8^236+"
100 "x1^74*x2^812*x3^162*x4^417*x5^71*x6^188*x7^258*x8^637+"
101 "x1^37*x2^604*x3^94*x4^474*x6^853*x7^521*x8^250", NULL, ctx);
102
103 check_omega(1, 1, f, ctx);
104
105 fmpz_mpoly_clear(f, ctx);
106 fmpz_mpoly_ctx_clear(ctx);
107 }
108
109 for (i = 0; i < tmul * flint_test_multiplier(); i++)
110 {
111 slong lower;
112 fmpz_mpoly_ctx_t ctx;
113 fmpz_mpoly_t a, t;
114 flint_bitcnt_t coeff_bits;
115 slong nfacs, len;
116 ulong expbound, powbound, pow;
117
118 fmpz_mpoly_ctx_init_rand(ctx, state, 8);
119
120 fmpz_mpoly_init(a, ctx);
121 fmpz_mpoly_init(t, ctx);
122
123 nfacs = 1 + (5 + n_randint(state, 5))/ctx->minfo->nvars;
124 expbound = 3 + 40/nfacs/ctx->minfo->nvars;
125 powbound = 1 + n_randint(state, 3);
126
127 lower = 0;
128 fmpz_mpoly_one(a, ctx);
129 for (j = 0; j < nfacs; j++)
130 {
131 do {
132 len = 1 + n_randint(state, 7);
133 coeff_bits = 10 + n_randint(state, 1000)/nfacs;
134 fmpz_mpoly_randtest_bound(t, state, len, coeff_bits, expbound, ctx);
135 } while (t->length == 0);
136 pow = 1 + n_randint(state, powbound);
137 if (!fmpz_mpoly_is_fmpz(t, ctx))
138 lower += pow;
139 fmpz_mpoly_pow_ui(t, t, pow, ctx);
140 fmpz_mpoly_mul(a, a, t, ctx);
141 }
142
143 check_omega(lower, WORD_MAX, a, ctx);
144
145 fmpz_mpoly_clear(t, ctx);
146 fmpz_mpoly_clear(a, ctx);
147 fmpz_mpoly_ctx_clear(ctx);
148 }
149
150 FLINT_TEST_CLEANUP(state);
151
152 flint_printf("PASS\n");
153 return 0;
154 }
155