1 /*
2 Copyright (C) 2016 William Hart
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 <http://www.gnu.org/licenses/>.
10 */
11
12 #include <gmp.h>
13 #include <stdlib.h>
14 #include "flint.h"
15 #include "fmpz.h"
16 #include "fmpz_mpoly.h"
17
_fmpz_mpoly_add1(fmpz * poly1,ulong * exps1,const fmpz * poly2,const ulong * exps2,slong len2,const fmpz * poly3,const ulong * exps3,slong len3,ulong maskhi)18 slong _fmpz_mpoly_add1(fmpz * poly1, ulong * exps1,
19 const fmpz * poly2, const ulong * exps2, slong len2,
20 const fmpz * poly3, const ulong * exps3, slong len3,
21 ulong maskhi)
22 {
23 slong i = 0, j = 0, k = 0;
24
25 while (i < len2 && j < len3)
26 {
27 if ((exps2[i]^maskhi) > (exps3[j]^maskhi))
28 {
29 fmpz_set(poly1 + k, poly2 + i);
30 exps1[k] = exps2[i];
31 i++;
32 } else if ((exps2[i]^maskhi) == (exps3[j]^maskhi))
33 {
34 fmpz_add(poly1 + k, poly2 + i, poly3 + j);
35 exps1[k] = exps2[i];
36 if (fmpz_is_zero(poly1 + k))
37 k--;
38 i++;
39 j++;
40 } else
41 {
42 fmpz_set(poly1 + k, poly3 + j);
43 exps1[k] = exps3[j];
44 j++;
45 }
46 k++;
47 }
48
49 while (i < len2)
50 {
51 fmpz_set(poly1 + k, poly2 + i);
52 exps1[k] = exps2[i];
53 i++;
54 k++;
55 }
56
57 while (j < len3)
58 {
59 fmpz_set(poly1 + k, poly3 + j);
60 exps1[k] = exps3[j];
61 j++;
62 k++;
63 }
64
65 return k;
66 }
67
_fmpz_mpoly_add(fmpz * poly1,ulong * exps1,const fmpz * poly2,const ulong * exps2,slong len2,const fmpz * poly3,const ulong * exps3,slong len3,slong N,const ulong * cmpmask)68 slong _fmpz_mpoly_add(fmpz * poly1, ulong * exps1,
69 const fmpz * poly2, const ulong * exps2, slong len2,
70 const fmpz * poly3, const ulong * exps3, slong len3, slong N,
71 const ulong * cmpmask)
72 {
73 slong i = 0, j = 0, k = 0;
74
75 if (N == 1)
76 return _fmpz_mpoly_add1(poly1, exps1, poly2, exps2, len2,
77 poly3, exps3, len3, cmpmask[0]);
78
79 while (i < len2 && j < len3)
80 {
81 int cmp = mpoly_monomial_cmp(exps2 + i*N, exps3 + j*N, N, cmpmask);
82
83 if (cmp > 0)
84 {
85 fmpz_set(poly1 + k, poly2 + i);
86 mpoly_monomial_set(exps1 + k*N, exps2 + i*N, N);
87 i++;
88 } else if (cmp == 0)
89 {
90 fmpz_add(poly1 + k, poly2 + i, poly3 + j);
91 mpoly_monomial_set(exps1 + k*N, exps2 + i*N, N);
92 if (fmpz_is_zero(poly1 + k))
93 k--;
94 i++;
95 j++;
96 } else
97 {
98 fmpz_set(poly1 + k, poly3 + j);
99 mpoly_monomial_set(exps1 + k*N, exps3 + j*N, N);
100 j++;
101 }
102 k++;
103 }
104
105 while (i < len2)
106 {
107 fmpz_set(poly1 + k, poly2 + i);
108 mpoly_monomial_set(exps1 + k*N, exps2 + i*N, N);
109 i++;
110 k++;
111 }
112
113 while (j < len3)
114 {
115 fmpz_set(poly1 + k, poly3 + j);
116 mpoly_monomial_set(exps1 + k*N, exps3 + j*N, N);
117 j++;
118 k++;
119 }
120
121 return k;
122 }
123
fmpz_mpoly_add(fmpz_mpoly_t poly1,const fmpz_mpoly_t poly2,const fmpz_mpoly_t poly3,const fmpz_mpoly_ctx_t ctx)124 void fmpz_mpoly_add(fmpz_mpoly_t poly1, const fmpz_mpoly_t poly2,
125 const fmpz_mpoly_t poly3, const fmpz_mpoly_ctx_t ctx)
126 {
127 slong len = 0, max_bits, N;
128 ulong * exp2 = poly2->exps, * exp3 = poly3->exps;
129 ulong * cmpmask;
130 int free2 = 0, free3 = 0;
131 TMP_INIT;
132
133 max_bits = FLINT_MAX(poly2->bits, poly3->bits);
134 N = mpoly_words_per_exp(max_bits, ctx->minfo);
135
136 if (poly2->length == 0)
137 {
138 fmpz_mpoly_set(poly1, poly3, ctx);
139 return;
140 } else if (poly3->length == 0)
141 {
142 fmpz_mpoly_set(poly1, poly2, ctx);
143 return;
144 }
145
146 TMP_START;
147 cmpmask = (ulong *) TMP_ALLOC(N*sizeof(ulong));
148 mpoly_get_cmpmask(cmpmask, N, max_bits, ctx->minfo);
149
150 if (max_bits > poly2->bits)
151 {
152 free2 = 1;
153 exp2 = (ulong *) flint_malloc(N*poly2->length*sizeof(ulong));
154 mpoly_repack_monomials(exp2, max_bits, poly2->exps, poly2->bits,
155 poly2->length, ctx->minfo);
156 }
157
158 if (max_bits > poly3->bits)
159 {
160 free3 = 1;
161 exp3 = (ulong *) flint_malloc(N*poly3->length*sizeof(ulong));
162 mpoly_repack_monomials(exp3, max_bits, poly3->exps, poly3->bits,
163 poly3->length, ctx->minfo);
164 }
165
166 if (poly1 == poly2 || poly1 == poly3)
167 {
168 fmpz_mpoly_t temp;
169
170 fmpz_mpoly_init2(temp, poly2->length + poly3->length, ctx);
171 fmpz_mpoly_fit_bits(temp, max_bits, ctx);
172 temp->bits = max_bits;
173
174 len = _fmpz_mpoly_add(temp->coeffs, temp->exps,
175 poly2->coeffs, exp2, poly2->length,
176 poly3->coeffs, exp3, poly3->length, N, cmpmask);
177
178 fmpz_mpoly_swap(temp, poly1, ctx);
179
180 fmpz_mpoly_clear(temp, ctx);
181 } else
182 {
183 fmpz_mpoly_fit_length(poly1, poly2->length + poly3->length, ctx);
184 fmpz_mpoly_fit_bits(poly1, max_bits, ctx);
185 poly1->bits = max_bits;
186
187 len = _fmpz_mpoly_add(poly1->coeffs, poly1->exps,
188 poly2->coeffs, exp2, poly2->length,
189 poly3->coeffs, exp3, poly3->length, N, cmpmask);
190 }
191
192 if (free2)
193 flint_free(exp2);
194
195 if (free3)
196 flint_free(exp3);
197
198 _fmpz_mpoly_set_length(poly1, len, ctx);
199 TMP_END;
200 }
201