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::ostream;
28 using std::endl;
29
factorize_fix_root_power(MathStructure & m)30 bool factorize_fix_root_power(MathStructure &m) {
31 if(!m[0].isFunction() || m[0].function()->id() != FUNCTION_ID_ROOT || !VALID_ROOT(m[0])) return false;
32 if(m[1].isNumber() && m[1].number().isInteger() && !m[1].number().isMinusOne()) {
33 if(m[1] == m[0][1]) {
34 // root(x, a)^a=x
35 m.setToChild(1, true);
36 m.setToChild(1, true);
37 return true;
38 } else if(m[1].number().isIntegerDivisible(m[0][1].number())) {
39 // root(x, a)^(2a)=x^2
40 if(m[1].number().divide(m[0][1].number())) {
41 m[0].setToChild(1, true);
42 return true;
43 }
44 } else if(m[0][1].number().isIntegerDivisible(m[1].number())) {
45 // root(x, 3a)^(a)=root(x, 3)
46 if(m[0][1].number().divide(m[1].number())) {
47 m.setToChild(1, true);
48 m.childUpdated(2);
49 return true;
50 }
51 }
52 }
53 return false;
54 }
55
sqrfree_differentiate(const MathStructure & mpoly,const MathStructure & x_var,MathStructure & mdiff,const EvaluationOptions & eo)56 bool sqrfree_differentiate(const MathStructure &mpoly, const MathStructure &x_var, MathStructure &mdiff, const EvaluationOptions &eo) {
57 if(mpoly == x_var) {
58 mdiff.set(1, 1, 0);
59 return true;
60 }
61 switch(mpoly.type()) {
62 case STRUCT_ADDITION: {
63 mdiff.clear();
64 mdiff.setType(STRUCT_ADDITION);
65 for(size_t i = 0; i < mpoly.size(); i++) {
66 mdiff.addChild(m_zero);
67 if(!sqrfree_differentiate(mpoly[i], x_var, mdiff[i], eo)) return false;
68 }
69 mdiff.calculatesub(eo, eo, false);
70 break;
71 }
72 case STRUCT_VARIABLE: {}
73 case STRUCT_FUNCTION: {}
74 case STRUCT_SYMBOLIC: {}
75 case STRUCT_UNIT: {}
76 case STRUCT_NUMBER: {
77 mdiff.clear();
78 break;
79 }
80 case STRUCT_POWER: {
81 if(mpoly[0] == x_var) {
82 mdiff = mpoly[1];
83 mdiff.multiply(x_var);
84 if(!mpoly[1].number().isTwo()) {
85 mdiff[1].raise(mpoly[1]);
86 mdiff[1][1].number()--;
87 }
88 mdiff.evalSort(true);
89 } else {
90 mdiff.clear();
91 }
92 break;
93 }
94 case STRUCT_MULTIPLICATION: {
95 if(mpoly.size() < 1) {
96 mdiff.clear();
97 break;
98 } else if(mpoly.size() < 2) {
99 return sqrfree_differentiate(mpoly[0], x_var, mdiff, eo);
100 }
101 mdiff.clear();
102 for(size_t i = 0; i < mpoly.size(); i++) {
103 if(mpoly[i] == x_var) {
104 if(mpoly.size() == 2) {
105 if(i == 0) mdiff = mpoly[1];
106 else mdiff = mpoly[0];
107 } else {
108 mdiff.setType(STRUCT_MULTIPLICATION);
109 for(size_t i2 = 0; i2 < mpoly.size(); i2++) {
110 if(i2 != i) {
111 mdiff.addChild(mpoly[i2]);
112 }
113 }
114 }
115 break;
116 } else if(mpoly[i].isPower() && mpoly[i][0] == x_var) {
117 mdiff = mpoly;
118 if(mpoly[i][1].number().isTwo()) {
119 mdiff[i].setToChild(1);
120 } else {
121 mdiff[i][1].number()--;
122 }
123 if(mdiff[0].isNumber()) {
124 mdiff[0].number() *= mpoly[i][1].number();
125 } else {
126 mdiff.insertChild(mpoly[i][1].number(), 1);
127 }
128 mdiff.evalSort();
129 break;
130 }
131 }
132 break;
133 }
134 default: {
135 return false;
136 }
137 }
138 return true;
139 }
fix_root_pow(MathStructure & m,const MathStructure & xvar,const EvaluationOptions & eo)140 bool fix_root_pow(MathStructure &m, const MathStructure &xvar, const EvaluationOptions &eo) {
141 if(m.isPower() && m[0].contains(xvar) && m[1].isNumber()) {
142 return m.calculateRaiseExponent(eo);
143 }
144 bool b_ret = false;
145 for(size_t i = 0; i < m.size(); i++) {
146 if(fix_root_pow(m[i], xvar, eo)) {m.childUpdated(i + 1); b_ret = true;}
147 }
148 if(b_ret) m.calculatesub(eo, eo, false);
149 return b_ret;
150 }
151
sqrfree_yun(const MathStructure & a,const MathStructure & xvar,MathStructure & factors,const EvaluationOptions & eo)152 bool sqrfree_yun(const MathStructure &a, const MathStructure &xvar, MathStructure &factors, const EvaluationOptions &eo) {
153 MathStructure w(a);
154 MathStructure z;
155 if(!sqrfree_differentiate(a, xvar, z, eo)) {
156 return false;
157 }
158 MathStructure g;
159 if(!MathStructure::gcd(w, z, g, eo)) {
160 return false;
161 }
162 if(g.isOne()) {
163 factors.addChild(a);
164 return true;
165 }
166 MathStructure y;
167 MathStructure tmp;
168 do {
169 tmp = w;
170 if(!MathStructure::polynomialQuotient(tmp, g, xvar, w, eo)) {
171 return false;
172 }
173 if(!MathStructure::polynomialQuotient(z, g, xvar, y, eo)) {
174 return false;
175 }
176 if(!sqrfree_differentiate(w, xvar, tmp, eo)) {
177 return false;
178 }
179 z = y;
180 z.calculateSubtract(tmp, eo);
181 if(!MathStructure::gcd(w, z, g, eo)) {
182 return false;
183 }
184 factors.addChild(g);
185 } while (!z.isZero());
186 return true;
187 }
188
sqrfree_simple(const MathStructure & a,const MathStructure & xvar,MathStructure & factors,const EvaluationOptions & eo)189 bool sqrfree_simple(const MathStructure &a, const MathStructure &xvar, MathStructure &factors, const EvaluationOptions &eo) {
190 MathStructure w(a);
191 size_t i = 0;
192 while(true) {
193 MathStructure z, zmod;
194 if(!sqrfree_differentiate(w, xvar, z, eo)) return false;
195 polynomial_smod(z, nr_three, zmod, eo);
196 if(z == w) {
197 factors.addChild(w);
198 break;
199 }
200 MathStructure mgcd;
201 if(!MathStructure::gcd(w, z, mgcd, eo)) return false;
202 if(mgcd.isOne() || mgcd == w) {
203 factors.addChild(w);
204 break;
205 }
206 MathStructure tmp(w);
207 if(!MathStructure::polynomialQuotient(tmp, mgcd, xvar, w, eo)) return false;
208 if(!sqrfree_simple(mgcd, xvar, factors, eo)) return false;
209 i++;
210 }
211 return true;
212 }
213
214 void lcmcoeff(const MathStructure &e, const Number &l, Number &nlcm);
lcmcoeff(const MathStructure & e,const Number & l,Number & nlcm)215 void lcmcoeff(const MathStructure &e, const Number &l, Number &nlcm) {
216 if(e.isNumber() && e.number().isRational()) {
217 nlcm = e.number().denominator();
218 nlcm.lcm(l);
219 } else if(e.isAddition()) {
220 nlcm.set(1, 1, 0);
221 for(size_t i = 0; i < e.size(); i++) {
222 Number c(nlcm);
223 lcmcoeff(e[i], c, nlcm);
224 }
225 nlcm.lcm(l);
226 } else if(e.isMultiplication()) {
227 nlcm.set(1, 1, 0);
228 for(size_t i = 0; i < e.size(); i++) {
229 Number c(nlcm);
230 lcmcoeff(e[i], nr_one, c);
231 nlcm *= c;
232 }
233 nlcm.lcm(l);
234 } else if(e.isPower()) {
235 if(IS_A_SYMBOL(e[0]) || e[0].isUnit()) {
236 nlcm = l;
237 } else {
238 lcmcoeff(e[0], l, nlcm);
239 nlcm ^= e[1].number();
240 }
241 } else {
242 nlcm = l;
243 }
244 }
245
lcm_of_coefficients_denominators(const MathStructure & e,Number & nlcm)246 void lcm_of_coefficients_denominators(const MathStructure &e, Number &nlcm) {
247 return lcmcoeff(e, nr_one, nlcm);
248 }
249
multiply_lcm(const MathStructure & e,const Number & lcm,MathStructure & mmul,const EvaluationOptions & eo)250 void multiply_lcm(const MathStructure &e, const Number &lcm, MathStructure &mmul, const EvaluationOptions &eo) {
251 if(e.isMultiplication()) {
252 Number lcm_accum(1, 1);
253 mmul.clear();
254 for(size_t i = 0; i < e.size(); i++) {
255 Number op_lcm;
256 lcmcoeff(e[i], nr_one, op_lcm);
257 if(mmul.isZero()) {
258 multiply_lcm(e[i], op_lcm, mmul, eo);
259 if(mmul.isOne()) mmul.clear();
260 } else {
261 mmul.multiply(m_one, true);
262 multiply_lcm(e[i], op_lcm, mmul[mmul.size() - 1], eo);
263 if(mmul[mmul.size() - 1].isOne()) {
264 mmul.delChild(i + 1);
265 if(mmul.size() == 1) mmul.setToChild(1);
266 }
267 }
268 lcm_accum *= op_lcm;
269 }
270 Number lcm2(lcm);
271 lcm2 /= lcm_accum;
272 if(mmul.isZero()) {
273 mmul = lcm2;
274 } else if(!lcm2.isOne()) {
275 if(mmul.size() > 0 && mmul[0].isNumber()) {
276 mmul[0].number() *= lcm2;
277 } else {
278 mmul.multiply(lcm2, true);
279 }
280 }
281 mmul.evalSort();
282 } else if(e.isAddition()) {
283 mmul.clear();
284 for (size_t i = 0; i < e.size(); i++) {
285 if(mmul.isZero()) {
286 multiply_lcm(e[i], lcm, mmul, eo);
287 } else {
288 mmul.add(m_zero, true);
289 multiply_lcm(e[i], lcm, mmul[mmul.size() - 1], eo);
290 }
291 }
292 mmul.evalSort();
293 } else if(e.isPower()) {
294 if(IS_A_SYMBOL(e[0]) || e[0].isUnit()) {
295 mmul = e;
296 if(!lcm.isOne()) {
297 mmul *= lcm;
298 mmul.evalSort();
299 }
300 } else {
301 mmul = e;
302 Number lcm_exp = e[1].number();
303 lcm_exp.recip();
304 multiply_lcm(e[0], lcm ^ lcm_exp, mmul[0], eo);
305 if(mmul[0] != e[0]) {
306 mmul.calculatesub(eo, eo, false);
307 }
308 }
309 } else if(e.isNumber()) {
310 mmul = e;
311 mmul.number() *= lcm;
312 } else if(IS_A_SYMBOL(e) || e.isUnit()) {
313 mmul = e;
314 if(!lcm.isOne()) {
315 mmul *= lcm;
316 mmul.evalSort();
317 }
318 } else {
319 mmul = e;
320 if(!lcm.isOne()) {
321 mmul.calculateMultiply(lcm, eo);
322 mmul.evalSort();
323 }
324 }
325 }
326
327 //from GiNaC
sqrfree(MathStructure & mpoly,const EvaluationOptions & eo)328 bool sqrfree(MathStructure &mpoly, const EvaluationOptions &eo) {
329 vector<MathStructure> symbols;
330 collect_symbols(mpoly, symbols);
331 return sqrfree(mpoly, symbols, eo);
332 }
sqrfree(MathStructure & mpoly,const vector<MathStructure> & symbols,const EvaluationOptions & eo)333 bool sqrfree(MathStructure &mpoly, const vector<MathStructure> &symbols, const EvaluationOptions &eo) {
334
335 EvaluationOptions eo2 = eo;
336 eo2.assume_denominators_nonzero = true;
337 eo2.warn_about_denominators_assumed_nonzero = false;
338 eo2.reduce_divisions = true;
339 eo2.keep_zero_units = false;
340 eo2.do_polynomial_division = false;
341 eo2.sync_units = false;
342 eo2.expand = true;
343 eo2.calculate_functions = false;
344 eo2.protected_function = CALCULATOR->getFunctionById(FUNCTION_ID_SIGNUM);
345
346 if(mpoly.size() == 0) {
347 return true;
348 }
349 if(symbols.empty()) return true;
350
351 size_t symbol_index = 0;
352 if(symbols.size() > 1) {
353 for(size_t i = 1; i < symbols.size(); i++) {
354 if(mpoly.degree(symbols[symbol_index]).isGreaterThan(mpoly.degree(symbols[i]))) symbol_index = i;
355 }
356 }
357
358 MathStructure xvar(symbols[symbol_index]);
359
360 UnknownVariable *var = NULL;
361 if(xvar.size() > 0) {
362 var = new UnknownVariable("", format_and_print(xvar));
363 var->setAssumptions(xvar);
364 mpoly.replace(xvar, var);
365 xvar = var;
366 }
367
368 Number nlcm;
369 lcm_of_coefficients_denominators(mpoly, nlcm);
370
371 MathStructure tmp;
372 multiply_lcm(mpoly, nlcm, tmp, eo2);
373
374 MathStructure factors;
375 factors.clearVector();
376
377 if(!sqrfree_yun(tmp, xvar, factors, eo2)) {
378 if(var) tmp.replace(var, symbols[symbol_index]);
379 factors.clearVector();
380 factors.addChild(tmp);
381 } else {
382 if(var) tmp.replace(var, symbols[symbol_index]);
383 }
384 if(var) {mpoly.replace(var, symbols[symbol_index]); var->destroy();}
385
386 vector<MathStructure> newsymbols;
387 for(size_t i = 0; i < symbols.size(); i++) {
388 if(i != symbol_index) newsymbols.push_back(symbols[i]);
389 }
390
391 if(newsymbols.size() > 0) {
392 for(size_t i = 0; i < factors.size(); i++) {
393 if(!sqrfree(factors[i], newsymbols, eo)) return false;
394 }
395 }
396
397 mpoly.set(1, 1, 0);
398 for(size_t i = 0; i < factors.size(); i++) {
399 if(CALCULATOR->aborted()) return false;
400 if(!factors[i].isOne()) {
401 if(mpoly.isOne()) {
402 mpoly = factors[i];
403 if(i != 0) mpoly.raise(MathStructure((long int) i + 1, 1L, 0L));
404 } else {
405 mpoly.multiply(factors[i], true);
406 mpoly[mpoly.size() - 1].raise(MathStructure((long int) i + 1, 1L, 0L));
407 }
408 }
409 }
410
411 if(CALCULATOR->aborted()) return false;
412 if(mpoly.isZero()) {
413 CALCULATOR->error(true, "mpoly is zero: %s. %s", format_and_print(tmp).c_str(), _("This is a bug. Please report it."), NULL);
414 return false;
415 }
416 MathStructure mquo;
417 MathStructure mpoly_expand(mpoly);
418 EvaluationOptions eo3 = eo;
419 eo3.expand = true;
420 mpoly_expand.calculatesub(eo3, eo3);
421
422 MathStructure::polynomialQuotient(tmp, mpoly_expand, xvar, mquo, eo2);
423
424 if(CALCULATOR->aborted()) return false;
425 if(mquo.isZero()) {
426 //CALCULATOR->error(true, "quo is zero: %s. %s", format_and_print(tmp).c_str(), _("This is a bug. Please report it."), NULL);
427 return false;
428 }
429 if(newsymbols.size() > 0) {
430 if(!sqrfree(mquo, newsymbols, eo)) return false;
431 }
432 if(!mquo.isOne()) {
433 mpoly.multiply(mquo, true);
434 }
435 if(!nlcm.isOne()) {
436 nlcm.recip();
437 mpoly.multiply(nlcm, true);
438 }
439
440 eo3.expand = false;
441 mpoly.calculatesub(eo3, eo3, false);
442
443 return true;
444
445 }
446
integerFactorize()447 bool MathStructure::integerFactorize() {
448 if(!isNumber()) return false;
449 vector<Number> factors;
450 if(!o_number.factorize(factors)) return false;
451 if(factors.size() <= 1) return true;
452 clear(true);
453 bool b_pow = false;
454 Number *lastnr = NULL;
455 for(size_t i = 0; i < factors.size(); i++) {
456 if(lastnr && factors[i] == *lastnr) {
457 if(!b_pow) {
458 LAST.raise(m_one);
459 b_pow = true;
460 }
461 LAST[1].number()++;
462 } else {
463 APPEND(factors[i]);
464 b_pow = false;
465 }
466 lastnr = &factors[i];
467 }
468 m_type = STRUCT_MULTIPLICATION;
469 return true;
470 }
count_powers(const MathStructure & mstruct)471 size_t count_powers(const MathStructure &mstruct) {
472 if(mstruct.isPower()) {
473 if(mstruct[1].isInteger()) {
474 bool overflow = false;
475 int c = mstruct.number().intValue(&overflow) - 1;
476 if(overflow) return 0;
477 if(c < 0) return -c;
478 return c;
479 }
480 }
481 size_t c = 0;
482 for(size_t i = 0; i < mstruct.size(); i++) {
483 c += count_powers(mstruct[i]);
484 }
485 return c;
486 }
487
gather_factors(const MathStructure & mstruct,const MathStructure & x_var,MathStructure & madd,MathStructure & mmul,MathStructure & mexp,bool mexp_as_x2=false)488 bool gather_factors(const MathStructure &mstruct, const MathStructure &x_var, MathStructure &madd, MathStructure &mmul, MathStructure &mexp, bool mexp_as_x2 = false) {
489 madd.clear();
490 if(mexp_as_x2) mexp = m_zero;
491 else mexp = m_one;
492 mmul = m_zero;
493 if(mstruct == x_var) {
494 mmul = m_one;
495 return true;
496 } else if(mexp_as_x2 && mstruct.isPower()) {
497 if(mstruct[1].isNumber() && mstruct[1].number().isTwo() && mstruct[0] == x_var) {
498 mexp = m_one;
499 return true;
500 }
501 } else if(!mexp_as_x2 && mstruct.isPower() && mstruct[1].isInteger() && mstruct[0] == x_var) {
502 if(mstruct[0] == x_var) {
503 mexp = mstruct[1];
504 mmul = m_one;
505 return true;
506 }
507 } else if(mstruct.isMultiplication() && mstruct.size() >= 2) {
508 bool b_x = false;
509 bool b2 = false;
510 size_t i_x = 0;
511 for(size_t i = 0; i < mstruct.size(); i++) {
512 if(!b_x && mstruct[i] == x_var) {
513 b_x = true;
514 i_x = i;
515 } else if(!b_x && mexp_as_x2 && mstruct[i].isPower() && mstruct[i][1].isNumber() && mstruct[i][1].number().isTwo() && mstruct[i][0] == x_var) {
516 b_x = true;
517 b2 = true;
518 i_x = i;
519 } else if(!b_x && !mexp_as_x2 && mstruct[i].isPower() && mstruct[i][1].isInteger() && mstruct[i][0] == x_var) {
520 b_x = true;
521 i_x = i;
522 mexp = mstruct[i][1];
523 } else if(mstruct[i].containsRepresentativeOf(x_var, true, true) != 0) {
524 return false;
525 }
526 }
527 if(!b_x) return false;
528 if(mstruct.size() == 1) {
529 if(b2) mexp = m_one;
530 else mmul = m_one;
531 } else if(mstruct.size() == 2) {
532 if(b2) {
533 if(i_x == 1) mexp = mstruct[0];
534 else mexp = mstruct[1];
535 } else {
536 if(i_x == 1) mmul = mstruct[0];
537 else mmul = mstruct[1];
538 }
539 } else {
540 if(b2) {
541 mexp = mstruct;
542 mexp.delChild(i_x + 1, true);
543 } else {
544 mmul = mstruct;
545 mmul.delChild(i_x + 1, true);
546 }
547 }
548 return true;
549 } else if(mstruct.isAddition()) {
550 mmul.setType(STRUCT_ADDITION);
551 if(mexp_as_x2) mexp.setType(STRUCT_ADDITION);
552 madd.setType(STRUCT_ADDITION);
553 for(size_t i = 0; i < mstruct.size(); i++) {
554 if(mstruct[i] == x_var) {
555 if(mexp_as_x2 || mexp.isOne()) mmul.addChild(m_one);
556 else return false;
557 } else if(mexp_as_x2 && mstruct[i].isPower() && mstruct[i][1].isNumber() && mstruct[i][1].number().isTwo() && mstruct[i][0] == x_var) {
558 mexp.addChild(m_one);
559 } else if(!mexp_as_x2 && mstruct[i].isPower() && mstruct[i][1].isInteger() && mstruct[i][0] == x_var) {
560 if(mmul.size() == 0) {
561 mexp = mstruct[i][1];
562 } else if(mexp != mstruct[i][1]) {
563 return false;
564 }
565 mmul.addChild(m_one);
566 } else if(mstruct[i].isMultiplication()) {
567 bool b_x = false;
568 bool b2 = false;
569 size_t i_x = 0;
570 for(size_t i2 = 0; i2 < mstruct[i].size(); i2++) {
571 if(!b_x && mstruct[i][i2] == x_var) {
572 if(!mexp_as_x2 && !mexp.isOne()) return false;
573 i_x = i2;
574 b_x = true;
575 } else if(!b_x && mexp_as_x2 && mstruct[i][i2].isPower() && mstruct[i][i2][1].isNumber() && mstruct[i][i2][1].number().isTwo() && mstruct[i][i2][0] == x_var) {
576 b2 = true;
577 i_x = i2;
578 b_x = true;
579 } else if(!b_x && !mexp_as_x2 && mstruct[i][i2].isPower() && mstruct[i][i2][1].isInteger() && mstruct[i][i2][0] == x_var) {
580 if(mmul.size() == 0) {
581 mexp = mstruct[i][i2][1];
582 } else if(mexp != mstruct[i][i2][1]) {
583 return false;
584 }
585 i_x = i2;
586 b_x = true;
587 } else if(mstruct[i][i2].containsRepresentativeOf(x_var, true, true) != 0) {
588 return false;
589 }
590 }
591 if(b_x) {
592 if(mstruct[i].size() == 1) {
593 if(b2) mexp.addChild(m_one);
594 else mmul.addChild(m_one);
595 } else {
596 if(b2) {
597 mexp.addChild(mstruct[i]);
598 mexp[mexp.size() - 1].delChild(i_x + 1, true);
599 mexp.childUpdated(mexp.size());
600 } else {
601 mmul.addChild(mstruct[i]);
602 mmul[mmul.size() - 1].delChild(i_x + 1, true);
603 mmul.childUpdated(mmul.size());
604 }
605 }
606 } else {
607 madd.addChild(mstruct[i]);
608 }
609 } else if(mstruct[i].containsRepresentativeOf(x_var, true, true) != 0) {
610 return false;
611 } else {
612 madd.addChild(mstruct[i]);
613 }
614 }
615 if(mmul.size() == 0 && (!mexp_as_x2 || mexp.size() == 0)) {
616 mmul.clear();
617 if(mexp_as_x2) mexp.clear();
618 return false;
619 }
620 if(mmul.size() == 0) mmul.clear();
621 else if(mmul.size() == 1) mmul.setToChild(1);
622 if(mexp_as_x2) {
623 if(mexp.size() == 0) mexp.clear();
624 else if(mexp.size() == 1) mexp.setToChild(1);
625 }
626 if(madd.size() == 0) madd.clear();
627 else if(madd.size() == 1) madd.setToChild(1);
628 return true;
629 }
630 return false;
631 }
632
factorize_find_multiplier(const MathStructure & mstruct,MathStructure & mnew,MathStructure & factor_mstruct,bool only_units)633 bool factorize_find_multiplier(const MathStructure &mstruct, MathStructure &mnew, MathStructure &factor_mstruct, bool only_units) {
634 factor_mstruct.set(m_one);
635 switch(mstruct.type()) {
636 case STRUCT_ADDITION: {
637 if(!only_units) {
638 bool bfrac = false, bint = true;
639 idm1(mstruct, bfrac, bint);
640 if(bfrac || bint) {
641 Number gcd(1, 1);
642 idm2(mstruct, bfrac, bint, gcd);
643 if((bint || bfrac) && !gcd.isOne()) {
644 if(bfrac) gcd.recip();
645 factor_mstruct.set(gcd);
646 }
647 }
648 }
649 if(mstruct.size() > 0) {
650 size_t i = 0;
651 const MathStructure *cur_mstruct;
652 while(true) {
653 if(mstruct[0].isMultiplication()) {
654 if(i >= mstruct[0].size()) {
655 break;
656 }
657 cur_mstruct = &mstruct[0][i];
658 } else {
659 cur_mstruct = &mstruct[0];
660 }
661 if(!cur_mstruct->containsInterval(true) && !cur_mstruct->isNumber() && (!only_units || cur_mstruct->isUnit_exp())) {
662 const MathStructure *exp = NULL;
663 const MathStructure *bas;
664 if(cur_mstruct->isPower() && IS_REAL((*cur_mstruct)[1]) && !(*cur_mstruct)[0].isNumber()) {
665 exp = cur_mstruct->exponent();
666 bas = cur_mstruct->base();
667 } else {
668 bas = cur_mstruct;
669 }
670 bool b = true;
671 for(size_t i2 = 1; i2 < mstruct.size(); i2++) {
672 b = false;
673 size_t i3 = 0;
674 const MathStructure *cmp_mstruct;
675 while(true) {
676 if(mstruct[i2].isMultiplication()) {
677 if(i3 >= mstruct[i2].size()) {
678 break;
679 }
680 cmp_mstruct = &mstruct[i2][i3];
681 } else {
682 cmp_mstruct = &mstruct[i2];
683 }
684 if(cmp_mstruct->equals(*bas)) {
685 if(exp) {
686 exp = NULL;
687 }
688 b = true;
689 break;
690 } else if(cmp_mstruct->isPower() && IS_REAL((*cmp_mstruct)[1]) && cmp_mstruct->base()->equals(*bas)) {
691 if(exp) {
692 if(cmp_mstruct->exponent()->number().isLessThan(exp->number())) {
693 exp = cmp_mstruct->exponent();
694 }
695 b = true;
696 break;
697 } else {
698 b = true;
699 break;
700 }
701 }
702 if(!mstruct[i2].isMultiplication()) {
703 break;
704 }
705 i3++;
706 }
707 if(!b) break;
708 }
709 if(b) {
710 b = !factor_mstruct.isOne();
711 if(exp) {
712 MathStructure *mstruct = new MathStructure(*bas);
713 mstruct->raise(*exp);
714 if(factor_mstruct.isOne()) {
715 factor_mstruct.set_nocopy(*mstruct);
716 mstruct->unref();
717 } else {
718 factor_mstruct.multiply_nocopy(mstruct, true);
719 }
720 } else {
721 if(factor_mstruct.isOne()) factor_mstruct.set(*bas);
722 else factor_mstruct.multiply(*bas, true);
723 }
724 if(b) {
725 size_t i3 = 0;
726 const MathStructure *cmp_mstruct;
727 b = false;
728 while(true) {
729 if(i3 >= factor_mstruct.size() - 1) {
730 break;
731 }
732 cmp_mstruct = &factor_mstruct[i3];
733 if(cmp_mstruct->equals(factor_mstruct.last())) {
734 if(exp) {
735 exp = NULL;
736 }
737 b = true;
738 break;
739 } else if(cmp_mstruct->isPower() && IS_REAL((*cmp_mstruct)[1]) && cmp_mstruct->base()->equals(factor_mstruct.last())) {
740 if(exp) {
741 if(cmp_mstruct->exponent()->number().isLessThan(exp->number())) {
742 exp = cmp_mstruct->exponent();
743 }
744 b = true;
745 break;
746 } else {
747 b = true;
748 break;
749 }
750 }
751 i3++;
752 }
753 if(b) factor_mstruct.delChild(factor_mstruct.size(), true);
754 }
755 }
756 }
757 if(!mstruct[0].isMultiplication()) {
758 break;
759 }
760 i++;
761 }
762 }
763 if(!factor_mstruct.isOne()) {
764 if(&mstruct != &mnew) mnew.set(mstruct);
765 MathStructure *mfactor;
766 size_t i = 0;
767 while(true) {
768 if(factor_mstruct.isMultiplication()) {
769 if(i >= factor_mstruct.size()) break;
770 mfactor = &factor_mstruct[i];
771 } else {
772 mfactor = &factor_mstruct;
773 }
774 for(size_t i2 = 0; i2 < mnew.size(); i2++) {
775 switch(mnew[i2].type()) {
776 case STRUCT_NUMBER: {
777 if(mfactor->isNumber()) {
778 mnew[i2].number() /= mfactor->number();
779 }
780 break;
781 }
782 case STRUCT_POWER: {
783 if(!IS_REAL(mnew[i2][1])) {
784 if(mfactor->isNumber()) {
785 mnew[i2].transform(STRUCT_MULTIPLICATION);
786 mnew[i2].insertChild(MathStructure(1, 1, 0), 1);
787 mnew[i2][0].number() /= mfactor->number();
788 } else {
789 mnew[i2].set(m_one);
790 }
791 } else if(mfactor->isNumber()) {
792 mnew[i2].transform(STRUCT_MULTIPLICATION);
793 mnew[i2].insertChild(MathStructure(1, 1, 0), 1);
794 mnew[i2][0].number() /= mfactor->number();
795 } else if(mfactor->isPower() && IS_REAL((*mfactor)[1])) {
796 if(mfactor->equals(mnew[i2])) {
797 mnew[i2].set(m_one);
798 } else {
799 mnew[i2][1].number() -= mfactor->exponent()->number();
800 if(mnew[i2][1].number().isOne()) {
801 mnew[i2].setToChild(1, true);
802 } else if(factorize_fix_root_power(mnew[i2])) {
803 mnew.childUpdated(i2 + 1);
804 }
805 }
806 } else {
807 mnew[i2][1].number() -= 1;
808 if(mnew[i2][1].number().isOne()) {
809 mnew[i2].setToChild(1);
810 } else if(mnew[i2][1].number().isZero()) {
811 mnew[i2].set(m_one);
812 } else if(factorize_fix_root_power(mnew[i2])) {
813 mnew.childUpdated(i2 + 1);
814 }
815 }
816 break;
817 }
818 case STRUCT_MULTIPLICATION: {
819 bool b = true;
820 if(mfactor->isNumber() && (mnew[i2].size() < 1 || !mnew[i2][0].isNumber())) {
821 mnew[i2].insertChild(MathStructure(1, 1, 0), 1);
822 }
823 for(size_t i3 = 0; i3 < mnew[i2].size() && b; i3++) {
824 switch(mnew[i2][i3].type()) {
825 case STRUCT_NUMBER: {
826 if(mfactor->isNumber()) {
827 if(mfactor->equals(mnew[i2][i3])) {
828 mnew[i2].delChild(i3 + 1);
829 } else {
830 mnew[i2][i3].number() /= mfactor->number();
831 }
832 b = false;
833 }
834 break;
835 }
836 case STRUCT_POWER: {
837 if(!IS_REAL(mnew[i2][i3][1])) {
838 if(mfactor->equals(mnew[i2][i3])) {
839 mnew[i2].delChild(i3 + 1);
840 b = false;
841 }
842 } else if(mfactor->isPower() && IS_REAL((*mfactor)[1]) && mfactor->base()->equals(mnew[i2][i3][0])) {
843 if(mfactor->equals(mnew[i2][i3])) {
844 mnew[i2].delChild(i3 + 1);
845 } else {
846 mnew[i2][i3][1].number() -= mfactor->exponent()->number();
847 if(mnew[i2][i3][1].number().isOne()) {
848 MathStructure mstruct2(mnew[i2][i3][0]);
849 mnew[i2][i3] = mstruct2;
850 } else if(mnew[i2][i3][1].number().isZero()) {
851 mnew[i2].delChild(i3 + 1);
852 } else if(factorize_fix_root_power(mnew[i2][i3])) {
853 mnew[i2].childUpdated(i3 + 1);
854 mnew.childUpdated(i2 + 1);
855 }
856 }
857 b = false;
858 } else if(mfactor->equals(mnew[i2][i3][0])) {
859 if(mnew[i2][i3][1].number() == 2) {
860 MathStructure mstruct2(mnew[i2][i3][0]);
861 mnew[i2][i3] = mstruct2;
862 } else if(mnew[i2][i3][1].number().isOne()) {
863 mnew[i2].delChild(i3 + 1);
864 } else {
865 mnew[i2][i3][1].number() -= 1;
866 if(factorize_fix_root_power(mnew[i2][i3])) {
867 mnew[i2].childUpdated(i3 + 1);
868 mnew.childUpdated(i2 + 1);
869 }
870 }
871 b = false;
872 }
873 break;
874 }
875 default: {
876 if(mfactor->equals(mnew[i2][i3])) {
877 mnew[i2].delChild(i3 + 1);
878 b = false;
879 }
880 }
881 }
882 }
883 if(mnew[i2].size() == 1) {
884 MathStructure mstruct2(mnew[i2][0]);
885 mnew[i2] = mstruct2;
886 }
887 break;
888 }
889 default: {
890 if(mfactor->isNumber()) {
891 mnew[i2].transform(STRUCT_MULTIPLICATION);
892 mnew[i2].insertChild(MathStructure(1, 1, 0), 1);
893 mnew[i2][0].number() /= mfactor->number();
894 } else {
895 mnew[i2].set(m_one);
896 }
897 }
898 }
899 }
900 if(factor_mstruct.isMultiplication()) {
901 i++;
902 } else {
903 break;
904 }
905 }
906 return true;
907 }
908 }
909 default: {}
910 }
911 return false;
912 }
913
polynomial_divide_integers(const vector<Number> & vnum,const vector<Number> & vden,vector<Number> & vquotient)914 bool polynomial_divide_integers(const vector<Number> &vnum, const vector<Number> &vden, vector<Number> &vquotient) {
915
916 vquotient.clear();
917
918 long int numdeg = vnum.size() - 1;
919 long int dendeg = vden.size() - 1;
920 Number dencoeff(vden[dendeg]);
921
922 if(numdeg < dendeg) return false;
923
924 vquotient.resize(numdeg - dendeg + 1, nr_zero);
925
926 vector<Number> vrem = vnum;
927
928 while(numdeg >= dendeg) {
929 Number numcoeff(vrem[numdeg]);
930 numdeg -= dendeg;
931 if(!numcoeff.isIntegerDivisible(dencoeff)) break;
932 numcoeff /= dencoeff;
933 vquotient[numdeg] += numcoeff;
934 for(size_t i = 0; i < vden.size(); i++) {
935 vrem[numdeg + i] -= (vden[i] * numcoeff);
936 }
937 while(true) {
938 if(vrem.back().isZero()) vrem.pop_back();
939 else break;
940 if(vrem.size() == 0) return true;
941 }
942 numdeg = (long int) vrem.size() - 1;
943 }
944 return false;
945 }
946
combination_factorize_is_complicated(MathStructure & m)947 bool combination_factorize_is_complicated(MathStructure &m) {
948 if(m.isPower()) {
949 return combination_factorize_is_complicated(m[0]) || combination_factorize_is_complicated(m[1]);
950 }
951 return m.size() > 0;
952 }
953
combination_factorize(MathStructure & mstruct)954 bool combination_factorize(MathStructure &mstruct) {
955 bool retval = false;
956 switch(mstruct.type()) {
957 case STRUCT_ADDITION: {
958 bool b = false;
959 // 5/y + x/y + z = (5 + x)/y + z
960 MathStructure mstruct_units(mstruct);
961 MathStructure mstruct_new(mstruct);
962 for(size_t i = 0; i < mstruct_units.size(); i++) {
963 if(mstruct_units[i].isMultiplication()) {
964 for(size_t i2 = 0; i2 < mstruct_units[i].size();) {
965 if(!mstruct_units[i][i2].isPower() || !mstruct_units[i][i2][1].hasNegativeSign()) {
966 mstruct_units[i].delChild(i2 + 1);
967 } else {
968 i2++;
969 }
970 }
971 if(mstruct_units[i].size() == 0) mstruct_units[i].setUndefined();
972 else if(mstruct_units[i].size() == 1) mstruct_units[i].setToChild(1);
973 for(size_t i2 = 0; i2 < mstruct_new[i].size();) {
974 if(mstruct_new[i][i2].isPower() && mstruct_new[i][i2][1].hasNegativeSign()) {
975 mstruct_new[i].delChild(i2 + 1);
976 } else {
977 i2++;
978 }
979 }
980 if(mstruct_new[i].size() == 0) mstruct_new[i].set(1, 1, 0);
981 else if(mstruct_new[i].size() == 1) mstruct_new[i].setToChild(1);
982 } else if(mstruct_new[i].isPower() && mstruct_new[i][1].hasNegativeSign()) {
983 mstruct_new[i].set(1, 1, 0);
984 } else {
985 mstruct_units[i].setUndefined();
986 }
987 }
988 for(size_t i = 0; i < mstruct_units.size(); i++) {
989 if(!mstruct_units[i].isUndefined()) {
990 for(size_t i2 = i + 1; i2 < mstruct_units.size();) {
991 if(mstruct_units[i2] == mstruct_units[i]) {
992 mstruct_new[i].add(mstruct_new[i2], true);
993 mstruct_new.delChild(i2 + 1);
994 mstruct_units.delChild(i2 + 1);
995 b = true;
996 } else {
997 i2++;
998 }
999 }
1000 if(mstruct_new[i].isOne()) mstruct_new[i].set(mstruct_units[i]);
1001 else mstruct_new[i].multiply(mstruct_units[i], true);
1002 }
1003 }
1004 if(b) {
1005 if(mstruct_new.size() == 1) {
1006 mstruct.set(mstruct_new[0], true);
1007 } else {
1008 mstruct = mstruct_new;
1009 }
1010 b = false;
1011 retval = true;
1012 }
1013 if(mstruct.isAddition()) {
1014 // y*f(x) + z*f(x) = (y+z)*f(x)
1015 MathStructure mstruct_units(mstruct);
1016 MathStructure mstruct_new(mstruct);
1017 for(size_t i = 0; i < mstruct_units.size(); i++) {
1018 if(mstruct_units[i].isMultiplication()) {
1019 for(size_t i2 = 0; i2 < mstruct_units[i].size();) {
1020 if(!combination_factorize_is_complicated(mstruct_units[i][i2])) {
1021 mstruct_units[i].delChild(i2 + 1);
1022 } else {
1023 i2++;
1024 }
1025 }
1026 if(mstruct_units[i].size() == 0) mstruct_units[i].setUndefined();
1027 else if(mstruct_units[i].size() == 1) mstruct_units[i].setToChild(1);
1028 for(size_t i2 = 0; i2 < mstruct_new[i].size();) {
1029 if(combination_factorize_is_complicated(mstruct_new[i][i2])) {
1030 mstruct_new[i].delChild(i2 + 1);
1031 } else {
1032 i2++;
1033 }
1034 }
1035 if(mstruct_new[i].size() == 0) mstruct_new[i].set(1, 1, 0);
1036 else if(mstruct_new[i].size() == 1) mstruct_new[i].setToChild(1);
1037 } else if(combination_factorize_is_complicated(mstruct_units[i])) {
1038 mstruct_new[i].set(1, 1, 0);
1039 } else {
1040 mstruct_units[i].setUndefined();
1041 }
1042 }
1043 for(size_t i = 0; i < mstruct_units.size(); i++) {
1044 if(!mstruct_units[i].isUndefined()) {
1045 for(size_t i2 = i + 1; i2 < mstruct_units.size();) {
1046 if(mstruct_units[i2] == mstruct_units[i]) {
1047 mstruct_new[i].add(mstruct_new[i2], true);
1048 mstruct_new.delChild(i2 + 1);
1049 mstruct_units.delChild(i2 + 1);
1050 b = true;
1051 } else {
1052 i2++;
1053 }
1054 }
1055 if(mstruct_new[i].isOne()) mstruct_new[i].set(mstruct_units[i]);
1056 else mstruct_new[i].multiply(mstruct_units[i], true);
1057 }
1058 }
1059 if(b) {
1060 if(mstruct_new.size() == 1) mstruct.set(mstruct_new[0], true);
1061 else mstruct = mstruct_new;
1062 retval = true;
1063 }
1064 }
1065 if(mstruct.isAddition()) {
1066 // 5x + pi*x + 5y + xy = (5 + pi)x + 5y + xy
1067 MathStructure mstruct_units(mstruct);
1068 MathStructure mstruct_new(mstruct);
1069 for(size_t i = 0; i < mstruct_units.size(); i++) {
1070 if(mstruct_units[i].isMultiplication()) {
1071 for(size_t i2 = 0; i2 < mstruct_units[i].size();) {
1072 if(!mstruct_units[i][i2].containsType(STRUCT_UNIT, true) && !mstruct_units[i][i2].containsUnknowns()) {
1073 mstruct_units[i].delChild(i2 + 1);
1074 } else {
1075 i2++;
1076 }
1077 }
1078 if(mstruct_units[i].size() == 0) mstruct_units[i].setUndefined();
1079 else if(mstruct_units[i].size() == 1) mstruct_units[i].setToChild(1);
1080 for(size_t i2 = 0; i2 < mstruct_new[i].size();) {
1081 if(mstruct_new[i][i2].containsType(STRUCT_UNIT, true) || mstruct_new[i][i2].containsUnknowns()) {
1082 mstruct_new[i].delChild(i2 + 1);
1083 } else {
1084 i2++;
1085 }
1086 }
1087 if(mstruct_new[i].size() == 0) mstruct_new[i].set(1, 1, 0);
1088 else if(mstruct_new[i].size() == 1) mstruct_new[i].setToChild(1);
1089 } else if(mstruct_units[i].containsType(STRUCT_UNIT, true) || mstruct_units[i].containsUnknowns()) {
1090 mstruct_new[i].set(1, 1, 0);
1091 } else {
1092 mstruct_units[i].setUndefined();
1093 }
1094 }
1095 for(size_t i = 0; i < mstruct_units.size(); i++) {
1096 if(!mstruct_units[i].isUndefined()) {
1097 for(size_t i2 = i + 1; i2 < mstruct_units.size();) {
1098 if(mstruct_units[i2] == mstruct_units[i]) {
1099 mstruct_new[i].add(mstruct_new[i2], true);
1100 mstruct_new.delChild(i2 + 1);
1101 mstruct_units.delChild(i2 + 1);
1102 b = true;
1103 } else {
1104 i2++;
1105 }
1106 }
1107 if(mstruct_new[i].isOne()) mstruct_new[i].set(mstruct_units[i]);
1108 else mstruct_new[i].multiply(mstruct_units[i], true);
1109 }
1110 }
1111 if(b) {
1112 if(mstruct_new.size() == 1) mstruct.set(mstruct_new[0], true);
1113 else mstruct = mstruct_new;
1114 retval = true;
1115 }
1116 }
1117 //if(retval) return retval;
1118 }
1119 default: {
1120 bool b = false;
1121 for(size_t i = 0; i < mstruct.size(); i++) {
1122 if(combination_factorize(mstruct[i])) {
1123 mstruct.childUpdated(i);
1124 b = true;
1125 }
1126 }
1127 if(b) retval = true;
1128 }
1129 }
1130 return retval;
1131 }
1132
factorize(const EvaluationOptions & eo_pre,bool unfactorize,int term_combination_levels,int max_msecs,bool only_integers,int recursive,struct timeval * endtime_p,const MathStructure & force_factorization,bool complete_square,bool only_sqrfree,int max_factor_degree)1133 bool MathStructure::factorize(const EvaluationOptions &eo_pre, bool unfactorize, int term_combination_levels, int max_msecs, bool only_integers, int recursive, struct timeval *endtime_p, const MathStructure &force_factorization, bool complete_square, bool only_sqrfree, int max_factor_degree) {
1134
1135 if(CALCULATOR->aborted()) return false;
1136 struct timeval endtime;
1137 if(max_msecs > 0 && !endtime_p) {
1138 #ifndef CLOCK_MONOTONIC
1139 gettimeofday(&endtime, NULL);
1140 #else
1141 struct timespec ts;
1142 clock_gettime(CLOCK_MONOTONIC, &ts);
1143 endtime.tv_sec = ts.tv_sec;
1144 endtime.tv_usec = ts.tv_nsec / 1000;
1145 #endif
1146 endtime.tv_sec += max_msecs / 1000;
1147 long int usecs = endtime.tv_usec + (long int) (max_msecs % 1000) * 1000;
1148 if(usecs >= 1000000) {
1149 usecs -= 1000000;
1150 endtime.tv_sec++;
1151 }
1152 endtime.tv_usec = usecs;
1153 max_msecs = 0;
1154 endtime_p = &endtime;
1155 }
1156
1157 EvaluationOptions eo = eo_pre;
1158 eo.sync_units = false;
1159 eo.structuring = STRUCTURING_NONE;
1160 if(unfactorize) {
1161 unformat(eo_pre);
1162 EvaluationOptions eo2 = eo;
1163 eo2.expand = true;
1164 eo2.combine_divisions = false;
1165 eo2.sync_units = false;
1166 calculatesub(eo2, eo2);
1167 do_simplification(*this, eo, true, false, true);
1168 } else if(term_combination_levels && isAddition()) {
1169 MathStructure *mdiv = new MathStructure;
1170 mdiv->setType(STRUCT_ADDITION);
1171 for(size_t i = 0; i < SIZE; ) {
1172 bool b = false;
1173 if(CHILD(i).isMultiplication()) {
1174 for(size_t i2 = 0; i2 < CHILD(i).size(); i2++) {
1175 if(CHILD(i)[i2].isPower() && CHILD(i)[i2][1].hasNegativeSign()) {
1176 b = true;
1177 break;
1178 }
1179 }
1180 } else if(CHILD(i).isPower() && CHILD(i)[1].hasNegativeSign()) {
1181 b = true;
1182 }
1183 if(b) {
1184 CHILD(i).ref();
1185 mdiv->addChild_nocopy(&CHILD(i));
1186 ERASE(i)
1187 } else {
1188 i++;
1189 }
1190 }
1191 if(mdiv->size() > 0) {
1192 bool b_ret = false;
1193 if(SIZE == 1 && recursive) {
1194 b_ret = CHILD(0).factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
1195 } else if(SIZE > 1) {
1196 b_ret = factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
1197 }
1198 if(mdiv->size() > 1) {
1199 // 5/y + x/y + z = (5 + x)/y + z
1200 MathStructure mstruct_units(*mdiv);
1201 MathStructure mstruct_new(*mdiv);
1202 for(size_t i = 0; i < mstruct_units.size(); i++) {
1203 if(mstruct_units[i].isMultiplication()) {
1204 for(size_t i2 = 0; i2 < mstruct_units[i].size();) {
1205 if(!mstruct_units[i][i2].isPower() || !mstruct_units[i][i2][1].hasNegativeSign()) {
1206 mstruct_units[i].delChild(i2 + 1);
1207 } else {
1208 i2++;
1209 }
1210 }
1211 if(mstruct_units[i].size() == 0) mstruct_units[i].setUndefined();
1212 else if(mstruct_units[i].size() == 1) mstruct_units[i].setToChild(1);
1213 for(size_t i2 = 0; i2 < mstruct_new[i].size();) {
1214 if(mstruct_new[i][i2].isPower() && mstruct_new[i][i2][1].hasNegativeSign()) {
1215 mstruct_new[i].delChild(i2 + 1);
1216 } else {
1217 i2++;
1218 }
1219 }
1220 if(mstruct_new[i].size() == 0) mstruct_new[i].set(1, 1, 0);
1221 else if(mstruct_new[i].size() == 1) mstruct_new[i].setToChild(1);
1222 } else if(mstruct_new[i].isPower() && mstruct_new[i][1].hasNegativeSign()) {
1223 mstruct_new[i].set(1, 1, 0);
1224 } else {
1225 mstruct_units[i].setUndefined();
1226 }
1227 }
1228 bool b = false;
1229 for(size_t i = 0; i < mstruct_units.size(); i++) {
1230 if(!mstruct_units[i].isUndefined()) {
1231 for(size_t i2 = i + 1; i2 < mstruct_units.size();) {
1232 if(mstruct_units[i2] == mstruct_units[i]) {
1233 mstruct_new[i].add(mstruct_new[i2], true);
1234 mstruct_new.delChild(i2 + 1);
1235 mstruct_units.delChild(i2 + 1);
1236 b = true;
1237 } else {
1238 i2++;
1239 }
1240 }
1241 if(mstruct_new[i].isOne()) mstruct_new[i].set(mstruct_units[i]);
1242 else mstruct_new[i].multiply(mstruct_units[i], true);
1243 }
1244 }
1245 if(b) {
1246 if(mstruct_new.size() == 1) {
1247 mdiv->set_nocopy(mstruct_new[0], true);
1248 } else {
1249 mdiv->set_nocopy(mstruct_new);
1250 }
1251 b_ret = true;
1252 }
1253 }
1254 size_t index = 1;
1255 if(isAddition()) index = SIZE;
1256 if(index == 0) {
1257 set_nocopy(*mdiv);
1258 } else if(mdiv->isAddition()) {
1259 for(size_t i = 0; i < mdiv->size(); i++) {
1260 (*mdiv)[i].ref();
1261 add_nocopy(&(*mdiv)[i], true);
1262 }
1263 mdiv->unref();
1264 } else {
1265 add_nocopy(mdiv, true);
1266 }
1267 if(recursive) {
1268 for(; index < SIZE; index++) {
1269 b_ret = CHILD(index).factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree) || b_ret;
1270 }
1271 }
1272 return b_ret;
1273 }
1274 mdiv->unref();
1275 }
1276
1277 MathStructure mden, mnum;
1278 evalSort(true);
1279
1280 if(term_combination_levels >= -1 && isAddition() && isRationalPolynomial()) {
1281 MathStructure msqrfree(*this);
1282 eo.protected_function = CALCULATOR->getFunctionById(FUNCTION_ID_SIGNUM);
1283 if(sqrfree(msqrfree, eo)) {
1284 if((!only_sqrfree || msqrfree.isPower()) && !equals(msqrfree) && (!msqrfree.isMultiplication() || msqrfree.size() != 2 || (!(msqrfree[0].isNumber() && msqrfree[1].isAddition()) && !(msqrfree[1].isNumber() && msqrfree[0].isAddition())))) {
1285 MathStructure mcopy(msqrfree);
1286 EvaluationOptions eo2 = eo;
1287 eo2.expand = true;
1288 eo2.calculate_functions = false;
1289 CALCULATOR->beginTemporaryStopMessages();
1290 mcopy.calculatesub(eo2, eo2);
1291 CALCULATOR->endTemporaryStopMessages();
1292 bool b_equal = equals(mcopy);
1293 if(!b_equal && !CALCULATOR->aborted()) {
1294 MathStructure mcopy2(*this);
1295 CALCULATOR->beginTemporaryStopMessages();
1296 mcopy.calculatesub(eo2, eo2, true);
1297 mcopy2.calculatesub(eo2, eo2, true);
1298 CALCULATOR->endTemporaryStopMessages();
1299 b_equal = mcopy.equals(mcopy2);
1300 }
1301 if(!b_equal) {
1302 eo.protected_function = eo_pre.protected_function;
1303 if(CALCULATOR->aborted()) return false;
1304 CALCULATOR->error(true, "factorized result is wrong: %s != %s. %s", format_and_print(msqrfree).c_str(), format_and_print(*this).c_str(), _("This is a bug. Please report it."), NULL);
1305 } else {
1306 eo.protected_function = eo_pre.protected_function;
1307 set(msqrfree);
1308 if(!isAddition()) {
1309 if(isMultiplication()) flattenMultiplication(*this);
1310 if(isMultiplication() && SIZE >= 2 && CHILD(0).isNumber()) {
1311 for(size_t i = 1; i < SIZE; i++) {
1312 if(CHILD(i).isNumber()) {
1313 CHILD(i).number() *= CHILD(0).number();
1314 CHILD(0).set(CHILD(i));
1315 delChild(i);
1316 } else if(CHILD(i).isPower() && CHILD(i)[0].isMultiplication() && CHILD(i)[0].size() >= 2 && CHILD(i)[0][0].isNumber() && CHILD(i)[0][0].number().isRational() && !CHILD(i)[0][0].number().isInteger() && CHILD(i)[1].isInteger()) {
1317 CHILD(i)[0][0].number().raise(CHILD(i)[1].number());
1318 CHILD(0).number().multiply(CHILD(i)[0][0].number());
1319 CHILD(i)[0].delChild(1);
1320 if(CHILD(i)[0].size() == 1) CHILD(i)[0].setToChild(1, true);
1321 }
1322 }
1323 if(SIZE > 1 && CHILD(0).isOne()) {
1324 ERASE(0);
1325 }
1326 if(SIZE == 1) SET_CHILD_MAP(0);
1327 }
1328 if(isMultiplication() && SIZE >= 2 && CHILD(0).isNumber() && CHILD(0).number().isRational() && !CHILD(0).number().isInteger()) {
1329 Number den = CHILD(0).number().denominator();
1330 for(size_t i = 1; i < SIZE; i++) {
1331 if(CHILD(i).isAddition()) {
1332 bool b = true;
1333 for(size_t i2 = 0; i2 < CHILD(i).size(); i2++) {
1334 if(CHILD(i)[i2].isNumber()) {
1335 if(!CHILD(i)[i2].number().isIntegerDivisible(den)) {b = false; break;}
1336 } else if(CHILD(i)[i2].isMultiplication() && CHILD(i)[i2][0].isNumber()) {
1337 if(!CHILD(i)[i2][0].number().isIntegerDivisible(den)) {b = false; break;}
1338 } else {
1339 b = false;
1340 break;
1341 }
1342 }
1343 if(b) {
1344 for(size_t i2 = 0; i2 < CHILD(i).size(); i2++) {
1345 if(CHILD(i)[i2].isNumber()) {
1346 CHILD(i)[i2].number().divide(den);
1347 } else if(CHILD(i)[i2].isMultiplication()) {
1348 CHILD(i)[i2][0].number().divide(den);
1349 if(CHILD(i)[i2][0].isOne() && CHILD(i)[i2].size() > 1) {
1350 CHILD(i)[i2].delChild(1);
1351 if(CHILD(i)[i2].size() == 1) {
1352 CHILD(i)[i2].setToChild(1, true);
1353 }
1354 }
1355 }
1356 }
1357 CHILD(0).set(CHILD(0).number().numerator(), true);
1358 if(SIZE > 1 && CHILD(0).isOne()) {
1359 ERASE(0);
1360 }
1361 if(SIZE == 1) SET_CHILD_MAP(0);
1362 break;
1363 }
1364 }
1365 }
1366 }
1367 if(isMultiplication()) {
1368 for(size_t i = 0; i < SIZE; i++) {
1369 if(CHILD(i).isPower() && CHILD(i)[1].isInteger()) {
1370 if(CHILD(i)[0].isAddition()) {
1371 bool b = true;
1372 for(size_t i2 = 0; i2 < CHILD(i)[0].size(); i2++) {
1373 if((!CHILD(i)[0][i2].isNumber() || !CHILD(i)[0][i2].number().isNegative()) && (!CHILD(i)[0][i2].isMultiplication() || CHILD(i)[0][i2].size() < 2 || !CHILD(i)[0][i2][0].isNumber() || !CHILD(i)[0][i2][0].number().isNegative())) {
1374 b = false;
1375 break;
1376 }
1377 }
1378 if(b) {
1379 for(size_t i2 = 0; i2 < CHILD(i)[0].size(); i2++) {
1380 if(CHILD(i)[0][i2].isNumber()) {
1381 CHILD(i)[0][i2].number().negate();
1382 } else {
1383 CHILD(i)[0][i2][0].number().negate();
1384 if(CHILD(i)[0][i2][0].isOne() && CHILD(i)[0][i2].size() > 1) {
1385 CHILD(i)[0][i2].delChild(1);
1386 if(CHILD(i)[0][i2].size() == 1) {
1387 CHILD(i)[0][i2].setToChild(1, true);
1388 }
1389 }
1390 }
1391 }
1392 if(CHILD(i)[1].number().isOdd()) {
1393 if(CHILD(0).isNumber()) CHILD(0).number().negate();
1394 else {
1395 PREPEND(MathStructure(-1, 1, 0));
1396 i++;
1397 }
1398 }
1399 }
1400 } else if(CHILD(i)[0].isMultiplication() && CHILD(i)[0].size() >= 2 && CHILD(i)[0][0].isNumber() && CHILD(i)[0][0].number().isNegative()) {
1401 CHILD(i)[0][0].number().negate();
1402 if(CHILD(i)[0][0].isOne() && CHILD(i)[0].size() > 1) {
1403 CHILD(i)[0].delChild(1);
1404 if(CHILD(i)[0].size() == 1) {
1405 CHILD(i)[0].setToChild(1, true);
1406 }
1407 }
1408 if(CHILD(i)[1].number().isOdd()) {
1409 if(CHILD(0).isNumber()) CHILD(0).number().negate();
1410 else {
1411 PREPEND(MathStructure(-1, 1, 0));
1412 i++;
1413 }
1414 }
1415 }
1416 } else if(CHILD(i).isAddition()) {
1417 bool b = true;
1418 for(size_t i2 = 0; i2 < CHILD(i).size(); i2++) {
1419 if((!CHILD(i)[i2].isNumber() || !CHILD(i)[i2].number().isNegative()) && (!CHILD(i)[i2].isMultiplication() || CHILD(i)[i2].size() < 2 || !CHILD(i)[i2][0].isNumber() || !CHILD(i)[i2][0].number().isNegative())) {
1420 b = false;
1421 break;
1422 }
1423 }
1424 if(b) {
1425 for(size_t i2 = 0; i2 < CHILD(i).size(); i2++) {
1426 if(CHILD(i)[i2].isNumber()) {
1427 CHILD(i)[i2].number().negate();
1428 } else {
1429 CHILD(i)[i2][0].number().negate();
1430 if(CHILD(i)[i2][0].isOne() && CHILD(i)[i2].size() > 1) {
1431 CHILD(i)[i2].delChild(1);
1432 if(CHILD(i)[i2].size() == 1) {
1433 CHILD(i)[i2].setToChild(1, true);
1434 }
1435 }
1436 }
1437 }
1438 if(CHILD(0).isNumber()) CHILD(0).number().negate();
1439 else {
1440 PREPEND(MathStructure(-1, 1, 0));
1441 i++;
1442 }
1443 }
1444 }
1445 }
1446 if(SIZE > 1 && CHILD(0).isOne()) {
1447 ERASE(0);
1448 }
1449 if(SIZE == 1) SET_CHILD_MAP(0);
1450 }
1451 if(isPower() && CHILD(1).isInteger()) {
1452 if(CHILD(0).isAddition()) {
1453 bool b = true;
1454 for(size_t i2 = 0; i2 < CHILD(0).size(); i2++) {
1455 if((!CHILD(0)[i2].isNumber() || !CHILD(0)[i2].number().isNegative()) && (!CHILD(0)[i2].isMultiplication() || CHILD(0)[i2].size() < 2 || !CHILD(0)[i2][0].isNumber() || !CHILD(0)[i2][0].number().isNegative())) {
1456 b = false;
1457 break;
1458 }
1459 }
1460 if(b) {
1461 for(size_t i2 = 0; i2 < CHILD(0).size(); i2++) {
1462 if(CHILD(0)[i2].isNumber()) {
1463 CHILD(0)[i2].number().negate();
1464 } else {
1465 CHILD(0)[i2][0].number().negate();
1466 if(CHILD(0)[i2][0].isOne() && CHILD(0)[i2].size() > 1) {
1467 CHILD(0)[i2].delChild(1);
1468 if(CHILD(0)[i2].size() == 1) {
1469 CHILD(0)[i2].setToChild(1, true);
1470 }
1471 }
1472 }
1473 }
1474 if(CHILD(1).number().isOdd()) {
1475 multiply(MathStructure(-1, 1, 0));
1476 CHILD_TO_FRONT(1)
1477 }
1478 }
1479 } else if(CHILD(0).isMultiplication() && CHILD(0).size() >= 2 && CHILD(0)[0].isNumber() && CHILD(0)[0].number().isNegative()) {
1480 CHILD(0)[0].number().negate();
1481 if(CHILD(0)[0].isOne() && CHILD(0).size() > 1) {
1482 CHILD(0).delChild(1);
1483 if(CHILD(0).size() == 1) {
1484 CHILD(0).setToChild(1, true);
1485 }
1486 }
1487 if(CHILD(1).number().isOdd()) {
1488 multiply(MathStructure(-1, 1, 0));
1489 CHILD_TO_FRONT(1)
1490 }
1491 }
1492 }
1493 }
1494 evalSort(true);
1495 factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
1496 return true;
1497 }
1498 }
1499 }
1500 eo.protected_function = eo_pre.protected_function;
1501 }
1502
1503 switch(type()) {
1504 case STRUCT_ADDITION: {
1505
1506 if(CALCULATOR->aborted()) return false;
1507 if(term_combination_levels >= -1 && !only_sqrfree && max_factor_degree != 0) {
1508
1509 if(SIZE <= 3 && SIZE > 1) {
1510 MathStructure *xvar = NULL;
1511 Number nr2(1, 1);
1512 if(CHILD(0).isPower() && CHILD(0)[0].size() == 0 && CHILD(0)[1].isNumber() && CHILD(0)[1].number().isTwo()) {
1513 xvar = &CHILD(0)[0];
1514 } else if(CHILD(0).isMultiplication() && CHILD(0).size() == 2 && CHILD(0)[0].isNumber()) {
1515 if(CHILD(0)[1].isPower()) {
1516 if(CHILD(0)[1][0].size() == 0 && CHILD(0)[1][1].isNumber() && CHILD(0)[1][1].number().isTwo()) {
1517 xvar = &CHILD(0)[1][0];
1518 nr2.set(CHILD(0)[0].number());
1519 }
1520 }
1521 }
1522 if(xvar) {
1523 bool factorable = false;
1524 Number nr1, nr0;
1525 if(SIZE == 2 && CHILD(1).isNumber()) {
1526 factorable = true;
1527 nr0 = CHILD(1).number();
1528 } else if(SIZE == 3 && CHILD(2).isNumber()) {
1529 nr0 = CHILD(2).number();
1530 if(CHILD(1).isMultiplication()) {
1531 if(CHILD(1).size() == 2 && CHILD(1)[0].isNumber() && xvar->equals(CHILD(1)[1])) {
1532 nr1 = CHILD(1)[0].number();
1533 factorable = true;
1534 }
1535 } else if(xvar->equals(CHILD(1))) {
1536 nr1.set(1, 1, 0);
1537 factorable = true;
1538 }
1539 }
1540 if(factorable) {
1541 Number nr4ac(4, 1, 0);
1542 nr4ac *= nr2;
1543 nr4ac *= nr0;
1544 Number nr2a(2, 1, 0);
1545 nr2a *= nr2;
1546 Number sqrtb24ac(nr1);
1547 sqrtb24ac.raise(nr_two);
1548 sqrtb24ac -= nr4ac;
1549 if(sqrtb24ac.isNegative()) factorable = false;
1550 MathStructure mstructb24(sqrtb24ac);
1551 if(factorable) {
1552 if(!only_integers) {
1553 if(eo.approximation == APPROXIMATION_EXACT && !sqrtb24ac.isApproximate()) {
1554 sqrtb24ac.raise(nr_half);
1555 if(sqrtb24ac.isApproximate()) {
1556 mstructb24.raise(nr_half);
1557 } else {
1558 mstructb24.set(sqrtb24ac);
1559 }
1560 } else {
1561 mstructb24.number().raise(nr_half);
1562 }
1563 } else {
1564 mstructb24.number().raise(nr_half);
1565 if((!sqrtb24ac.isApproximate() && mstructb24.number().isApproximate()) || (sqrtb24ac.isInteger() && !mstructb24.number().isInteger())) {
1566 factorable = false;
1567 }
1568 }
1569 }
1570 if(factorable) {
1571 MathStructure m1(nr1), m2(nr1);
1572 Number mul1(1, 1), mul2(1, 1);
1573 if(mstructb24.isNumber()) {
1574 m1.number() += mstructb24.number();
1575 m1.number() /= nr2a;
1576 if(m1.number().isRational() && !m1.number().isInteger()) {
1577 mul1 = m1.number().denominator();
1578 m1.number() *= mul1;
1579 }
1580 m2.number() -= mstructb24.number();
1581 m2.number() /= nr2a;
1582 if(m2.number().isRational() && !m2.number().isInteger()) {
1583 mul2 = m2.number().denominator();
1584 m2.number() *= mul2;
1585 }
1586 } else {
1587 m1.calculateAdd(mstructb24, eo);
1588 m1.calculateDivide(nr2a, eo);
1589 if(m1.isNumber()) {
1590 if(m1.number().isRational() && !m1.number().isInteger()) {
1591 mul1 = m1.number().denominator();
1592 m1.number() *= mul1;
1593 }
1594 } else {
1595 bool bint = false, bfrac = false;
1596 idm1(m1, bfrac, bint);
1597 if(bfrac) {
1598 idm2(m1, bfrac, bint, mul1);
1599 idm3(m1, mul1, true);
1600 }
1601 }
1602 m2.calculateSubtract(mstructb24, eo);
1603 m2.calculateDivide(nr2a, eo);
1604 if(m2.isNumber()) {
1605 if(m2.number().isRational() && !m2.number().isInteger()) {
1606 mul2 = m2.number().denominator();
1607 m2.number() *= mul2;
1608 }
1609 } else {
1610 bool bint = false, bfrac = false;
1611 idm1(m2, bfrac, bint);
1612 if(bfrac) {
1613 idm2(m2, bfrac, bint, mul2);
1614 idm3(m2, mul2, true);
1615 }
1616 }
1617 }
1618 nr2 /= mul1;
1619 nr2 /= mul2;
1620 if(m1 == m2 && mul1 == mul2) {
1621 MathStructure xvar2(*xvar);
1622 if(!mul1.isOne()) xvar2 *= mul1;
1623 set(m1);
1624 add(xvar2, true);
1625 raise(MathStructure(2, 1, 0));
1626 if(!nr2.isOne()) {
1627 multiply(nr2);
1628 }
1629 } else {
1630 m1.add(*xvar, true);
1631 if(!mul1.isOne()) m1[m1.size() - 1] *= mul1;
1632 m2.add(*xvar, true);
1633 if(!mul2.isOne()) m2[m2.size() - 1] *= mul2;
1634 clear(true);
1635 m_type = STRUCT_MULTIPLICATION;
1636 if(!nr2.isOne()) {
1637 APPEND_NEW(nr2);
1638 }
1639 APPEND(m1);
1640 APPEND(m2);
1641 }
1642 EvaluationOptions eo2 = eo;
1643 eo2.expand = false;
1644 calculatesub(eo2, eo2, false);
1645 evalSort(true);
1646 return true;
1647 }
1648 }
1649 }
1650 }
1651
1652 MathStructure *factor_mstruct = new MathStructure(1, 1, 0);
1653 MathStructure mnew;
1654 if(factorize_find_multiplier(*this, mnew, *factor_mstruct) && !factor_mstruct->isZero() && !mnew.isZero()) {
1655 mnew.factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
1656 factor_mstruct->factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
1657 clear(true);
1658 m_type = STRUCT_MULTIPLICATION;
1659 APPEND_REF(factor_mstruct);
1660 APPEND(mnew);
1661 EvaluationOptions eo2 = eo;
1662 eo2.expand = false;
1663 calculatesub(eo2, eo2, false);
1664 factor_mstruct->unref();
1665 evalSort(true);
1666 return true;
1667 }
1668 factor_mstruct->unref();
1669
1670 if(SIZE > 1 && CHILD(SIZE - 1).isNumber() && CHILD(SIZE - 1).number().isInteger() && max_factor_degree != 0) {
1671 MathStructure *xvar = NULL;
1672 Number qnr(1, 1);
1673 int degree = 1;
1674 bool overflow = false;
1675 int qcof = 1;
1676 if(CHILD(0).isPower() && !CHILD(0)[0].isNumber() && CHILD(0)[0].size() == 0 && CHILD(0)[1].isNumber() && CHILD(0)[1].number().isInteger() && CHILD(0)[1].number().isPositive()) {
1677 xvar = &CHILD(0)[0];
1678 degree = CHILD(0)[1].number().intValue(&overflow);
1679 } else if(CHILD(0).isMultiplication() && CHILD(0).size() == 2 && CHILD(0)[0].isNumber() && CHILD(0)[0].number().isInteger()) {
1680 if(CHILD(0)[1].isPower()) {
1681 if(CHILD(0)[1][0].size() == 0 && !CHILD(0)[1][0].isNumber() && CHILD(0)[1][1].isNumber() && CHILD(0)[1][1].number().isInteger() && CHILD(0)[1][1].number().isPositive()) {
1682 xvar = &CHILD(0)[1][0];
1683 qcof = CHILD(0)[0].number().intValue(&overflow);
1684 if(!overflow) {
1685 if(qcof < 0) qcof = -qcof;
1686 degree = CHILD(0)[1][1].number().intValue(&overflow);
1687 }
1688 }
1689 }
1690 }
1691
1692 int pcof = 1;
1693 if(!overflow) {
1694 pcof = CHILD(SIZE - 1).number().intValue(&overflow);
1695 if(pcof < 0) pcof = -pcof;
1696 }
1697
1698 if(xvar && !overflow && degree <= 1000 && degree > 2 && qcof != 0 && pcof != 0) {
1699 bool b = true, b2 = true;
1700 for(size_t i = 1; b && i < SIZE - 1; i++) {
1701 switch(CHILD(i).type()) {
1702 case STRUCT_NUMBER: {
1703 b = false;
1704 break;
1705 }
1706 case STRUCT_POWER: {
1707 if(!CHILD(i)[1].isNumber() || !xvar->equals(CHILD(i)[0]) || !CHILD(i)[1].number().isInteger() || !CHILD(i)[1].number().isPositive()) {
1708 b = false;
1709 }
1710 break;
1711 }
1712 case STRUCT_MULTIPLICATION: {
1713 if(!(CHILD(i).size() == 2) || !CHILD(i)[0].isNumber()) {
1714 b = false;
1715 } else if(CHILD(i)[1].isPower()) {
1716 if(!CHILD(i)[1][1].isNumber() || !xvar->equals(CHILD(i)[1][0]) || !CHILD(i)[1][1].number().isInteger() || !CHILD(i)[1][1].number().isPositive()) {
1717 b = false;
1718 }
1719 } else if(!xvar->equals(CHILD(i)[1])) {
1720 b = false;
1721 }
1722 if(b && b2 && !CHILD(i)[0].isInteger()) b2 = false;
1723 break;
1724 }
1725 default: {
1726 if(!xvar->equals(CHILD(i))) {
1727 b = false;
1728 }
1729 }
1730 }
1731 }
1732
1733 if(b) {
1734 vector<Number> factors;
1735 factors.resize(degree + 1, Number());
1736 factors[0] = CHILD(SIZE - 1).number();
1737 vector<int> ps;
1738 vector<int> qs;
1739 vector<Number> zeroes;
1740 int curdeg = 1, prevdeg = 0;
1741 for(size_t i = 0; b && i < SIZE - 1; i++) {
1742 switch(CHILD(i).type()) {
1743 case STRUCT_POWER: {
1744 curdeg = CHILD(i)[1].number().intValue(&overflow);
1745 if(curdeg == prevdeg || curdeg > degree || (prevdeg > 0 && curdeg > prevdeg) || overflow) {
1746 b = false;
1747 } else {
1748 factors[curdeg].set(1, 1, 0);
1749 }
1750 break;
1751 }
1752 case STRUCT_MULTIPLICATION: {
1753 if(CHILD(i)[1].isPower()) {
1754 curdeg = CHILD(i)[1][1].number().intValue(&overflow);
1755 } else {
1756 curdeg = 1;
1757 }
1758 if(curdeg == prevdeg || curdeg > degree || (prevdeg > 0 && curdeg > prevdeg) || overflow) {
1759 b = false;
1760 } else {
1761 factors[curdeg] = CHILD(i)[0].number();
1762 }
1763 break;
1764 }
1765 default: {
1766 curdeg = 1;
1767 factors[curdeg].set(1, 1, 0);
1768 }
1769 }
1770 prevdeg = curdeg;
1771 }
1772
1773 while(b && degree > 2) {
1774 for(int i = 1; i <= 1000; i++) {
1775 if(i > pcof) break;
1776 if(pcof % i == 0) ps.push_back(i);
1777 }
1778 for(int i = 1; i <= 1000; i++) {
1779 if(i > qcof) break;
1780 if(qcof % i == 0) qs.push_back(i);
1781 }
1782 Number itest;
1783 int i2;
1784 size_t pi = 0, qi = 0;
1785 if(ps.empty() || qs.empty()) break;
1786 Number nrtest(ps[0], qs[0], 0);
1787 while(true) {
1788 itest.clear(); i2 = degree;
1789 while(true) {
1790 itest += factors[i2];
1791 if(i2 == 0) break;
1792 itest *= nrtest;
1793 i2--;
1794 }
1795 if(itest.isZero()) {
1796 break;
1797 }
1798 if(nrtest.isPositive()) {
1799 nrtest.negate();
1800 } else {
1801 qi++;
1802 if(qi == qs.size()) {
1803 qi = 0;
1804 pi++;
1805 if(pi == ps.size()) {
1806 break;
1807 }
1808 }
1809 nrtest.set(ps[pi], qs[qi], 0);
1810 }
1811 }
1812 if(itest.isZero()) {
1813 itest.clear(); i2 = degree;
1814 Number ntmp(factors[i2]);
1815 for(; i2 > 0; i2--) {
1816 itest += ntmp;
1817 ntmp = factors[i2 - 1];
1818 factors[i2 - 1] = itest;
1819 itest *= nrtest;
1820 }
1821 degree--;
1822 nrtest.negate();
1823 zeroes.push_back(nrtest);
1824 if(degree == 2) {
1825 break;
1826 }
1827 qcof = factors[degree].intValue(&overflow);
1828 if(!overflow) {
1829 if(qcof < 0) qcof = -qcof;
1830 pcof = factors[0].intValue(&overflow);
1831 if(!overflow) {
1832 if(pcof < 0) pcof = -pcof;
1833 }
1834 }
1835 if(overflow || qcof == 0 || pcof == 0) {
1836 break;
1837 }
1838 } else {
1839 break;
1840 }
1841 ps.clear();
1842 qs.clear();
1843 }
1844
1845 if(zeroes.size() > 0) {
1846 MathStructure mleft;
1847 MathStructure mtmp;
1848 MathStructure *mcur;
1849 for(int i = degree; i >= 0; i--) {
1850 if(!factors[i].isZero()) {
1851 if(mleft.isZero()) {
1852 mcur = &mleft;
1853 } else {
1854 mleft.add(m_zero, true);
1855 mcur = &mleft[mleft.size() - 1];
1856 }
1857 if(i > 1) {
1858 if(!factors[i].isOne()) {
1859 mcur->multiply(*xvar);
1860 (*mcur)[0].set(factors[i]);
1861 mcur = &(*mcur)[1];
1862 } else {
1863 mcur->set(*xvar);
1864 }
1865 mtmp.set(i, 1, 0);
1866 mcur->raise(mtmp);
1867 } else if(i == 1) {
1868 if(!factors[i].isOne()) {
1869 mcur->multiply(*xvar);
1870 (*mcur)[0].set(factors[i]);
1871 } else {
1872 mcur->set(*xvar);
1873 }
1874 } else {
1875 mcur->set(factors[i]);
1876 }
1877 }
1878 }
1879 mleft.factorize(eo, false, 0, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
1880 vector<long int> powers;
1881 vector<size_t> powers_i;
1882 int dupsfound = 0;
1883 for(size_t i = 0; i < zeroes.size() - 1; i++) {
1884 while(i + 1 < zeroes.size() && zeroes[i] == zeroes[i + 1]) {
1885 dupsfound++;
1886 zeroes.erase(zeroes.begin() + (i + 1));
1887 }
1888 if(dupsfound > 0) {
1889 powers_i.push_back(i);
1890 powers.push_back(dupsfound + 1);
1891 dupsfound = 0;
1892 }
1893 }
1894 MathStructure xvar2(*xvar);
1895 Number *nrmul;
1896 if(mleft.isMultiplication()) {
1897 set(mleft);
1898 evalSort();
1899 if(CHILD(0).isNumber()) {
1900 nrmul = &CHILD(0).number();
1901 } else if(CHILD(0).isMultiplication() && CHILD(0).size() > 0 && CHILD(0)[0].isNumber()) {
1902 nrmul = &CHILD(0)[0].number();
1903 } else {
1904 PREPEND(m_one);
1905 nrmul = &CHILD(0).number();
1906 }
1907 } else {
1908 clear(true);
1909 m_type = STRUCT_MULTIPLICATION;
1910 APPEND(m_one);
1911 APPEND(mleft);
1912 nrmul = &CHILD(0).number();
1913 }
1914 size_t pi = 0;
1915 for(size_t i = 0; i < zeroes.size(); i++) {
1916 if(zeroes[i].isInteger()) {
1917 APPEND(xvar2);
1918 } else {
1919 APPEND(m_zero);
1920 }
1921 mcur = &CHILD(SIZE - 1);
1922 if(pi < powers_i.size() && powers_i[pi] == i) {
1923 mcur->raise(MathStructure(powers[pi], 1L, 0L));
1924 mcur = &(*mcur)[0];
1925 if(zeroes[i].isInteger()) {
1926 mcur->add(zeroes[i]);
1927 } else {
1928 Number nr(zeroes[i].denominator());
1929 mcur->add(zeroes[i].numerator());
1930 (*mcur)[0] *= xvar2;
1931 (*mcur)[0][0].number() = nr;
1932 nr.raise(powers[pi]);
1933 nrmul->divide(nr);
1934 }
1935 pi++;
1936 } else {
1937 if(zeroes[i].isInteger()) {
1938 mcur->add(zeroes[i]);
1939 } else {
1940 nrmul->divide(zeroes[i].denominator());
1941 mcur->add(zeroes[i].numerator());
1942 (*mcur)[0] *= xvar2;
1943 (*mcur)[0][0].number() = zeroes[i].denominator();
1944 }
1945 }
1946 }
1947 if(CHILD(0).isNumber() && CHILD(0).number().isOne()) {
1948 ERASE(0);
1949 } else if(CHILD(0).isMultiplication() && CHILD(0).size() > 0 && CHILD(0)[0].isNumber() && CHILD(0)[0].number().isOne()) {
1950 if(CHILD(0).size() == 1) {
1951 ERASE(0);
1952 } else if(CHILD(0).size() == 2) {
1953 CHILD(0).setToChild(2, true);
1954 } else {
1955 CHILD(0).delChild(1);
1956 }
1957 }
1958 evalSort(true);
1959 Number dupspow;
1960 for(size_t i = 0; i < SIZE - 1; i++) {
1961 mcur = NULL;
1962 if(CHILD(i).isPower()) {
1963 if(CHILD(i)[0].isAddition() && CHILD(i)[1].isNumber()) {
1964 mcur = &CHILD(i)[0];
1965 }
1966 } else if(CHILD(i).isAddition()) {
1967 mcur = &CHILD(i);
1968 }
1969 while(mcur && i + 1 < SIZE) {
1970 if(CHILD(i + 1).isPower()) {
1971 if(CHILD(i + 1)[0].isAddition() && CHILD(i + 1)[1].isNumber() && mcur->equals(CHILD(i + 1)[0])) {
1972 dupspow += CHILD(i + 1)[1].number();
1973 } else {
1974 mcur = NULL;
1975 }
1976 } else if(CHILD(i + 1).isAddition() && mcur->equals(CHILD(i + 1))) {
1977 dupspow++;
1978 } else {
1979 mcur = NULL;
1980 }
1981 if(mcur) {
1982 ERASE(i + 1);
1983 }
1984 }
1985 if(!dupspow.isZero()) {
1986 if(CHILD(i).isPower()) {
1987 CHILD(i)[1].number() += dupspow;
1988 } else {
1989 dupspow++;
1990 CHILD(i) ^= dupspow;
1991 }
1992 dupspow.clear();
1993 }
1994 }
1995 if(SIZE == 1) {
1996 setToChild(1, true);
1997 } else {
1998 EvaluationOptions eo2 = eo;
1999 eo2.expand = false;
2000 calculatesub(eo2, eo2, false);
2001 }
2002 evalSort(true);
2003 return true;
2004 }
2005 }
2006
2007 if(b && b2 && (max_factor_degree < 0 || max_factor_degree >= 2) && degree > 3 && degree < 50) {
2008 // Kronecker method
2009 vector<Number> vnum;
2010 vnum.resize(degree + 1, nr_zero);
2011 bool overflow = false;
2012 for(size_t i = 0; b && i < SIZE; i++) {
2013 switch(CHILD(i).type()) {
2014 case STRUCT_POWER: {
2015 if(CHILD(i)[0] == *xvar && CHILD(i)[1].isInteger()) {
2016 int curdeg = CHILD(i)[1].number().intValue(&overflow);
2017 if(curdeg < 0 || overflow || curdeg > degree) b = false;
2018 else vnum[curdeg] += 1;
2019 } else {
2020 b = false;
2021 }
2022 break;
2023 }
2024 case STRUCT_MULTIPLICATION: {
2025 if(CHILD(i).size() == 2 && CHILD(i)[0].isInteger()) {
2026 long int icoeff = CHILD(i)[0].number().intValue(&overflow);
2027 if(!overflow && CHILD(i)[1].isPower() && CHILD(i)[1][0] == *xvar && CHILD(i)[1][1].isInteger()) {
2028 int curdeg = CHILD(i)[1][1].number().intValue(&overflow);
2029 if(curdeg < 0 || overflow || curdeg > degree) b = false;
2030 else vnum[curdeg] += icoeff;
2031 } else if(!overflow && CHILD(i)[1] == *xvar) {
2032 vnum[1] += icoeff;
2033 } else {
2034 b = false;
2035 }
2036 } else {
2037 b = false;
2038 }
2039 break;
2040 }
2041 default: {
2042 if(CHILD(i).isInteger()) {
2043 long int icoeff = CHILD(i).number().intValue(&overflow);
2044 if(overflow) b = false;
2045 else vnum[0] += icoeff;
2046 } else if(CHILD(i) == *xvar) {
2047 vnum[1] += 1;
2048 } else {
2049 b = false;
2050 }
2051 break;
2052 }
2053 }
2054 }
2055
2056 long int lcoeff = vnum[degree].lintValue();
2057 vector<int> vs;
2058 if(b && lcoeff != 0) {
2059 degree /= 2;
2060 if(max_factor_degree > 0 && degree > max_factor_degree) degree = max_factor_degree;
2061 for(int i = 0; i <= degree; i++) {
2062 if(CALCULATOR->aborted()) return false;
2063 MathStructure mcalc(*this);
2064 mcalc.calculateReplace(*xvar, Number((i / 2 + i % 2) * (i % 2 == 0 ? -1 : 1), 1), eo);
2065 mcalc.calculatesub(eo, eo, false);
2066 if(!mcalc.isInteger()) break;
2067 bool overflow = false;
2068 int v = ::abs(mcalc.number().intValue(&overflow));
2069 if(overflow) {
2070 if(i > 2) degree = i;
2071 else b = false;
2072 break;
2073 }
2074 vs.push_back(v);
2075 }
2076 }
2077
2078 if(b) {
2079 vector<int> factors0, factorsl;
2080 factors0.push_back(1);
2081 for(int i = 2; i < vs[0] / 3 && i < 1000; i++) {
2082 if(vs[0] % i == 0) factors0.push_back(i);
2083 }
2084 if(vs[0] % 3 == 0) factors0.push_back(vs[0] / 3);
2085 if(vs[0] % 2 == 0) factors0.push_back(vs[0] / 2);
2086 factors0.push_back(vs[0]);
2087 for(int i = 2; i < lcoeff / 3 && i < 1000; i++) {
2088 if(lcoeff % i == 0) factorsl.push_back(i);
2089 }
2090 factorsl.push_back(1);
2091 if(lcoeff % 3 == 0) factorsl.push_back(lcoeff / 3);
2092 if(lcoeff % 2 == 0) factorsl.push_back(lcoeff / 2);
2093 factorsl.push_back(lcoeff);
2094
2095 long long int cmax = 500000LL / (factors0.size() * factorsl.size());
2096 if(term_combination_levels != 0) cmax *= 10;
2097 if(degree >= 2 && cmax > 10) {
2098 vector<Number> vden;
2099 vector<Number> vquo;
2100 vden.resize(3, nr_zero);
2101 long int c0;
2102 for(size_t i = 0; i < factors0.size() * 2; i++) {
2103 c0 = factors0[i / 2];
2104 if(i % 2 == 1) c0 = -c0;
2105 long int c2;
2106 for(size_t i2 = 0; i2 < factorsl.size(); i2++) {
2107 c2 = factorsl[i2];
2108 long int c1max = vs[1] - c0 - c2, c1min;
2109 if(c1max < 0) {c1min = c1max; c1max = -vs[1] - c0 - c2;}
2110 else {c1min = -vs[1] - c0 - c2;}
2111 if(-(vs[2] - c0 - c2) < -(-vs[2] - c0 - c2)) {
2112 if(c1max > -(-vs[2] - c0 - c2)) c1max = -(-vs[2] - c0 - c2);
2113 if(c1min < -(vs[2] - c0 - c2)) c1min = -(vs[2] - c0 - c2);
2114 } else {
2115 if(c1max > -(vs[2] - c0 - c2)) c1max = -(vs[2] - c0 - c2);
2116 if(c1min < -(-vs[2] - c0 - c2)) c1min = -(-vs[2] - c0 - c2);
2117 }
2118 if(c1min < -cmax / 2) c1min = -cmax / 2;
2119 for(long int c1 = c1min; c1 <= c1max && c1 <= cmax / 2; c1++) {
2120 long int v1 = ::labs(c2 + c1 + c0);
2121 long int v2 = ::labs(c2 - c1 + c0);
2122 if(v1 != 0 && v2 != 0 && v1 <= vs[1] && v2 <= vs[2] && (c1 != 0 || c2 != 0) && vs[1] % v1 == 0 && vs[2] % v2 == 0) {
2123 vden[0] = c0; vden[1] = c1; vden[2] = c2;
2124 if(CALCULATOR->aborted()) return false;
2125 if(polynomial_divide_integers(vnum, vden, vquo)) {
2126 MathStructure mtest;
2127 mtest.setType(STRUCT_ADDITION);
2128 if(c2 != 0) {
2129 MathStructure *mpow = new MathStructure();
2130 mpow->setType(STRUCT_POWER);
2131 mpow->addChild(*xvar);
2132 mpow->addChild_nocopy(new MathStructure(2, 1, 0));
2133 if(c2 == 1) {
2134 mtest.addChild_nocopy(mpow);
2135 } else {
2136 MathStructure *mterm = new MathStructure();
2137 mterm->setType(STRUCT_MULTIPLICATION);
2138 mterm->addChild_nocopy(new MathStructure(c2, 1L, 0L));
2139 mterm->addChild_nocopy(mpow);
2140 mtest.addChild_nocopy(mterm);
2141 }
2142 }
2143 if(c1 == 1) {
2144 mtest.addChild(*xvar);
2145 } else if(c1 != 0) {
2146 MathStructure *mterm = new MathStructure();
2147 mterm->setType(STRUCT_MULTIPLICATION);
2148 mterm->addChild_nocopy(new MathStructure(c1, 1L, 0L));
2149 mterm->addChild(*xvar);
2150 mtest.addChild_nocopy(mterm);
2151 }
2152 mtest.addChild_nocopy(new MathStructure(c0, 1L, 0L));
2153 MathStructure mthis(*this);
2154 MathStructure mquo;
2155 if(mtest.size() > 1 && polynomialDivide(mthis, mtest, mquo, eo, false)) {
2156 mquo.factorize(eo, false, 0, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
2157 set(mquo, true);
2158 multiply(mtest, true);
2159 return true;
2160 }
2161 }
2162 }
2163 }
2164 }
2165 }
2166 }
2167 for(int i_d = 3; i_d <= degree; i_d++) {
2168 if(CALCULATOR->aborted()) return false;
2169 long int t1max = ::pow(cmax / (i_d - 1), 1.0 / (i_d - 1));
2170 if(t1max < 1) break;
2171 if(t1max > 1000) t1max = 1000;
2172 long int c2totalmax = t1max;
2173 long int c2cur;
2174 for(int i = 0; i < i_d - 3; i++) {
2175 c2totalmax *= t1max;
2176 }
2177 vector<Number> vden;
2178 vector<Number> vquo;
2179 long int *vc = (long int*) malloc(sizeof(long int) * (i_d + 1));
2180 vden.resize(i_d + 1, nr_zero);
2181 int in = 0;
2182 for(size_t i = 0; i < factors0.size() * 2; i++) {
2183 vc[0] = factors0[i / 2] * (i % 2 == 1 ? -1 : 1);
2184 for(size_t i2 = 0; i2 < factorsl.size(); i2++) {
2185 vc[i_d] = factorsl[i2];
2186 for(long int c2p = 0; c2p <= c2totalmax; c2p++) {
2187 c2cur = c2p;
2188 for(int i = 2; i < i_d; i++) {
2189 vc[i] = c2cur % t1max;
2190 if(vc[i] % 2 == 1) vc[i] = -vc[i];
2191 vc[i] = vc[i] / 2 + vc[i] % 2;
2192 c2cur /= t1max;
2193 }
2194 long int c1max = t1max / 2 + t1max % 2, c1min = -t1max / 2 - t1max % 2;
2195 for(size_t i = 1; i < vs.size(); i++) {
2196 long int vsmax = vs[i] - vc[0];
2197 long int vsmin = -vs[i] - vc[0];
2198 int ix = (i / 2 + i % 2) * (i % 2 == 0 ? -1 : 1);
2199 int ixi = ix;
2200 for(int i2 = 2; i2 <= i_d; i2++) {
2201 ixi *= ix;
2202 vsmax -= vc[i2] * ixi;
2203 }
2204 vsmax /= ix;
2205 vsmin /= ix;
2206 if(vsmax < vsmin) {
2207 if(c1max > vsmin) c1max = vsmin;
2208 if(c1min < vsmax) c1min = vsmax;
2209 } else {
2210 if(c1max > vsmax) c1max = vsmax;
2211 if(c1min < vsmin) c1min = vsmin;
2212 }
2213 }
2214 for(long int c1 = c1min; c1 <= c1max; c1++) {
2215 vc[1] = c1;
2216 bool b = true;
2217 for(size_t i = 1; i < vs.size(); i++) {
2218 long int v = vc[0];
2219 int ix = (i / 2 + i % 2) * (i % 2 == 0 ? -1 : 1);
2220 int ixi = 1;
2221 for(int i2 = 1; i2 <= i_d; i2++) {
2222 ixi *= ix;
2223 v += vc[i2] * ixi;
2224 }
2225 if(v < 0) v = -v;
2226 if(v == 0 || v > vs[i] || vs[i] % v != 0) {
2227 b = false;
2228 break;
2229 }
2230 }
2231 in++;
2232 if(b) {
2233 if(CALCULATOR->aborted()) return false;
2234 for(size_t iden = 0; iden < vden.size(); iden++) {
2235 vden[iden] = vc[iden];
2236 }
2237 if(polynomial_divide_integers(vnum, vden, vquo)) {
2238 MathStructure mtest;
2239 mtest.setType(STRUCT_ADDITION);
2240 for(int i2 = i_d; i2 >= 2; i2--) {
2241 if(vc[i2] != 0) {
2242 MathStructure *mpow = new MathStructure();
2243 mpow->setType(STRUCT_POWER);
2244 mpow->addChild(*xvar);
2245 mpow->addChild_nocopy(new MathStructure(i2, 1, 0));
2246 if(vc[i2] == 1) {
2247 mtest.addChild_nocopy(mpow);
2248 } else {
2249 MathStructure *mterm = new MathStructure();
2250 mterm->setType(STRUCT_MULTIPLICATION);
2251 mterm->addChild_nocopy(new MathStructure(vc[i2], 1L, 0L));
2252 mterm->addChild_nocopy(mpow);
2253 mtest.addChild_nocopy(mterm);
2254 }
2255 }
2256 }
2257 if(vc[1] == 1) {
2258 mtest.addChild(*xvar);
2259 } else if(vc[1] != 0) {
2260 MathStructure *mterm = new MathStructure();
2261 mterm->setType(STRUCT_MULTIPLICATION);
2262 mterm->addChild_nocopy(new MathStructure(vc[1], 1L, 0L));
2263 mterm->addChild(*xvar);
2264 mtest.addChild_nocopy(mterm);
2265 }
2266 mtest.addChild_nocopy(new MathStructure(vc[0], 1L, 0L));
2267 MathStructure mthis(*this);
2268 MathStructure mquo;
2269 if(mtest.size() > 1 && polynomialDivide(mthis, mtest, mquo, eo, false)) {
2270 mquo.factorize(eo, false, 0, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
2271 free(vc);
2272 set(mquo, true);
2273 multiply(mtest, true);
2274 return true;
2275 }
2276 }
2277 }
2278 }
2279 }
2280 }
2281 }
2282 free(vc);
2283 }
2284 }
2285 }
2286
2287 }
2288 }
2289
2290 if(SIZE == 2 && max_factor_degree != 0) {
2291 Number nr1(1, 1, 0), nr2(1, 1, 0);
2292 bool b = true, b_nonnum = false;
2293 bool b1_neg = false, b2_neg = false;
2294 for(size_t i = 0; i < SIZE && b; i++) {
2295 b = false;
2296 if(CHILD(i).isInteger() && CHILD(i).number().integerLength() < 100) {
2297 b = true;
2298 if(i == 0) nr1 = CHILD(i).number();
2299 else nr2 = CHILD(i).number();
2300 } else if(CHILD(i).isMultiplication() && CHILD(i).size() > 1) {
2301 b_nonnum = true;
2302 b = true;
2303 size_t i2 = 0;
2304 if(CHILD(i)[0].isInteger() && CHILD(i).number().integerLength() < 100) {
2305 if(i == 0) nr1 = CHILD(i)[0].number();
2306 else nr2 = CHILD(i)[0].number();
2307 i2++;
2308 }
2309 for(; i2 < CHILD(i).size(); i2++) {
2310 if(!CHILD(i)[i2].isPower() || !CHILD(i)[i2][1].isInteger() || !CHILD(i)[i2][1].number().isPositive() || !CHILD(i)[i2][1].number().isEven() || CHILD(i)[1].number().integerLength() >= 100 || !CHILD(i)[i2][0].representsNonMatrix()) {
2311 b = false;
2312 break;
2313 }
2314 }
2315 } else if(CHILD(i).isPower() && CHILD(i)[1].isNumber() && CHILD(i)[1].number().isInteger() && CHILD(i)[1].number().isPositive() && CHILD(i)[1].number().isEven() && CHILD(i)[1].number().integerLength() < 100 && CHILD(i)[0].representsNonMatrix()) {
2316 b_nonnum = true;
2317 b = true;
2318 }
2319 }
2320 if(!b_nonnum) b = false;
2321 if(b) {
2322 b1_neg = nr1.isNegative();
2323 b2_neg = nr2.isNegative();
2324 if(b1_neg == b2_neg) b = false;
2325 }
2326 if(b) {
2327 if(b1_neg) b = nr1.negate();
2328 if(b && !nr1.isOne()) {
2329 b = nr1.isPerfectSquare() && nr1.isqrt();
2330 }
2331 }
2332 if(b) {
2333 if(b2_neg) nr2.negate();
2334 if(!nr2.isOne()) {
2335 b = nr2.isPerfectSquare() && nr2.isqrt();
2336 }
2337 }
2338 if(b) {
2339 bool calc = false;
2340 MathStructure *mmul = new MathStructure(*this);
2341 for(size_t i = 0; i < SIZE; i++) {
2342 if(CHILD(i).isNumber()) {
2343 if(i == 0) {
2344 CHILD(i).number() = nr1;
2345 if(b1_neg) nr1.negate();
2346 (*mmul)[i].number() = nr1;
2347 } else {
2348 CHILD(i).number() = nr2;
2349 if(b2_neg) nr2.negate();
2350 (*mmul)[i].number() = nr2;
2351 }
2352 } else if(CHILD(i).isMultiplication() && CHILD(i).size() > 1) {
2353 b = true;
2354 size_t i2 = 0;
2355 if(CHILD(i)[0].isNumber()) {
2356 if(i == 0) {
2357 CHILD(i)[0].number() = nr1;
2358 if(b1_neg) nr1.negate();
2359 (*mmul)[i][0].number() = nr1;
2360 } else {
2361 CHILD(i)[0].number() = nr2;
2362 if(b2_neg) nr2.negate();
2363 (*mmul)[i][0].number() = nr2;
2364 }
2365 i2++;
2366 }
2367 for(; i2 < CHILD(i).size(); i2++) {
2368 if(CHILD(i)[i2][1].number().isTwo()) {
2369 CHILD(i)[i2].setToChild(1, true);
2370 (*mmul)[i][i2].setToChild(1, true);
2371 } else {
2372 CHILD(i)[i2][1].number().divide(2);
2373 (*mmul)[i][i2][1].number().divide(2);
2374 }
2375 CHILD(i).childUpdated(i2 + 1);
2376 (*mmul)[i].childUpdated(i2 + 1);
2377 }
2378 if(CHILD(i)[0].isOne()) CHILD(i).delChild(1, true);
2379 if((*mmul)[i][0].isOne()) (*mmul)[i].delChild(1, true);
2380 } else if(CHILD(i).isPower()) {
2381 if(CHILD(i)[1].number().isTwo()) {
2382 CHILD(i).setToChild(1, true);
2383 (*mmul)[i].setToChild(1, true);
2384 } else {
2385 CHILD(i)[1].number().divide(2);
2386 (*mmul)[i][1].number().divide(2);
2387 }
2388 }
2389 if(CHILD(i).isAddition()) calc = true;
2390 CHILD_UPDATED(i)
2391 mmul->childUpdated(i + 1);
2392 }
2393 if(calc) {
2394 calculatesub(eo, eo, false);
2395 mmul->calculatesub(eo, eo, false);
2396 }
2397 if(recursive) {
2398 factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
2399 mmul->factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
2400 }
2401 multiply_nocopy(mmul);
2402 evalSort(true);
2403 return true;
2404 }
2405 }
2406
2407 //x^3-y^3=(x-y)(x^2+xy+y^2)
2408 if(max_factor_degree != 0 && SIZE == 2 && CHILD(0).isPower() && CHILD(0)[1].isNumber() && CHILD(0)[1].number() == 3 && CHILD(1).isMultiplication() && CHILD(1).size() == 2 && CHILD(1)[0].isMinusOne() && CHILD(1)[1].isPower() && CHILD(1)[1][1].isNumber() && CHILD(1)[1][1].number() == 3) {
2409 if(CHILD(0)[0].representsNonMatrix() && CHILD(1)[1][0].representsNonMatrix()) {
2410 MathStructure *m2 = new MathStructure(*this);
2411 (*m2)[0].setToChild(1, true);
2412 (*m2)[1][1].setToChild(1, true);
2413 EvaluationOptions eo2 = eo;
2414 eo2.expand = false;
2415 m2->calculatesub(eo2, eo2, false);
2416 CHILD(0)[1].set(2, 1, 0, true);
2417 CHILD(1).setToChild(2, true);
2418 CHILD(1)[1].set(2, 1, 0, true);
2419 MathStructure *m3 = new MathStructure(CHILD(0)[0]);
2420 m3->calculateMultiply(CHILD(1)[0], eo2);
2421 add_nocopy(m3, true);
2422 calculatesub(eo2, eo2, false);
2423 multiply_nocopy(m2, true);
2424 evalSort(true);
2425 return true;
2426 }
2427 }
2428 //-x^3+y^3=(-x+y)(x^2+xy+y^2)
2429 if(max_factor_degree != 0 && SIZE == 2 && CHILD(1).isPower() && CHILD(1)[1].isNumber() && CHILD(1)[1].number() == 3 && CHILD(0).isMultiplication() && CHILD(0).size() == 2 && CHILD(0)[0].isMinusOne() && CHILD(0)[1].isPower() && CHILD(0)[1][1].isNumber() && CHILD(0)[1][1].number() == 3) {
2430 if(CHILD(1)[0].representsNonMatrix() && CHILD(0)[1][0].representsNonMatrix()) {
2431 MathStructure *m2 = new MathStructure(*this);
2432 (*m2)[1].setToChild(1, true);
2433 (*m2)[0][1].setToChild(1, true);
2434 EvaluationOptions eo2 = eo;
2435 eo2.expand = false;
2436 m2->calculatesub(eo2, eo2, false);
2437 CHILD(1)[1].set(2, 1, 0, true);
2438 CHILD(0).setToChild(2, true);
2439 CHILD(0)[1].set(2, 1, 0, true);
2440 MathStructure *m3 = new MathStructure(CHILD(0)[0]);
2441 m3->calculateMultiply(CHILD(1)[0], eo2);
2442 add_nocopy(m3, true);
2443 calculatesub(eo2, eo2, false);
2444 multiply_nocopy(m2, true);
2445 evalSort(true);
2446 return true;
2447 }
2448 }
2449
2450 if(max_factor_degree != 0 && !only_integers && !force_factorization.isUndefined() && SIZE >= 2) {
2451 MathStructure mexp, madd, mmul;
2452 if(gather_factors(*this, force_factorization, madd, mmul, mexp) && !madd.isZero() && !mmul.isZero() && mexp.isInteger() && mexp.number().isGreaterThan(nr_two)) {
2453 if(!mmul.isOne()) madd.calculateDivide(mmul, eo);
2454 bool overflow = false;
2455 int n = mexp.number().intValue(&overflow);
2456 if(!overflow) {
2457 if(n % 4 == 0) {
2458 int i_u = 1;
2459 if(n != 4) {
2460 i_u = n / 4;
2461 }
2462 MathStructure m_sqrt2(2, 1, 0);
2463 m_sqrt2.calculateRaise(nr_half, eo);
2464 MathStructure m_sqrtb(madd);
2465 m_sqrtb.calculateRaise(nr_half, eo);
2466 MathStructure m_bfourth(madd);
2467 m_bfourth.calculateRaise(Number(1, 4), eo);
2468 m_sqrt2.calculateMultiply(m_bfourth, eo);
2469 MathStructure m_x(force_factorization);
2470 if(i_u != 1) m_x ^= i_u;
2471 m_sqrt2.calculateMultiply(m_x, eo);
2472 MathStructure *m2 = new MathStructure(force_factorization);
2473 m2->raise(Number(i_u * 2, 1));
2474 m2->add(m_sqrtb);
2475 m2->calculateAdd(m_sqrt2, eo);
2476 set(force_factorization, true);
2477 raise(Number(i_u * 2, 1));
2478 add(m_sqrtb);
2479 calculateSubtract(m_sqrt2, eo);
2480 multiply_nocopy(m2);
2481 } else {
2482 int i_u = 1;
2483 if(n % 2 == 0) {
2484 i_u = 2;
2485 n /= 2;
2486 }
2487 MathStructure *m2 = new MathStructure(madd);
2488 m2->calculateRaise(Number(n - 1, n), eo);
2489 for(int i = 1; i < n - 1; i++) {
2490 MathStructure *mterm = new MathStructure(madd);
2491 mterm->calculateRaise(Number(n - i - 1, n), eo);
2492 mterm->multiply(force_factorization);
2493 if(i != 1 || i_u != 1) {
2494 mterm->last().raise(Number(i * i_u, 1));
2495 mterm->childUpdated(mterm->size());
2496 }
2497 if(i % 2 == 1) mterm->calculateMultiply(m_minus_one, eo);
2498 m2->add_nocopy(mterm, true);
2499 }
2500 MathStructure *mterm = new MathStructure(force_factorization);
2501 mterm->raise(Number((n - 1) * i_u, 1));
2502 m2->add_nocopy(mterm, true);
2503 mterm = new MathStructure(force_factorization);
2504 if(i_u != 1) mterm->raise(Number(i_u, 1));
2505 set(madd, true);
2506 calculateRaise(Number(1, n), eo);
2507 add_nocopy(mterm);
2508 multiply_nocopy(m2);
2509 }
2510 if(!mmul.isOne()) multiply(mmul, true);
2511 evalSort(true);
2512 return true;
2513 }
2514 }
2515 }
2516
2517 //-x-y = -(x+y)
2518 bool b = true;
2519 for(size_t i2 = 0; i2 < SIZE; i2++) {
2520 if((!CHILD(i2).isNumber() || !CHILD(i2).number().isNegative()) && (!CHILD(i2).isMultiplication() || CHILD(i2).size() < 2 || !CHILD(i2)[0].isNumber() || !CHILD(i2)[0].number().isNegative())) {
2521 b = false;
2522 break;
2523 }
2524 }
2525 if(b) {
2526 for(size_t i2 = 0; i2 < SIZE; i2++) {
2527 if(CHILD(i2).isNumber()) {
2528 CHILD(i2).number().negate();
2529 } else {
2530 CHILD(i2)[0].number().negate();
2531 if(CHILD(i2)[0].isOne() && CHILD(i2).size() > 1) {
2532 CHILD(i2).delChild(1);
2533 if(CHILD(i2).size() == 1) {
2534 CHILD(i2).setToChild(1, true);
2535 }
2536 }
2537 }
2538 }
2539 multiply(MathStructure(-1, 1, 0));
2540 CHILD_TO_FRONT(1)
2541 }
2542
2543 for(size_t i = 0; i < SIZE; i++) {
2544 if(CHILD(i).isMultiplication() && CHILD(i).size() > 1) {
2545 for(size_t i2 = 0; i2 < CHILD(i).size(); i2++) {
2546 if(CHILD(i)[i2].isAddition()) {
2547 for(size_t i3 = i + 1; i3 < SIZE; i3++) {
2548 if(CHILD(i3).isMultiplication() && CHILD(i3).size() > 1) {
2549 for(size_t i4 = 0; i4 < CHILD(i3).size(); i4++) {
2550 if(CHILD(i3)[i4].isAddition() && CHILD(i3)[i4] == CHILD(i)[i2]) {
2551 MathStructure *mfac = &CHILD(i)[i2];
2552 mfac->ref();
2553 CHILD(i).delChild(i2 + 1, true);
2554 CHILD(i3).delChild(i4 + 1, true);
2555 CHILD(i3).ref();
2556 CHILD(i).add_nocopy(&CHILD(i3));
2557 CHILD(i).calculateAddLast(eo);
2558 CHILD(i).multiply_nocopy(mfac);
2559 CHILD_UPDATED(i)
2560 delChild(i3 + 1, true);
2561 evalSort(true);
2562 factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
2563 return true;
2564 }
2565 }
2566 }
2567 }
2568 if(SIZE > 2) {
2569 MathStructure mtest(*this);
2570 mtest.delChild(i + 1);
2571 if(mtest == CHILD(i)[i2]) {
2572 CHILD(i).delChild(i2 + 1, true);
2573 SET_CHILD_MAP(i);
2574 add(m_one, true);
2575 multiply(mtest);
2576 evalSort(true);
2577 factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
2578 return true;
2579 }
2580 }
2581 }
2582 }
2583 }
2584 }
2585 }
2586
2587 //complete the square
2588 if(max_factor_degree != 0 && (term_combination_levels != 0 || complete_square)) {
2589 if(only_integers) {
2590 if(SIZE <= 3 && SIZE > 1) {
2591 MathStructure *xvar = NULL;
2592 Number nr2(1, 1);
2593 if(CHILD(0).isPower() && CHILD(0)[0].size() == 0 && CHILD(0)[1].isNumber() && CHILD(0)[1].number().isTwo()) {
2594 xvar = &CHILD(0)[0];
2595 } else if(CHILD(0).isMultiplication() && CHILD(0).size() == 2 && CHILD(0)[0].isNumber()) {
2596 if(CHILD(0)[1].isPower()) {
2597 if(CHILD(0)[1][0].size() == 0 && CHILD(0)[1][1].isNumber() && CHILD(0)[1][1].number().isTwo()) {
2598 xvar = &CHILD(0)[1][0];
2599 nr2.set(CHILD(0)[0].number());
2600 }
2601 }
2602 }
2603 if(xvar) {
2604 bool factorable = false;
2605 Number nr1, nr0;
2606 if(SIZE == 2 && CHILD(1).isNumber()) {
2607 factorable = true;
2608 nr0 = CHILD(1).number();
2609 } else if(SIZE == 3 && CHILD(2).isNumber()) {
2610 nr0 = CHILD(2).number();
2611 if(CHILD(1).isMultiplication()) {
2612 if(CHILD(1).size() == 2 && CHILD(1)[0].isNumber() && xvar->equals(CHILD(1)[1])) {
2613 nr1 = CHILD(1)[0].number();
2614 factorable = true;
2615 }
2616 } else if(xvar->equals(CHILD(1))) {
2617 nr1.set(1, 1, 0);
2618 factorable = true;
2619 }
2620 }
2621 if(factorable && !nr2.isZero() && !nr1.isZero()) {
2622 Number nrh(nr1);
2623 nrh /= 2;
2624 nrh /= nr2;
2625 if(nrh.isInteger()) {
2626 Number nrk(nrh);
2627 if(nrk.square()) {
2628 nrk *= nr2;
2629 nrk.negate();
2630 nrk += nr0;
2631 set(MathStructure(*xvar), true);
2632 add(nrh);
2633 raise(nr_two);
2634 if(!nr2.isOne()) multiply(nr2);
2635 if(!nrk.isZero()) add(nrk);
2636 evalSort(true);
2637 return true;
2638 }
2639 }
2640 }
2641 }
2642 }
2643 } else {
2644 MathStructure m2, m1, m0;
2645 const MathStructure *xvar = NULL;
2646 if(!force_factorization.isUndefined()) {
2647 xvar = &force_factorization;
2648 } else {
2649 if(CHILD(0).isPower() && CHILD(0)[0].size() == 0 && CHILD(0)[1].isNumber() && CHILD(0)[1].number().isTwo()) {
2650 xvar = &CHILD(0)[0];
2651 } else if(CHILD(0).isMultiplication()) {
2652 for(size_t i2 = 0; i2 < CHILD(0).size(); i2++) {
2653 if(CHILD(0).isPower() && CHILD(0)[i2][0].size() == 0 && CHILD(0)[i2][1].isNumber() && CHILD(0)[i2][1].number().isTwo()) {
2654 xvar = &CHILD(0)[0];
2655 }
2656 }
2657 }
2658 }
2659 if(xvar && gather_factors(*this, *xvar, m0, m1, m2, true) && !m1.isZero() && !m2.isZero()) {
2660 MathStructure *mx = new MathStructure(*xvar);
2661 set(m1, true);
2662 calculateMultiply(nr_half, eo);
2663 if(!m2.isOne()) calculateDivide(m2, eo);
2664 add_nocopy(mx);
2665 calculateAddLast(eo);
2666 raise(nr_two);
2667 if(!m2.isOne()) multiply(m2);
2668 if(!m1.isOne()) m1.calculateRaise(nr_two, eo);
2669 m1.calculateMultiply(Number(-1, 4), eo);
2670 if(!m2.isOne()) {
2671 m2.calculateInverse(eo);
2672 m1.calculateMultiply(m2, eo);
2673 }
2674 m0.calculateAdd(m1, eo);
2675 if(!m0.isZero()) add(m0);
2676 if(recursive) {
2677 CHILD(0).factorize(eo, false, 0, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
2678 CHILD(1).factorize(eo, false, 0, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
2679 CHILDREN_UPDATED
2680 }
2681 evalSort(true);
2682 return true;
2683 }
2684 }
2685 }
2686
2687 //Try factorize combinations of terms
2688 if(SIZE > 2 && term_combination_levels > 0) {
2689 bool b = false, b_ret = false;
2690 // 5/y + x/y + z = (5 + x)/y + z
2691 MathStructure mstruct_units(*this);
2692 MathStructure mstruct_new(*this);
2693 for(size_t i = 0; i < mstruct_units.size(); i++) {
2694 if(mstruct_units[i].isMultiplication()) {
2695 for(size_t i2 = 0; i2 < mstruct_units[i].size();) {
2696 if(!mstruct_units[i][i2].isPower() || !mstruct_units[i][i2][1].hasNegativeSign()) {
2697 mstruct_units[i].delChild(i2 + 1);
2698 } else {
2699 i2++;
2700 }
2701 }
2702 if(mstruct_units[i].size() == 0) mstruct_units[i].setUndefined();
2703 else if(mstruct_units[i].size() == 1) mstruct_units[i].setToChild(1);
2704 for(size_t i2 = 0; i2 < mstruct_new[i].size();) {
2705 if(mstruct_new[i][i2].isPower() && mstruct_new[i][i2][1].hasNegativeSign()) {
2706 mstruct_new[i].delChild(i2 + 1);
2707 } else {
2708 i2++;
2709 }
2710 }
2711 if(mstruct_new[i].size() == 0) mstruct_new[i].set(1, 1, 0);
2712 else if(mstruct_new[i].size() == 1) mstruct_new[i].setToChild(1);
2713 } else if(mstruct_new[i].isPower() && mstruct_new[i][1].hasNegativeSign()) {
2714 mstruct_new[i].set(1, 1, 0);
2715 } else {
2716 mstruct_units[i].setUndefined();
2717 }
2718 }
2719 for(size_t i = 0; i < mstruct_units.size(); i++) {
2720 if(!mstruct_units[i].isUndefined()) {
2721 for(size_t i2 = i + 1; i2 < mstruct_units.size();) {
2722 if(mstruct_units[i2] == mstruct_units[i]) {
2723 mstruct_new[i].add(mstruct_new[i2], true);
2724 mstruct_new.delChild(i2 + 1);
2725 mstruct_units.delChild(i2 + 1);
2726 b = true;
2727 } else {
2728 i2++;
2729 }
2730 }
2731 if(mstruct_new[i].isOne()) mstruct_new[i].set(mstruct_units[i]);
2732 else mstruct_new[i].multiply(mstruct_units[i], true);
2733 }
2734 }
2735 if(b) {
2736 if(mstruct_new.size() == 1) {
2737 set(mstruct_new[0], true);
2738 factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
2739 return true;
2740 } else {
2741 set(mstruct_new);
2742 }
2743 b = false;
2744 b_ret = true;
2745 }
2746 // a*y + a*z + x = a(y + z) + x
2747 vector<MathStructure> syms;
2748 vector<size_t> counts;
2749 collect_symbols(*this, syms);
2750 size_t max_count = 0, max_i = 0;
2751 Number min_pow;
2752 for(size_t i = 0; i < syms.size(); i++) {
2753 if(syms[i].containsUnknowns()) {
2754 size_t count = 0;
2755 Number min_pow_i;
2756 for(size_t i2 = 0; i2 < SIZE; i2++) {
2757 if(CHILD(i2).isMultiplication()) {
2758 for(size_t i3 = 0; i3 < CHILD(i2).size(); i3++) {
2759 if(CHILD(i2)[i3].isPower() && CHILD(i2)[i3][1].isNumber() && CHILD(i2)[i3][1].number().isRational() && CHILD(i2)[i3][1].number().isNegative() && CHILD(i2)[i3][0] == syms[i]) {
2760 if(min_pow_i.isZero() || CHILD(i2)[i3][1].number() > min_pow_i) min_pow_i = CHILD(i2)[i3][1].number();
2761 count++;
2762 break;
2763 }
2764 }
2765 } else if(CHILD(i2).isPower() && CHILD(i2)[1].isNumber() && CHILD(i2)[1].number().isRational() && CHILD(i2)[1].number().isNegative() && CHILD(i2)[0] == syms[i]) {
2766 if(min_pow_i.isZero() || CHILD(i2)[1].number() > min_pow_i) min_pow_i = CHILD(i2)[1].number();
2767 count++;
2768 }
2769 }
2770 if(count > 1 && count > max_count) {
2771 max_count = count;
2772 min_pow = min_pow_i;
2773 max_i = i;
2774 }
2775 }
2776 }
2777 if(!max_count) {
2778 for(size_t i = 0; i < syms.size(); i++) {
2779 if(syms[i].containsUnknowns()) {
2780 size_t count = 0;
2781 Number min_pow_i;
2782 for(size_t i2 = 0; i2 < SIZE; i2++) {
2783 if(CHILD(i2).isMultiplication()) {
2784 for(size_t i3 = 0; i3 < CHILD(i2).size(); i3++) {
2785 if(CHILD(i2)[i3].isPower() && CHILD(i2)[i3][1].isNumber() && CHILD(i2)[i3][1].number().isRational() && CHILD(i2)[i3][1].number().isPositive() && CHILD(i2)[i3][0] == syms[i]) {
2786 if(min_pow_i.isZero() || CHILD(i2)[i3][1].number() < min_pow_i) min_pow_i = CHILD(i2)[i3][1].number();
2787 count++;
2788 break;
2789 } else if(CHILD(i2)[i3] == syms[i]) {
2790 if(min_pow_i.isZero() || min_pow_i > 1) min_pow_i = 1;
2791 count++;
2792 break;
2793 }
2794 }
2795 } else if(CHILD(i2).isPower() && CHILD(i2)[1].isNumber() && CHILD(i2)[1].number().isRational() && CHILD(i2)[1].number().isPositive() && CHILD(i2)[0] == syms[i]) {
2796 if(min_pow_i.isZero() || CHILD(i2)[1].number() < min_pow_i) min_pow_i = CHILD(i2)[1].number();
2797 count++;
2798 } else if(CHILD(i2) == syms[i]) {
2799 if(min_pow_i.isZero() || min_pow_i > 1) min_pow_i = 1;
2800 count++;
2801 }
2802 }
2803 if(count > 1 && count > max_count) {
2804 max_count = count;
2805 min_pow = min_pow_i;
2806 max_i = i;
2807 }
2808 }
2809 }
2810 }
2811 if(max_count > 0) {
2812 size_t i = max_i;
2813 vector<MathStructure*> mleft;
2814 for(size_t i2 = 0; i2 < SIZE;) {
2815 b = false;
2816 if(CHILD(i2).isMultiplication()) {
2817 for(size_t i3 = 0; i3 < CHILD(i2).size(); i3++) {
2818 if(CHILD(i2)[i3].isPower() && CHILD(i2)[i3][1].isNumber() && CHILD(i2)[i3][1].number().isRational() && (min_pow.isPositive() ? CHILD(i2)[i3][1].number().isPositive() : CHILD(i2)[i3][1].number().isNegative()) && CHILD(i2)[i3][0] == syms[i]) {
2819 if(CHILD(i2)[i3][1] == min_pow) CHILD(i2).delChild(i3 + 1, true);
2820 else if(CHILD(i2)[i3][1] == min_pow + 1) CHILD(i2)[i3].setToChild(1, true);
2821 else {
2822 CHILD(i2)[i3][1].number() -= min_pow;
2823 factorize_fix_root_power(CHILD(i2)[i3]);
2824 }
2825 b = true;
2826 break;
2827 } else if(min_pow.isPositive() && CHILD(i2)[i3] == syms[i]) {
2828 if(min_pow.isOne()) CHILD(i2).delChild(i3 + 1, true);
2829 else {
2830 CHILD(i2)[i3].raise((-min_pow) + 1);
2831 factorize_fix_root_power(CHILD(i2)[i3]);
2832 }
2833 b = true;
2834 break;
2835 }
2836 }
2837 } else if(CHILD(i2).isPower() && CHILD(i2)[1].isNumber() && CHILD(i2)[1].number().isRational() && (min_pow.isPositive() ? CHILD(i2)[1].number().isPositive() : CHILD(i2)[1].number().isNegative()) && CHILD(i2)[0] == syms[i]) {
2838 if(CHILD(i2)[1] == min_pow) CHILD(i2).set(1, 1, 0, true);
2839 else if(CHILD(i2)[1] == min_pow + 1) CHILD(i2).setToChild(1, true);
2840 else {
2841 CHILD(i2)[1].number() -= min_pow;
2842 factorize_fix_root_power(CHILD(i2));
2843 }
2844 b = true;
2845 } else if(min_pow.isPositive() && CHILD(i2) == syms[i]) {
2846 if(min_pow.isOne()) CHILD(i2).set(1, 1, 0, true);
2847 else {
2848 CHILD(i2).raise((-min_pow) + 1);
2849 factorize_fix_root_power(CHILD(i2));
2850 }
2851 b = true;
2852 }
2853 if(b) {
2854 i2++;
2855 } else {
2856 CHILD(i2).ref();
2857 mleft.push_back(&CHILD(i2));
2858 ERASE(i2)
2859 }
2860 }
2861 multiply(syms[i]);
2862 if(!min_pow.isOne()) LAST ^= min_pow;
2863 for(size_t i2 = 0; i2 < mleft.size(); i2++) {
2864 add_nocopy(mleft[i2], true);
2865 }
2866 factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
2867 return true;
2868 }
2869 if(LAST.isNumber()) {
2870 MathStructure *mdel = &LAST;
2871 mdel->ref();
2872 delChild(SIZE, true);
2873 b = factorize(eo, false, term_combination_levels - 1, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
2874 add_nocopy(mdel, true);
2875 if(term_combination_levels == 1) return b || b_ret;
2876 if(b) b_ret = true;
2877 }
2878 for(size_t i = 0; !b && i < SIZE; i++) {
2879 MathStructure *mdel = &CHILD(i);
2880 mdel->ref();
2881 delChild(i + 1, true);
2882 b = true;
2883 if(mdel->isMultiplication()) {
2884 for(size_t i2 = 0; i2 < mdel->size(); i2++) {
2885 if((*mdel)[i2].isPower() && (*mdel)[i2][0].containsUnknowns()) {
2886 if(contains((*mdel)[i2][0], false, false, false) > 0) {b = false; break;}
2887 } else if((*mdel)[i2].containsUnknowns()) {
2888 if(contains((*mdel)[i2], false, false, false) > 0) {b = false; break;}
2889 }
2890 }
2891
2892 } else {
2893 b = contains(*mdel, false, false, false) <= 0;
2894 }
2895 if(b) {
2896 b = factorize(eo, false, term_combination_levels - 1, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
2897 if(recursive) mdel->factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
2898 add_nocopy(mdel, true);
2899 if(term_combination_levels == 1) return b || b_ret;
2900 if(b) b_ret = true;
2901 break;
2902 } else {
2903 insertChild_nocopy(mdel, i + 1);
2904 }
2905 }
2906 b = false;
2907 // a*y + a*z + x = a(y + z) + x
2908 syms.clear();
2909 counts.clear();
2910 collect_symbols(*this, syms);
2911 max_count = 0; max_i = 0;
2912 for(size_t i = 0; i < syms.size(); i++) {
2913 size_t count = 0;
2914 Number min_pow_i;
2915 for(size_t i2 = 0; i2 < SIZE; i2++) {
2916 if(CHILD(i2).isMultiplication()) {
2917 for(size_t i3 = 0; i3 < CHILD(i2).size(); i3++) {
2918 if(CHILD(i2)[i3].isPower() && CHILD(i2)[i3][1].isNumber() && CHILD(i2)[i3][1].number().isRational() && CHILD(i2)[i3][1].number().isNegative() && CHILD(i2)[i3][0] == syms[i]) {
2919 if(min_pow_i.isZero() || CHILD(i2)[i3][1].number() > min_pow_i) min_pow_i = CHILD(i2)[i3][1].number();
2920 count++;
2921 break;
2922 }
2923 }
2924 } else if(CHILD(i2).isPower() && CHILD(i2)[1].isNumber() && CHILD(i2)[1].number().isRational() && CHILD(i2)[1].number().isNegative() && CHILD(i2)[0] == syms[i]) {
2925 if(min_pow_i.isZero() || CHILD(i2)[1].number() > min_pow_i) min_pow_i = CHILD(i2)[1].number();
2926 count++;
2927 }
2928 }
2929 if(count > 1 && count > max_count) {
2930 max_count = count;
2931 min_pow = min_pow_i;
2932 max_i = i;
2933 }
2934 }
2935 if(!max_count) {
2936 for(size_t i = 0; i < syms.size(); i++) {
2937 size_t count = 0;
2938 Number min_pow_i;
2939 for(size_t i2 = 0; i2 < SIZE; i2++) {
2940 if(CHILD(i2).isMultiplication()) {
2941 for(size_t i3 = 0; i3 < CHILD(i2).size(); i3++) {
2942 if(CHILD(i2)[i3].isPower() && CHILD(i2)[i3][1].isNumber() && CHILD(i2)[i3][1].number().isRational() && CHILD(i2)[i3][1].number().isPositive() && CHILD(i2)[i3][0] == syms[i]) {
2943 if(min_pow_i.isZero() || CHILD(i2)[i3][1].number() < min_pow_i) min_pow_i = CHILD(i2)[i3][1].number();
2944 count++;
2945 break;
2946 } else if(CHILD(i2)[i3] == syms[i]) {
2947 if(min_pow_i.isZero() || min_pow_i > 1) min_pow_i = 1;
2948 count++;
2949 break;
2950 }
2951 }
2952 } else if(CHILD(i2).isPower() && CHILD(i2)[1].isNumber() && CHILD(i2)[1].number().isRational() && CHILD(i2)[1].number().isPositive() && CHILD(i2)[0] == syms[i]) {
2953 if(min_pow_i.isZero() || CHILD(i2)[1].number() < min_pow_i) min_pow_i = CHILD(i2)[1].number();
2954 count++;
2955 } else if(CHILD(i2) == syms[i]) {
2956 if(min_pow_i.isZero() || min_pow_i > 1) min_pow_i = 1;
2957 count++;
2958 }
2959 }
2960 if(count > 1 && count > max_count) {
2961 max_count = count;
2962 min_pow = min_pow_i;
2963 max_i = i;
2964 }
2965 }
2966 }
2967 if(max_count > 0) {
2968 size_t i = max_i;
2969 vector<MathStructure*> mleft;
2970 for(size_t i2 = 0; i2 < SIZE;) {
2971 b = false;
2972 if(CHILD(i2).isMultiplication()) {
2973 for(size_t i3 = 0; i3 < CHILD(i2).size(); i3++) {
2974 if(CHILD(i2)[i3].isPower() && CHILD(i2)[i3][1].isNumber() && CHILD(i2)[i3][1].number().isRational() && (min_pow.isPositive() ? CHILD(i2)[i3][1].number().isPositive() : CHILD(i2)[i3][1].number().isNegative()) && CHILD(i2)[i3][0] == syms[i]) {
2975 if(CHILD(i2)[i3][1] == min_pow) CHILD(i2).delChild(i3 + 1, true);
2976 else if(CHILD(i2)[i3][1] == min_pow + 1) CHILD(i2)[i3].setToChild(1, true);
2977 else {
2978 CHILD(i2)[i3][1].number() -= min_pow;
2979 factorize_fix_root_power(CHILD(i2)[i3]);
2980 }
2981 b = true;
2982 break;
2983 } else if(min_pow.isPositive() && CHILD(i2)[i3] == syms[i]) {
2984 if(min_pow.isOne()) CHILD(i2).delChild(i3 + 1, true);
2985 else {
2986 CHILD(i2)[i3].raise((-min_pow) + 1);
2987 factorize_fix_root_power(CHILD(i2)[i3]);
2988 }
2989 b = true;
2990 break;
2991 }
2992 }
2993 } else if(CHILD(i2).isPower() && CHILD(i2)[1].isNumber() && CHILD(i2)[1].number().isRational() && (min_pow.isPositive() ? CHILD(i2)[1].number().isPositive() : CHILD(i2)[1].number().isNegative()) && CHILD(i2)[0] == syms[i]) {
2994 if(CHILD(i2)[1] == min_pow) CHILD(i2).set(1, 1, 0, true);
2995 else if(CHILD(i2)[1] == min_pow + 1) CHILD(i2).setToChild(1, true);
2996 else {
2997 CHILD(i2)[1].number() -= min_pow;
2998 factorize_fix_root_power(CHILD(i2));
2999 }
3000 b = true;
3001 } else if(min_pow.isPositive() && CHILD(i2) == syms[i]) {
3002 if(min_pow.isOne()) CHILD(i2).set(1, 1, 0, true);
3003 else {
3004 CHILD(i2).raise((-min_pow) + 1);
3005 factorize_fix_root_power(CHILD(i2));
3006 }
3007 b = true;
3008 }
3009 if(b) {
3010 i2++;
3011 } else {
3012 CHILD(i2).ref();
3013 mleft.push_back(&CHILD(i2));
3014 ERASE(i2)
3015 }
3016 }
3017 multiply(syms[i]);
3018 if(!min_pow.isOne()) LAST ^= min_pow;
3019 for(size_t i2 = 0; i2 < mleft.size(); i2++) {
3020 add_nocopy(mleft[i2], true);
3021 }
3022 factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
3023 return true;
3024 }
3025 if(isAddition()) {
3026 b = false;
3027 // y*f(x) + z*f(x) = (y+z)*f(x)
3028 mstruct_units.set(*this);
3029 mstruct_new.set(*this);
3030 for(size_t i = 0; i < mstruct_units.size(); i++) {
3031 if(mstruct_units[i].isMultiplication()) {
3032 for(size_t i2 = 0; i2 < mstruct_units[i].size();) {
3033 if(!combination_factorize_is_complicated(mstruct_units[i][i2])) {
3034 mstruct_units[i].delChild(i2 + 1);
3035 } else {
3036 i2++;
3037 }
3038 }
3039 if(mstruct_units[i].size() == 0) mstruct_units[i].setUndefined();
3040 else if(mstruct_units[i].size() == 1) mstruct_units[i].setToChild(1);
3041 for(size_t i2 = 0; i2 < mstruct_new[i].size();) {
3042 if(combination_factorize_is_complicated(mstruct_new[i][i2])) {
3043 mstruct_new[i].delChild(i2 + 1);
3044 } else {
3045 i2++;
3046 }
3047 }
3048 if(mstruct_new[i].size() == 0) mstruct_new[i].set(1, 1, 0);
3049 else if(mstruct_new[i].size() == 1) mstruct_new[i].setToChild(1);
3050 } else if(combination_factorize_is_complicated(mstruct_units[i])) {
3051 mstruct_new[i].set(1, 1, 0);
3052 } else {
3053 mstruct_units[i].setUndefined();
3054 }
3055 }
3056 for(size_t i = 0; i < mstruct_units.size(); i++) {
3057 if(!mstruct_units[i].isUndefined()) {
3058 for(size_t i2 = i + 1; i2 < mstruct_units.size();) {
3059 if(mstruct_units[i2] == mstruct_units[i]) {
3060 mstruct_new[i].add(mstruct_new[i2], true);
3061 mstruct_new.delChild(i2 + 1);
3062 mstruct_units.delChild(i2 + 1);
3063 b = true;
3064 } else {
3065 i2++;
3066 }
3067 }
3068 if(mstruct_new[i].isOne()) mstruct_new[i].set(mstruct_units[i]);
3069 else mstruct_new[i].multiply(mstruct_units[i], true);
3070 }
3071 }
3072 if(b) {
3073 if(mstruct_new.size() == 1) set(mstruct_new[0], true);
3074 else set(mstruct_new);
3075 factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
3076 return true;
3077 }
3078 }
3079 if(isAddition()) {
3080 b = false;
3081 mstruct_units.set(*this);
3082 mstruct_new.set(*this);
3083 // 5x + pi*x + 5y + xy = (5 + pi)x + 5y + xy
3084 for(size_t i = 0; i < mstruct_units.size(); i++) {
3085 if(mstruct_units[i].isMultiplication()) {
3086 for(size_t i2 = 0; i2 < mstruct_units[i].size();) {
3087 if(!mstruct_units[i][i2].containsType(STRUCT_UNIT, true) && !mstruct_units[i][i2].containsUnknowns()) {
3088 mstruct_units[i].delChild(i2 + 1);
3089 } else {
3090 i2++;
3091 }
3092 }
3093 if(mstruct_units[i].size() == 0) mstruct_units[i].setUndefined();
3094 else if(mstruct_units[i].size() == 1) mstruct_units[i].setToChild(1);
3095 for(size_t i2 = 0; i2 < mstruct_new[i].size();) {
3096 if(mstruct_new[i][i2].containsType(STRUCT_UNIT, true) || mstruct_new[i][i2].containsUnknowns()) {
3097 mstruct_new[i].delChild(i2 + 1);
3098 } else {
3099 i2++;
3100 }
3101 }
3102 if(mstruct_new[i].size() == 0) mstruct_new[i].set(1, 1, 0);
3103 else if(mstruct_new[i].size() == 1) mstruct_new[i].setToChild(1);
3104 } else if(mstruct_units[i].containsType(STRUCT_UNIT, true) || mstruct_units[i].containsUnknowns()) {
3105 mstruct_new[i].set(1, 1, 0);
3106 } else {
3107 mstruct_units[i].setUndefined();
3108 }
3109 }
3110 for(size_t i = 0; i < mstruct_units.size(); i++) {
3111 if(!mstruct_units[i].isUndefined()) {
3112 for(size_t i2 = i + 1; i2 < mstruct_units.size();) {
3113 if(mstruct_units[i2] == mstruct_units[i]) {
3114 mstruct_new[i].add(mstruct_new[i2], true);
3115 mstruct_new.delChild(i2 + 1);
3116 mstruct_units.delChild(i2 + 1);
3117 b = true;
3118 } else {
3119 i2++;
3120 }
3121 }
3122 if(mstruct_new[i].isOne()) mstruct_new[i].set(mstruct_units[i]);
3123 else mstruct_new[i].multiply(mstruct_units[i], true);
3124 }
3125 }
3126 if(b) {
3127 if(mstruct_new.size() == 1) set(mstruct_new[0], true);
3128 else set(mstruct_new);
3129 factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
3130 return true;
3131 }
3132 }
3133 return b_ret;
3134 } else if(term_combination_levels != 0 && SIZE > 2) {
3135 int start_index = rand() % SIZE;
3136 int index = start_index;
3137 int best_index = -1;
3138 int run_index = 0;
3139 int max_run_index = SIZE - 3;
3140 if(term_combination_levels < -1) {
3141 run_index = -term_combination_levels - 2;
3142 max_run_index = run_index;
3143 } else if(term_combination_levels > 0 && term_combination_levels - 1 < max_run_index) {
3144 max_run_index = term_combination_levels -1;
3145 }
3146
3147 MathStructure mbest;
3148 do {
3149 if(CALCULATOR->aborted()) break;
3150 if(endtime_p && endtime_p->tv_sec > 0) {
3151 #ifndef CLOCK_MONOTONIC
3152 struct timeval curtime;
3153 gettimeofday(&curtime, NULL);
3154 if(curtime.tv_sec > endtime_p->tv_sec || (curtime.tv_sec == endtime_p->tv_sec && curtime.tv_usec > endtime_p->tv_usec)) {
3155 #else
3156 struct timespec curtime;
3157 clock_gettime(CLOCK_MONOTONIC, &curtime);
3158 if(curtime.tv_sec > endtime_p->tv_sec || (curtime.tv_sec == endtime_p->tv_sec && curtime.tv_nsec / 1000 > endtime_p->tv_usec)) {
3159 #endif
3160 CALCULATOR->error(false, _("Because of time constraints only a limited number of combinations of terms were tried during factorization. Repeat factorization to try other random combinations."), NULL);
3161 break;
3162 }
3163 }
3164
3165 MathStructure mtest(*this);
3166 mtest.delChild(index + 1);
3167 if(mtest.factorize(eo, false, run_index == 0 ? 0 : -1 - run_index, 0, only_integers, false, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree)) {
3168 bool b = best_index < 0 || (mbest.isAddition() && !mtest.isAddition());
3169 if(!b && (mtest.isAddition() == mbest.isAddition())) {
3170 b = mtest.isAddition() && (mtest.size() < mbest.size());
3171 if(!b && (!mtest.isAddition() || mtest.size() == mbest.size())) {
3172 size_t c1 = mtest.countTotalChildren() + CHILD(index).countTotalChildren();
3173 size_t c2 = mbest.countTotalChildren() + CHILD(best_index).countTotalChildren();
3174 b = (c1 < c2);
3175 if(c1 == c2) {
3176 b = (count_powers(mtest) + count_powers(CHILD(index))) < (count_powers(mbest) + count_powers(CHILD(best_index)));
3177 }
3178 }
3179 }
3180 if(b) {
3181 mbest = mtest;
3182 best_index = index;
3183 if(mbest.isPower()) {
3184 break;
3185 }
3186 }
3187 }
3188 index++;
3189 if(index == (int) SIZE) index = 0;
3190 if(index == start_index) {
3191 if(best_index >= 0) {
3192 break;
3193 }
3194 run_index++;
3195 if(run_index > max_run_index) break;
3196 }
3197 } while(true);
3198 if(best_index >= 0) {
3199 mbest.add(CHILD(best_index), true);
3200 set(mbest);
3201 if(term_combination_levels >= -1 && (run_index > 0 || recursive)) {
3202 factorize(eo, false, term_combination_levels, 0, only_integers, true, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
3203 }
3204 return true;
3205 }
3206 }
3207 }
3208 default: {
3209 if(term_combination_levels < -1) break;
3210 bool b = false;
3211
3212 if(isComparison()) {
3213 EvaluationOptions eo2 = eo;
3214 eo2.assume_denominators_nonzero = false;
3215 for(size_t i = 0; i < SIZE; i++) {
3216 if(CHILD(i).factorize(eo2, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree)) {
3217 CHILD_UPDATED(i);
3218 b = true;
3219 }
3220 }
3221 } else if(recursive && (recursive > 1 || !isAddition())) {
3222 for(size_t i = 0; i < SIZE; i++) {
3223 if(CHILD(i).factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree)) {
3224 CHILD_UPDATED(i);
3225 b = true;
3226 }
3227 }
3228 }
3229 if(b) {
3230 EvaluationOptions eo2 = eo;
3231 eo2.expand = false;
3232 calculatesub(eo2, eo2, false);
3233 evalSort(true);
3234 if(isAddition()) {
3235 for(size_t i = 0; i < SIZE; i++) {
3236 if(CHILD(i).isMultiplication() && CHILD(i).size() > 1) {
3237 for(size_t i2 = 0; i2 < CHILD(i).size(); i2++) {
3238 if(CHILD(i)[i2].isAddition()) {
3239 for(size_t i3 = i + 1; i3 < SIZE; i3++) {
3240 if(CHILD(i3).isMultiplication() && CHILD(i3).size() > 1) {
3241 for(size_t i4 = 0; i4 < CHILD(i3).size(); i4++) {
3242 if(CHILD(i3)[i4].isAddition() && CHILD(i3)[i4] == CHILD(i)[i2]) {
3243 MathStructure *mfac = &CHILD(i)[i2];
3244 mfac->ref();
3245 CHILD(i).delChild(i2 + 1, true);
3246 CHILD(i3).delChild(i4 + 1, true);
3247 CHILD(i3).ref();
3248 CHILD(i).add_nocopy(&CHILD(i3));
3249 CHILD(i).calculateAddLast(eo);
3250 CHILD(i).multiply_nocopy(mfac);
3251 CHILD_UPDATED(i)
3252 delChild(i3 + 1, true);
3253 evalSort(true);
3254 factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
3255 return true;
3256 }
3257 }
3258 }
3259 }
3260 if(SIZE > 2) {
3261 MathStructure mtest(*this);
3262 mtest.delChild(i + 1);
3263 if(mtest == CHILD(i)[i2]) {
3264 CHILD(i).delChild(i2 + 1, true);
3265 SET_CHILD_MAP(i);
3266 add(m_one, true);
3267 multiply(mtest);
3268 evalSort(true);
3269 factorize(eo, false, term_combination_levels, 0, only_integers, recursive, endtime_p, force_factorization, complete_square, only_sqrfree, max_factor_degree);
3270 return true;
3271 }
3272 }
3273 }
3274 }
3275 }
3276 }
3277 }
3278 return true;
3279 }
3280 }
3281 }
3282 return false;
3283 }
3284
3285