1 /*
2 Qalculate (library)
3
4 Copyright (C) 2003-2007, 2008, 2016-2019 Hanna Knutsson (hanna.knutsson@protonmail.com)
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10 */
11
12 #include "support.h"
13
14 #include "MathStructure.h"
15 #include "Calculator.h"
16 #include "BuiltinFunctions.h"
17 #include "Number.h"
18 #include "Function.h"
19 #include "Variable.h"
20 #include "Unit.h"
21 #include "Prefix.h"
22 #include "MathStructure-support.h"
23
24 using std::string;
25 using std::cout;
26 using std::vector;
27 using std::endl;
28
decomposeFractions(const MathStructure & x_var,const EvaluationOptions & eo)29 bool MathStructure::decomposeFractions(const MathStructure &x_var, const EvaluationOptions &eo) {
30 MathStructure mtest2;
31 bool b = false;
32 int mmul_i = 0;
33 if(isPower()) {
34 if(CHILD(1).isMinusOne() && CHILD(0).isMultiplication() && CHILD(0).size() >= 2) {
35 mtest2 = CHILD(0);
36 b = true;
37 }
38 } else if(isMultiplication() && SIZE == 2) {
39 for(size_t i = 0; i < SIZE; i++) {
40 if(CHILD(i).isPower() && CHILD(i)[1].isMinusOne() && (CHILD(i)[0].isPower() || CHILD(i)[0].isMultiplication())) {
41 mtest2 = CHILD(i)[0];
42 b = true;
43 } else if(CHILD(i) == x_var) {
44 mmul_i = 1;
45 } else if(CHILD(i).isPower() && CHILD(i)[0] == x_var && CHILD(i)[1].isInteger() && CHILD(i)[1].number().isPositive() && CHILD(i)[1].number().isLessThan(100)) {
46 mmul_i = CHILD(i)[1].number().intValue();
47 }
48 }
49 if(mmul_i == 0) b = false;
50 }
51 if(b) {
52 if(!mtest2.isMultiplication()) mtest2.transform(STRUCT_MULTIPLICATION);
53 MathStructure mfacs, mnew;
54 mnew.setType(STRUCT_ADDITION);
55 mfacs.setType(STRUCT_ADDITION);
56 vector<int> i_degrees;
57 i_degrees.resize(mtest2.size(), 1);
58 for(size_t i = 0; i < mtest2.size() && b; i++) {
59 if(CALCULATOR->aborted()) return false;
60 MathStructure mfactor = mtest2[i];
61 if(mtest2[i].isPower()) {
62 if(!mtest2[i][1].isInteger() || !mtest2[i][1].number().isPositive() || mtest2[i][1].isOne() || mtest2[i][1].number().isGreaterThan(100)) {
63 b = false;
64 break;
65 }
66 mfactor = mtest2[i][0];
67 }
68 if(mfactor.isAddition()) {
69 bool b2 = false;
70 for(size_t i2 = 0; i2 < mfactor.size() && b; i2++) {
71 if(mfactor[i2].isMultiplication()) {
72 bool b_x = false;
73 for(size_t i3 = 0; i3 < mfactor[i2].size() && b; i3++) {
74 if(!b_x && mfactor[i2][i3].isPower() && mfactor[i2][i3][0] == x_var) {
75 if(!mfactor[i2][i3][1].isInteger() || !mfactor[i2][i3][1].number().isPositive() || mfactor[i2][i3][1].isOne() || mfactor[i2][i3][1].number().isGreaterThan(100)) {
76 b = false;
77 } else if(mfactor[i2][i3][1].number().intValue() > i_degrees[i]) {
78 i_degrees[i] = mfactor[i2][i3][1].number().intValue();
79 }
80 b_x = true;
81 } else if(!b_x && mfactor[i2][i3] == x_var) {
82 b_x = true;
83 } else if(mfactor[i2][i3].containsRepresentativeOf(x_var, true, true) != 0) {
84 b = false;
85 }
86 }
87 if(!b_x) b2 = true;
88 } else if(mfactor[i2].isPower() && mfactor[i2][0] == x_var) {
89 if(!mfactor[i2][1].isInteger() || !mfactor[i2][1].number().isPositive() || mfactor[i2][1].isOne() || mfactor[i2][1].number().isGreaterThan(100)) {
90 b = false;
91 } else if(mfactor[i2][1].number().intValue() > i_degrees[i]) {
92 i_degrees[i] = mfactor[i2][1].number().intValue();
93 }
94 } else if(mfactor[i2] == x_var) {
95 } else if(mfactor[i2].containsRepresentativeOf(x_var, true, true) != 0) {
96 b = false;
97 } else {
98 b2 = true;
99 }
100 }
101 if(!b2) b = false;
102 } else if(mfactor != x_var) {
103 b = false;
104 }
105 }
106 MathStructure mtest3, mnums3;
107 mnums3.clearVector();
108 mtest3.clearVector();
109 if(b) {
110 UnknownVariable *var = new UnknownVariable("", string("a"));
111 var->setAssumptions(new Assumptions());
112 MathStructure mvar(var);
113 for(size_t i = 0; i < mtest2.size(); i++) {
114 if(CALCULATOR->aborted()) return false;
115 if(i_degrees[i] == 1) {
116 MathStructure mnum(1, 1, 0);
117 if(mtest2.size() != 1) {
118 mnum = mtest2;
119 mnum.delChild(i + 1, true);
120 }
121 MathStructure mx(mtest2[i]);
122 mx.transform(COMPARISON_EQUALS, m_zero);
123 mx.replace(x_var, mvar);
124 mx.isolate_x(eo, mvar);
125 mx.calculatesub(eo, eo, true);
126 if(mx.isLogicalOr()) mx.setToChild(1);
127 if(!mx.isComparison() || mx.comparisonType() != COMPARISON_EQUALS || mx[0] != var) {b = false; break;}
128 mx.setToChild(2);
129 if(mtest2.size() != 1) {
130 mfacs.addChild(mnum);
131 mnum.replace(x_var, mx);
132 mnum.inverse();
133 }
134 if(mmul_i > 0) {
135 mx ^= Number(mmul_i, 1);
136 if(mtest2.size() == 1) mnum = mx;
137 else mnum *= mx;
138 }
139 mnum.calculatesub(eo, eo, true);
140 if(mtest2.size() == 1) mfacs.addChild(mnum);
141 else mfacs.last() *= mnum;
142 mnums3.addChild(mnum);
143 mtest3.addChild(mtest2[i]);
144 }
145 }
146 var->destroy();
147 }
148 if(b) {
149 vector<UnknownVariable*> vars;
150 bool b_solve = false;
151 for(size_t i = 0; i < mtest2.size(); i++) {
152 if(CALCULATOR->aborted()) return false;
153 if(mtest2[i].isPower()) {
154 int i_exp = mtest2[i][1].number().intValue();
155 for(int i_exp_n = mtest2[i][1].number().intValue() - (i_degrees[i] == 1 ? 1 : 0); i_exp_n > 0; i_exp_n--) {
156 if(i_exp_n == 1) {
157 mtest3.addChild(mtest2[i][0]);
158 } else {
159 mtest3.addChild(mtest2[i]);
160 if(i_exp_n != i_exp) mtest3.last()[1].number() = i_exp_n;
161 }
162 if(i_exp == i_exp_n) {
163 if(mtest2.size() > 1) {
164 mfacs.addChild(mtest2);
165 mfacs.last().delChild(i + 1, true);
166 }
167 } else {
168 mfacs.addChild(mtest2);
169 if(i_exp - i_exp_n == 1) mfacs.last()[i].setToChild(1);
170 else mfacs.last()[i][1].number() = i_exp - i_exp_n;
171 }
172 if(i_degrees[i] == 1) {
173 UnknownVariable *var = new UnknownVariable("", string("a") + i2s(mtest3.size()));
174 var->setAssumptions(new Assumptions());
175 mnums3.addChild_nocopy(new MathStructure(var));
176 vars.push_back(var);
177 } else {
178 mnums3.addChild_nocopy(new MathStructure());
179 mnums3.last().setType(STRUCT_ADDITION);
180 for(int i2 = 1; i2 <= i_degrees[i]; i2++) {
181 UnknownVariable *var = new UnknownVariable("", string("a") + i2s(mtest3.size()) + i2s(i2));
182 var->setAssumptions(new Assumptions());
183 if(i2 == 1) {
184 mnums3.last().addChild_nocopy(new MathStructure(var));
185 } else {
186 mnums3.last().addChild_nocopy(new MathStructure(var));
187 mnums3.last().last() *= x_var;
188 if(i2 > 2) mnums3.last().last().last() ^= Number(i2 - 1, 1);
189 }
190 vars.push_back(var);
191 }
192 }
193 if(i_exp != i_exp_n || mtest2.size() > 1) mfacs.last() *= mnums3.last();
194 else mfacs.addChild(mnums3.last());
195 b_solve = true;
196 }
197 } else if(i_degrees[i] > 1) {
198 mtest3.addChild(mtest2[i]);
199 if(mtest2.size() > 1) {
200 mfacs.addChild(mtest2);
201 mfacs.last().delChild(i + 1, true);
202 }
203 mnums3.addChild_nocopy(new MathStructure());
204 mnums3.last().setType(STRUCT_ADDITION);
205 for(int i2 = 1; i2 <= i_degrees[i]; i2++) {
206 UnknownVariable *var = new UnknownVariable("", string("a") + i2s(mtest3.size()) + i2s(i2));
207 var->setAssumptions(new Assumptions());
208 if(i2 == 1) {
209 mnums3.last().addChild_nocopy(new MathStructure(var));
210 } else {
211 mnums3.last().addChild_nocopy(new MathStructure(var));
212 mnums3.last().last() *= x_var;
213 if(i2 > 2) mnums3.last().last().last() ^= Number(i2 - 1, 1);
214 }
215 vars.push_back(var);
216 }
217 if(mtest2.size() > 1) mfacs.last() *= mnums3.last();
218 else mfacs.addChild(mnums3.last());
219 b_solve = true;
220 }
221 }
222 if(b_solve) {
223 mfacs.childrenUpdated(true);
224 MathStructure mfac_expand(mfacs);
225 mfac_expand.calculatesub(eo, eo, true);
226 size_t i_degree = 0;
227 if(mfac_expand.isAddition()) {
228 i_degree = mfac_expand.degree(x_var).uintValue();
229 if(i_degree >= 100 || i_degree <= 0) b = false;
230 }
231 if(i_degree == 0) b = false;
232 if(b) {
233 MathStructure m_eqs;
234 m_eqs.resizeVector(i_degree + 1, m_zero);
235 for(size_t i = 0; i < m_eqs.size(); i++) {
236 for(size_t i2 = 0; i2 < mfac_expand.size();) {
237 if(CALCULATOR->aborted()) return false;
238 bool b_add = false;
239 if(i == 0) {
240 if(!mfac_expand[i2].contains(x_var)) b_add = true;
241 } else {
242 if(mfac_expand[i2].isMultiplication() && mfac_expand[i2].size() >= 2) {
243 for(size_t i3 = 0; i3 < mfac_expand[i2].size(); i3++) {
244 if(i == 1 && mfac_expand[i2][i3] == x_var) b_add = true;
245 else if(i > 1 && mfac_expand[i2][i3].isPower() && mfac_expand[i2][i3][0] == x_var && mfac_expand[i2][i3][1] == i) b_add = true;
246 if(b_add) {
247 mfac_expand[i2].delChild(i3 + 1, true);
248 break;
249 }
250 }
251
252 } else {
253 if(i == 1 && mfac_expand[i2] == x_var) b_add = true;
254 else if(i > 1 && mfac_expand[i2].isPower() && mfac_expand[i2][0] == x_var && mfac_expand[i2][1] == i) b_add = true;
255 if(b_add) mfac_expand[i2].set(1, 1, 0);
256 }
257 }
258 if(b_add) {
259 if(m_eqs[i].isZero()) m_eqs[i] = mfac_expand[i2];
260 else m_eqs[i].add(mfac_expand[i2], true);
261 mfac_expand.delChild(i2 + 1);
262 } else {
263 i2++;
264 }
265 }
266 }
267 if(mfac_expand.size() == 0 && m_eqs.size() >= vars.size()) {
268 for(size_t i = 0; i < m_eqs.size(); i++) {
269 if(!m_eqs[i].isZero()) {
270 m_eqs[i].transform(COMPARISON_EQUALS, i == (size_t) mmul_i ? m_one : m_zero);
271 }
272 }
273 for(size_t i = 0; i < m_eqs.size();) {
274 if(m_eqs[i].isZero()) {
275 m_eqs.delChild(i + 1);
276 if(i == (size_t) mmul_i) b = false;
277 } else {
278 i++;
279 }
280 }
281 if(b) {
282 MathStructure vars_m;
283 vars_m.clearVector();
284 for(size_t i = 0; i < vars.size(); i++) {
285 vars_m.addChild_nocopy(new MathStructure(vars[i]));
286 }
287 for(size_t i = 0; i < m_eqs.size() && b; i++) {
288 for(size_t i2 = 0; i2 < vars_m.size(); i2++) {
289 if(m_eqs[i].isComparison() && m_eqs[i][0].contains(vars_m[i2], true)) {
290 if(CALCULATOR->aborted() || m_eqs[i].countTotalChildren() > 1000) return false;
291 m_eqs[i].isolate_x(eo, vars_m[i2]);
292 if(CALCULATOR->aborted() || m_eqs[i].countTotalChildren() > 10000) return false;
293 m_eqs[i].calculatesub(eo, eo, true);
294 if(m_eqs[i].isLogicalOr()) m_eqs[i].setToChild(1);
295 if(m_eqs[i].isComparison() && m_eqs[i].comparisonType() == COMPARISON_EQUALS && m_eqs[i][0] == vars_m[i2]) {
296 for(size_t i3 = 0; i3 < m_eqs.size(); i3++) {
297 if(i3 != i) {
298 if(CALCULATOR->aborted()) return false;
299 m_eqs[i3][0].calculateReplace(vars_m[i2], m_eqs[i][1], eo);
300 if(CALCULATOR->aborted()) return false;
301 m_eqs[i3][1].calculateReplace(vars_m[i2], m_eqs[i][1], eo);
302 }
303 }
304 vars_m.delChild(i2 + 1);
305 } else {
306 b = false;
307 }
308 break;
309 }
310 }
311 }
312 for(size_t i = 0; i < m_eqs.size();) {
313 if(CALCULATOR->aborted()) return false;
314 m_eqs[i].calculatesub(eo, eo);
315 if(m_eqs[i].isZero()) {b = false; break;}
316 if(m_eqs[i].isOne()) m_eqs.delChild(i + 1);
317 else i++;
318 }
319 if(b && vars_m.size() == 0) {
320 for(size_t i = 0; i < vars.size(); i++) {
321 for(size_t i2 = 0; i2 < m_eqs.size(); i2++) {
322 if(m_eqs[i2][0] == vars[i]) {
323 mnums3.replace(vars[i], m_eqs[i2][1]);
324 break;
325 }
326 }
327 }
328 } else {
329 b = false;
330 }
331 }
332 } else {
333 b = false;
334 }
335 }
336 }
337 for(size_t i = 0; i < vars.size(); i++) {
338 vars[i]->destroy();
339 }
340 if(b) {
341 for(size_t i = 0; i < mnums3.size(); i++) {
342 mnums3.calculatesub(eo, eo, true);
343 if(!mnums3[i].isZero()) {
344 if(mnums3[i].isOne()) {
345 mnew.addChild(mtest3[i]);
346 mnew.last().inverse();
347 } else {
348 mnew.addChild(mnums3[i]);
349 mnew.last() /= mtest3[i];
350 }
351 }
352 }
353 }
354 if(b) {
355 if(mnew.size() == 0) mnew.clear();
356 else if(mnew.size() == 1) mnew.setToChild(1);
357 mnew.childrenUpdated();
358 if(equals(mnew, true)) return false;
359 set(mnew, true);
360 return true;
361 }
362 }
363 }
364 return false;
365 }
366
expand_partial_fractions(MathStructure & m,const EvaluationOptions & eo,bool do_simplify=true)367 bool expand_partial_fractions(MathStructure &m, const EvaluationOptions &eo, bool do_simplify = true) {
368 MathStructure mtest(m);
369 if(do_simplify) {
370 mtest.simplify(eo);
371 mtest.calculatesub(eo, eo, true);
372 }
373 if(mtest.isPower() && mtest[1].representsNegative()) {
374 MathStructure x_var = mtest[0].find_x_var();
375 if(!x_var.isUndefined() && mtest[0].factorize(eo, false, 0, 0, false, false, NULL, x_var)) {
376 if(mtest.decomposeFractions(x_var, eo) && mtest.isAddition()) {
377 m = mtest;
378 return true;
379 }
380 }
381 } else if(mtest.isMultiplication()) {
382 for(size_t i = 0; i < mtest.size(); i++) {
383 if(mtest[i].isPower() && mtest[i][1].isMinusOne() && mtest[i][0].isAddition()) {
384 MathStructure x_var = mtest[i][0].find_x_var();
385 if(!x_var.isUndefined()) {
386 MathStructure mfac(mtest);
387 mfac.delChild(i + 1, true);
388 bool b_poly = true;
389 if(mfac.contains(x_var, true)) {
390 MathStructure mquo, mrem;
391 b_poly = polynomial_long_division(mfac, mtest[i][0], x_var, mquo, mrem, eo, true);
392 if(b_poly && !mquo.isZero()) {
393 m = mquo;
394 if(!mrem.isZero()) {
395 m += mrem;
396 m.last() *= mtest[i];
397 m.childrenUpdated();
398 }
399 expand_partial_fractions(m, eo, false);
400 return true;
401 }
402 }
403 if(b_poly && mtest[i][0].factorize(eo, false, 0, 0, false, false, NULL, x_var)) {
404 MathStructure mmul(1, 1, 0);
405 while(mtest[i][0].isMultiplication() && mtest[i][0].size() >= 2 && !mtest[i][0][0].containsRepresentativeOf(x_var, true)) {
406 if(mmul.isOne()) {
407 mmul = mtest[i][0][0];
408 mmul.calculateInverse(eo);
409 } else {
410 mmul *= mtest[i][0][0];
411 mmul.last().calculateInverse(eo);
412 mmul.calculateMultiplyLast(eo);
413 }
414 mtest[i][0].delChild(1, true);
415 }
416 for(size_t i2 = 0; i2 < mtest.size();) {
417 if(i2 != i && !mtest[i2].containsRepresentativeOf(x_var, true)) {
418 if(mmul.isOne()) {
419 mmul = mtest[i2];
420 } else {
421 mmul.calculateMultiply(mtest[i2], eo);
422 }
423 if(mtest.size() == 2) {
424 mtest.setToChild(i + 1, true);
425 break;
426 } else {
427 mtest.delChild(i2 + 1);
428 if(i2 < i) i--;
429 }
430 } else {
431 i2++;
432 }
433 }
434 if(mtest.decomposeFractions(x_var, eo) && mtest.isAddition()) {
435 m = mtest;
436 if(!mmul.isOne()) {
437 for(size_t i2 = 0; i2 < m.size(); i2++) {
438 m[i2].calculateMultiply(mmul, eo);
439 }
440 }
441 return true;
442 }
443 }
444 }
445 }
446 }
447 } else {
448 bool b = false;
449 for(size_t i = 0; i < mtest.size(); i++) {
450 if(expand_partial_fractions(mtest[i], eo, false)) {
451 b = true;
452 }
453 }
454 if(b) {
455 m = mtest;
456 m.calculatesub(eo, eo, false);
457 return true;
458 }
459 }
460 return false;
461 }
expandPartialFractions(const EvaluationOptions & eo)462 bool MathStructure::expandPartialFractions(const EvaluationOptions &eo) {
463 return expand_partial_fractions(*this, eo, true);
464 }
465
466