symbolic4
polynomial.c
Go to the documentation of this file.
1 
2 /*
3 
4  Copyright (c) 2019 Hannes Eberhard
5 
6  Permission is hereby granted, free of charge, to any person obtaining a copy
7  of this software and associated documentation files (the "Software"), to deal
8  in the Software without restriction, including without limitation the rights
9  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10  copies of the Software, and to permit persons to whom the Software is
11  furnished to do so, subject to the following conditions:
12 
13  The above copyright notice and this permission notice shall be included in all
14  copies or substantial portions of the Software.
15 
16  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22  SOFTWARE.
23 
24  */
25 
26 #include "symbolic4.h"
27 
28 return_status expression_to_sparse_polynomial(expression* source, const expression* variable);
29 void sparse_polynomial_to_expression(expression* source);
30 return_status sparse_polynomial_to_dense_polynomial(expression* source);
31 void dense_polynomial_to_sparse_polynomial(expression* source);
32 
33 void any_expression_to_expression(expression* source) {
34  if (source->identifier == EXPI_POLYNOMIAL_SPARSE) {
35  sparse_polynomial_to_expression(source);
36  } else if (source->identifier == EXPI_POLYNOMIAL_DENSE) {
37  dense_polynomial_to_sparse_polynomial(source);
38  sparse_polynomial_to_expression(source);
39  } else {
40  return;
41  }
42 }
43 
44 void any_expression_to_expression_recursive(expression* source) {
45  uint8_t i;
46  for (i = 0; i < source->child_count; i++) {
47  if (source->children[i] == NULL) continue;
48  any_expression_to_expression_recursive(source->children[i]);
49  }
50  any_expression_to_expression(source);
51 }
52 
53 return_status any_expression_to_sparse_polynomial(expression* source, const expression* variable) {
54  if (source->identifier == EXPI_POLYNOMIAL_SPARSE) {
55  sort_sparse_polynomial(source);
56  return RETS_SUCCESS;
57  } else if (source->identifier == EXPI_POLYNOMIAL_DENSE) {
58  dense_polynomial_to_sparse_polynomial(source);
59  } else {
60  ERROR_CHECK(expression_to_sparse_polynomial(source, variable));
61  }
62 
63  return RETS_SUCCESS;
64 
65 }
66 
67 return_status any_expression_to_dense_polynomial(expression* source, const expression* variable) {
68 
69  if (source->identifier == EXPI_POLYNOMIAL_SPARSE) {
70  ERROR_CHECK(sparse_polynomial_to_dense_polynomial(source));
71  } else if (source->identifier == EXPI_POLYNOMIAL_DENSE) {
72  return RETS_SUCCESS;
73  } else {
74  ERROR_CHECK(expression_to_sparse_polynomial(source, variable));
75  ERROR_CHECK(sparse_polynomial_to_dense_polynomial(source));
76  }
77 
78  return RETS_SUCCESS;
79 
80 }
81 
82 return_status validate_sparse_polynomial(expression* source, bool allow_decimal_exponents, bool allow_negative_exponents, bool allow_arbitrary_base) {
83 
84  uint8_t i;
85  expression* temp_base = NULL;
86 
87  for (i = 0; i < source->child_count; i++) {
88  if (source->children[i]->children[2] != NULL) {
89  temp_base = copy_expression(source->children[i]->children[2]);
90  break;
91  }
92  }
93 
94  if (temp_base == NULL) temp_base = new_symbol(EXPI_SYMBOL, "x");
95 
96  for (i = 0; i < source->child_count; i++) {
97 
98  if (source->children[i]->children[2] == NULL) {
99  source->children[i]->children[2] = copy_expression(temp_base);
100  }
101 
102  if (source->children[i]->children[0]->identifier == EXPI_LITERAL &&
103  source->children[i]->children[0]->value.numeric.denominator != 1 &&
104  !allow_decimal_exponents) {
105  free_expression(temp_base, false);
106  return RETS_ERROR;
107  }
108 
109  if (source->children[i]->children[0]->identifier == EXPI_LITERAL &&
110  source->children[i]->children[0]->sign == -1 &&
111  !allow_negative_exponents) {
112  free_expression(temp_base, false);
113  return RETS_ERROR;
114  }
115 
116  if (source->children[i]->children[2]->identifier != EXPI_SYMBOL && !allow_arbitrary_base) {
117  free_expression(temp_base, false);
118  return RETS_ERROR;
119  }
120 
121  if (!expressions_are_identical(source->children[i]->children[2], source->children[0]->children[2], true)) {
122  free_expression(temp_base, false);
123  return RETS_ERROR;
124  }
125 
126  }
127 
128  free_expression(temp_base, false);
129 
130  return RETS_SUCCESS;
131 
132 }
133 
134 void sort_sparse_polynomial(expression* source) {
135 
136  uint8_t i, j;
137  uint8_t hightest_exponent_index = 0;
138  double hightest_exponent_value;
139  expression* result = new_expression(EXPT_STRUCTURE, EXPI_POLYNOMIAL_SPARSE, 0);
140 
141  for (i = 0; i < source->child_count; i++) {
142 
143  hightest_exponent_value = -1000000;
144 
145  for (j = 0; j < source->child_count; j++) {
146  if (source->children[j] == NULL) continue;
147  if (literal_to_double(source->children[j]->children[0]) >= hightest_exponent_value) {
148  hightest_exponent_index = j;
149  hightest_exponent_value = literal_to_double(source->children[j]->children[0]);
150  }
151  }
152 
153  append_child(result, source->children[hightest_exponent_index]);
154  source->children[hightest_exponent_index] = NULL;
155 
156  }
157 
158  replace_expression(source, result);
159 
160 }
161 
162 void expression_to_sparse_polynomial_term(expression* source, const expression* variable) {
163 
164  uint8_t i;
165  expression* result;
166 
167  if (count_occurrences(source, copy_expression(variable), false) == 0) {
168  result = new_expression(EXPT_STRUCTURE, EXPI_LIST, 3,
169  new_literal(1, 0, 1),
170  copy_expression(source),
171  copy_expression(variable));
172  replace_expression(source, result);
173  return;
174  }
175 
176  result = new_expression(EXPT_STRUCTURE, EXPI_LIST, 3,
177  NULL,
178  NULL,
179  NULL);
180 
181  if (source->identifier == EXPI_MULTIPLICATION) {
182  result->children[1] = new_expression(EXPT_OPERATION, EXPI_MULTIPLICATION, 0);
183  for (i = 0; i < source->child_count; i++) {
184  if (source->children[i] == NULL) continue;
185  if (count_occurrences(source->children[i], copy_expression(variable), false) == 0) {
186  append_child(result->children[1], source->children[i]);
187  source->children[i] = NULL;
188  }
189  }
190  simplify(source, true);
191  simplify(result->children[1], true);
192  } else {
193  result->children[1] = new_literal(1, 1, 1);
194  }
195 
196  if (source->identifier == EXPI_EXPONENTATION) {
197  result->children[0] = copy_expression(source->children[1]);
198  result->children[2] = copy_expression(source->children[0]);
199  } else {
200  result->children[0] = new_literal(1, 1, 1);
201  result->children[2] = copy_expression(source);
202  }
203 
204  replace_expression(source, result);
205 
206 }
207 
208 return_status expression_to_sparse_polynomial(expression* source, const expression* variable) {
209 
210  uint8_t i;
211  expression* temp_source = copy_expression(source);
212  expression* temp_variable;
213  expression* result;
214 
215  if (variable == NULL) {
216  temp_variable = guess_symbol(source, "", 0);
217  if (temp_variable == NULL) {
218  temp_variable = new_symbol(EXPI_SYMBOL, "x");
219  }
220  } else {
221  temp_variable = copy_expression(variable);
222  }
223 
224  result = new_expression(EXPT_STRUCTURE, EXPI_POLYNOMIAL_SPARSE, 0);
225 
226  if (temp_source->identifier == EXPI_ADDITION) {
227  for (i = 0; i < temp_source->child_count; i++) {
228  if (temp_source->children[i] == NULL) continue;
229  expression_to_sparse_polynomial_term(temp_source->children[i], temp_variable);
230  append_child(result, copy_expression(temp_source->children[i]));
231  }
232  } else {
233  simplify(temp_source, true);
234  expression_to_sparse_polynomial_term(temp_source, temp_variable);
235  append_child(result, copy_expression(temp_source));
236  }
237 
238  free_expression(temp_source, false);
239 
240  if (validate_sparse_polynomial(result, true, true, true) == RETS_ERROR) {
241  free_expression(result, false);
242  free_expression(temp_variable, false);
243  return RETS_ERROR;
244  } else {
245  sort_sparse_polynomial(result);
246  replace_expression(source, result);
247  free_expression(temp_variable, false);
248  return RETS_SUCCESS;
249  }
250 
251 }
252 
253 void sparse_polynomial_to_expression(expression* source) {
254 
255  uint8_t i;
256  expression* result = new_expression(EXPT_OPERATION, EXPI_ADDITION, 0);
257 
258  for (i = 0; i < source->child_count; i++) {
259  append_child(result, new_expression(EXPT_OPERATION, EXPI_MULTIPLICATION, 2,
260  copy_expression(source->children[i]->children[1]),
261  new_expression(EXPT_OPERATION, EXPI_EXPONENTATION, 2,
262  copy_expression(source->children[i]->children[2]),
263  copy_expression(source->children[i]->children[0]))));
264  }
265 
266  simplify(result, true);
267  replace_expression(source, result);
268 
269 }
270 
271 return_status sparse_polynomial_to_dense_polynomial(expression* source) {
272 
273  uint8_t i;
274  expression* result = new_expression(EXPT_STRUCTURE, EXPI_POLYNOMIAL_DENSE, 2,
275  copy_expression(source->children[0]->children[2]),
276  new_expression(EXPT_STRUCTURE, EXPI_LIST, 0));
277 
278  for (i = 0; i < source->child_count; i++) {
279  if (source->children[i]->children[0]->identifier != EXPI_LITERAL &&
280  source->children[i]->children[0]->value.numeric.denominator != 1) {
281  free_expression(result, false);
282  return RETS_ERROR;
283  }
284  }
285 
286  for (i = 0; i < source->children[0]->children[0]->value.numeric.numerator + 1; i++) {
287  append_child(result->children[1], new_literal(1, 0, 1));
288  }
289 
290  for (i = 0; i < source->child_count; i++) {
291  replace_expression(result->children[1]->children[source->children[i]->children[0]->value.numeric.numerator], copy_expression(source->children[i]->children[1]));
292  }
293 
294  replace_expression(source, result);
295 
296  return RETS_SUCCESS;
297 
298 }
299 
300 void dense_polynomial_to_sparse_polynomial(expression* source) {
301 
302  uint8_t i;
303  expression* result = new_expression(EXPT_STRUCTURE, EXPI_POLYNOMIAL_SPARSE, 0);
304 
305  for (i = 0; i < source->children[1]->child_count; i++) {
306  if (source->children[1]->children[i] == 0) continue;
307  if (source->children[1]->children[i]->value.numeric.numerator != 0) {
308  append_child(result, new_expression(EXPT_STRUCTURE, EXPI_LIST, 3,
309  new_literal(1, i, 1),
310  copy_expression(source->children[1]->children[i]),
311  copy_expression(source->children[0])));
312  }
313  }
314 
315  sort_sparse_polynomial(result);
316  replace_expression(source, result);
317 
318 }
319 
320 void quadratic_formula(expression** result, expression* a, expression* b, expression* c) {
321 
322  expression* discriminant;
323  expression* divisor;
324 
325  discriminant = new_expression(EXPT_OPERATION, EXPI_ADDITION, 2,
326  new_expression(EXPT_OPERATION, EXPI_EXPONENTATION, 2,
327  copy_expression(b),
328  new_literal(1, 2, 1)),
329  new_expression(EXPT_OPERATION, EXPI_MULTIPLICATION, 3,
330  new_literal(-1, 4, 1),
331  copy_expression(a),
332  copy_expression(c)));
333 
334  simplify(discriminant, true);
335 
336  divisor = new_expression(EXPT_OPERATION, EXPI_MULTIPLICATION, 2,
337  new_literal(1, 2, 1),
338  copy_expression(a));
339 
340  simplify(discriminant, true);
341 
342  if (discriminant->identifier == EXPI_LITERAL && discriminant->value.numeric.numerator == 0) {
343 
344  *result = new_expression(EXPT_STRUCTURE, EXPI_LIST, 1,
345  new_expression(EXPT_OPERATION, EXPI_DIVISION, 2,
346  new_expression(EXPT_OPERATION, EXPI_MULTIPLICATION, 2,
347  new_literal(-1, 1, 1),
348  copy_expression(b)),
349  copy_expression(divisor)));
350 
351  simplify(*result, true);
352 
353  } else {
354 
355  discriminant = new_expression(EXPT_OPERATION, EXPI_EXPONENTATION, 2,
356  discriminant,
357  new_literal(1, 1, 2));
358 
359  simplify(discriminant, true);
360 
361  (*result) = new_expression(EXPT_STRUCTURE, EXPI_LIST, 2,
362  new_expression(EXPT_OPERATION, EXPI_DIVISION, 2,
363  new_expression(EXPT_OPERATION, EXPI_ADDITION, 2,
364  new_expression(EXPT_OPERATION, EXPI_MULTIPLICATION, 2,
365  copy_expression(b),
366  new_literal(-1, 1, 1)),
367  copy_expression(discriminant)),
368  copy_expression(divisor)),
369  new_expression(EXPT_OPERATION, EXPI_DIVISION, 2,
370  new_expression(EXPT_OPERATION, EXPI_SUBTRACTION, 2,
371  new_expression(EXPT_OPERATION, EXPI_MULTIPLICATION, 2,
372  copy_expression(b),
373  new_literal(-1, 1, 1)),
374  copy_expression(discriminant)),
375  copy_expression(divisor)));
376 
377  simplify(*result, true);
378 
379  }
380 
381 }
382 
383 return_status polysolve_quadratic(expression* source) {
384 
385  uint8_t i;
386  expression* temp_source = copy_expression(source->children[0]);
387  expression* temp;
388  expression* result;
389 
390  if (temp_source->child_count > 3) {
391  return RETS_ERROR;
392  }
393 
394  if (temp_source->child_count == 2) {
395  append_child(temp_source, new_expression(EXPT_STRUCTURE, EXPI_LIST, 3,
396  new_literal(1, 0, 1),
397  new_literal(1, 0, 1),
398  copy_expression(temp_source->children[0]->children[2])));
399  }
400 
401  temp = new_expression(EXPT_OPERATION, EXPI_DIVISION, 2,
402  copy_expression(temp_source->children[0]->children[0]),
403  copy_expression(temp_source->children[1]->children[0]));
404 
405  simplify(temp, true);
406 
407  if (temp->sign != 1) return RETS_ERROR;
408  if (literal_to_double(temp) != 2) return RETS_ERROR;
409 
410  free_expression(temp, true);
411 
412  quadratic_formula(&result, temp_source->children[0]->children[1], temp_source->children[1]->children[1], temp_source->children[2]->children[1]);
413 
414  temp = new_expression(EXPT_OPERATION, EXPI_EXPONENTATION, 2,
415  copy_expression(temp_source->children[1]->children[2]),
416  copy_expression(temp_source->children[1]->children[0]));
417 
418  simplify(temp, true);
419 
420  for (i = 0; i < result->child_count; i++) {
421 
422  replace_expression(result->children[i], new_expression(EXPT_OPERATION, EXPI_EQUATION, 2,
423  copy_expression(temp),
424  copy_expression(result->children[i])));
425 
426  if (temp->identifier != EXPI_SYMBOL) {
427  solve(result->children[i], NULL);
428  }
429 
430  }
431 
432  free_expression(temp_source, true);
433  free_expression(temp, true);
434  replace_expression(source, result);
435 
436  return RETS_SUCCESS;
437 
438 }
439 
440 return_status polysolve(expression* source, expression* variable) {
441 
442  expression* temp_source;
443 
444  if (variable == NULL) {
445  variable = guess_symbol(source, "", 0);
446  }
447 
448  subtract_rhs(source);
449  temp_source = copy_expression(source);
450 
451  if (expression_to_sparse_polynomial(temp_source->children[0], variable) == RETS_ERROR) {
452  free_expression(temp_source, false);
453  return RETS_ERROR;
454  }
455 
456  if (polysolve_quadratic(temp_source) == RETS_ERROR) {
457  free_expression(temp_source, false);
458  return RETS_ERROR;
459  }
460 
461  replace_expression(source, temp_source);
462 
463  return RETS_ERROR;
464 
465 }
466 
467 uint8_t poly_div(expression** quotient, expression** remainder, const expression* a, const expression* b, int8_t degree) {
468 
469  expression* symbol;
470  expression* a_temp = copy_expression(a);
471  expression* b_temp = copy_expression(b);
472  uint8_t a_degree;
473  uint8_t b_degree;
474  uint8_t power;
475  expression* coefficient;
476  expression* monomial;
477  expression* result;
478  expression* temp_quotient;
479  expression* temp_remainder;
480 
481  symbol = get_symbol(a);
482 
483  simplify(a_temp, true);
484  simplify(b_temp, true);
485 
486  if (any_expression_to_sparse_polynomial(a_temp, symbol) == RETS_ERROR ||
487  any_expression_to_sparse_polynomial(b_temp, symbol) == RETS_ERROR ||
488  validate_sparse_polynomial(a_temp, false, false, true) == RETS_ERROR ||
489  validate_sparse_polynomial(b_temp, false, false, false) == RETS_ERROR) {
490  free_expressions(3, symbol, a_temp, b_temp);
491  return RETS_ERROR;
492  }
493 
494  a_degree = (degree == -1) ? a_temp->children[0]->children[0]->value.numeric.numerator : degree;
495  b_degree = b_temp->children[0]->children[0]->value.numeric.numerator;
496 
497  if (a_degree < b_degree) {
498  if (quotient != NULL) *quotient = new_literal(1, 0, 1);
499  if (remainder != NULL) *remainder = copy_expression(a_temp);
500  free_expressions(3, symbol, a_temp, b_temp);
501  return RETS_SUCCESS;
502  }
503 
504  power = a_degree - b_degree;
505 
506  coefficient = new_expression(EXPT_OPERATION, EXPI_DIVISION, 2,
507  (a_temp->children[0]->children[0]->value.numeric.numerator == a_degree) ? copy_expression(a_temp->children[0]->children[1]) : new_literal(1, 0, 1),
508  copy_expression(b_temp->children[0]->children[1]));
509  simplify(coefficient, true);
510 
511  monomial = new_expression(EXPT_STRUCTURE, EXPI_POLYNOMIAL_SPARSE, 1,
512  new_expression(EXPT_STRUCTURE, EXPI_LIST, 3,
513  new_literal(1, power, 1),
514  coefficient,
515  copy_expression(symbol)));
516 
517  result = new_expression(EXPT_OPERATION, EXPI_SUBTRACTION, 2,
518  copy_expression(a),
519  new_expression(EXPT_OPERATION, EXPI_MULTIPLICATION, 2,
520  copy_expression(monomial),
521  copy_expression(b)));
522  simplify(result, true);
523 
524  if (any_expression_to_sparse_polynomial(result, symbol) == RETS_ERROR) {
525  free_expressions(5, symbol, a_temp, b_temp, monomial, result);
526  return RETS_ERROR;
527  }
528 
529  if (expressions_are_equivalent(result, new_literal(1, 0, 1), false)) {
530 
531  if (quotient != NULL) *quotient = copy_expression(monomial);
532  if (remainder != NULL) *remainder = new_literal(1, 0, 1);
533 
534  } else {
535 
536  poly_div(&temp_quotient, &temp_remainder, result, b_temp, a_degree - 1);
537 
538  replace_expression(temp_quotient, new_expression(EXPT_OPERATION, EXPI_ADDITION, 2,
539  copy_expression(temp_quotient),
540  copy_expression(monomial)));
541  simplify(temp_quotient, true);
542 
543  if (any_expression_to_sparse_polynomial(temp_quotient, symbol) == RETS_ERROR ||
544  any_expression_to_sparse_polynomial(temp_remainder, symbol) == RETS_ERROR) {
545  return RETS_ERROR;
546  }
547 
548  if (quotient != NULL) *quotient = copy_expression(temp_quotient);
549  if (remainder != NULL) *remainder = copy_expression(temp_remainder);
550  free_expressions(2, temp_quotient, temp_remainder);
551 
552  }
553 
554  free_expressions(5, symbol, a_temp, b_temp, monomial, result);
555 
556  return RETS_SUCCESS;
557 
558 }
559 
560 bool poly_is_square_free(expression* source) {
561 
562  expression* gcd;
563  expression* temp_source = copy_expression(source);
564 
565  simplify(temp_source, true);
566  any_expression_to_sparse_polynomial(temp_source, NULL);
567 
568  poly_log_gcd(&gcd, temp_source);
569 
570  free_expression(temp_source, true);
571 
572  if (expressions_are_equivalent(gcd, new_literal(1, 1, 1), false)) {
573  return true;
574  } else {
575  return false;
576  }
577 
578 }
579 
580 void make_monic(expression* source) {
581 
582  uint8_t i;
583  expression* result;
584 
585  any_expression_to_sparse_polynomial(source, NULL);
586 
587  result = new_expression(EXPT_STRUCTURE, EXPI_POLYNOMIAL_SPARSE, 0);
588 
589  for (i = 0; i < source->child_count; i++) {
590  append_child(result, new_expression(EXPT_STRUCTURE, EXPI_LIST, 3,
591  copy_expression(source->children[i]->children[0]),
592  new_expression(EXPT_OPERATION, EXPI_DIVISION, 2,
593  copy_expression(source->children[i]->children[1]),
594  copy_expression(source->children[0]->children[1])),
595  copy_expression(source->children[i]->children[2])));
596  }
597 
598  simplify(result, true);
599  replace_expression(source, result);
600 
601 }
602 
603 uint8_t poly_gcd(expression** gcd, const expression* a, const expression* b) {
604 
605  expression* symbol;
606  expression* a_temp;
607  expression* b_temp;
608  expression* temp;
609  expression* quotient;
610  expression* remainder;
611 
612  if (expressions_are_equivalent(a, new_literal(1, 0, 1), false)) {
613  *gcd = copy_expression(b);
614  return RETS_SUCCESS;
615  }
616 
617  if (expressions_are_equivalent(b, new_literal(1, 0, 1), false)) {
618  *gcd = copy_expression(a);
619  return RETS_SUCCESS;
620  }
621 
622  a_temp = copy_expression(a);
623  b_temp = copy_expression(b);
624 
625  simplify(a_temp, true);
626  simplify(b_temp, true);
627 
628  symbol = get_symbol(a_temp);
629 
630  if (any_expression_to_sparse_polynomial(a_temp, symbol) == RETS_ERROR ||
631  any_expression_to_sparse_polynomial(b_temp, symbol) == RETS_ERROR ||
632  validate_sparse_polynomial(a_temp, false, false, true) == RETS_ERROR ||
633  validate_sparse_polynomial(b_temp, false, false, false) == RETS_ERROR) {
634  free_expressions(3, symbol, a_temp, b_temp);
635  return RETS_ERROR;
636  }
637 
638  sort_sparse_polynomial(a_temp);
639  sort_sparse_polynomial(b_temp);
640 
641  if (expression_is_greater_than(b_temp->children[0]->children[0], a_temp->children[0]->children[0], true)) {
642  temp = a_temp;
643  a_temp = b_temp;
644  b_temp = temp;
645  }
646 
647  poly_div(&quotient, &remainder, a_temp, b_temp, -1);
648 
649  if (expressions_are_equivalent(remainder, new_literal(1, 0, 1), false)) {
650  *gcd = copy_expression(b_temp);
651  } else {
652  poly_gcd(gcd, b_temp, remainder);
653  }
654 
655  free_expressions(5, symbol, a_temp, b_temp, quotient, remainder);
656 
657  make_monic(*gcd);
658 
659  return RETS_SUCCESS;
660 
661 }
662 
663 void poly_log_gcd(expression** gcd, const expression* source) {
664 
665  expression* symbol = get_symbol(source);
666  expression* a = copy_expression(source);
667  expression* a_derivative;
668 
669  any_expression_to_sparse_polynomial(a, symbol);
670  derivative(&a_derivative, copy_expression(a), copy_expression(symbol), false);
671 
672  any_expression_to_sparse_polynomial(a_derivative, symbol);
673 
674  poly_gcd(gcd, a, a_derivative);
675 
676  free_expressions(3, symbol, a, a_derivative);
677 
678 }
679 
680 uint8_t factor_square_free(expression** factors, const expression* source) {
681 
682  uint8_t i = 1;
683  expression* symbol = get_symbol(source);
684  expression* a = copy_expression(source);
685  expression* b = NULL;
686  expression* c = NULL;
687  expression* g = NULL;
688  expression* w = NULL;
689  expression* y = NULL;
690  expression* z = NULL;
691  expression* temp;
692 
693  *factors = new_expression(EXPT_STRUCTURE, EXPI_LIST, 0);
694 
695  derivative(&b, a, symbol, true);
696  poly_log_gcd(&c, a);
697 
698  if (expressions_are_equivalent(c, new_literal(1, 1, 1), false)) {
699 
700  w = copy_expression(a);
701 
702  } else {
703 
704  poly_div(&w, NULL, a, c, -1);
705  poly_div(&y, NULL, b, c, -1);
706 
707  derivative(&temp, w, symbol, true);
708  z = new_expression(EXPT_OPERATION, EXPI_SUBTRACTION, 2,
709  copy_expression(y),
710  temp);
711  simplify(z, true);
712 
713  while (!expressions_are_equivalent(z, new_literal(1, 0, 1), false)) {
714 
715  free_expression(g, false);
716  poly_gcd(&g, w, z);
717 
718  if (!expressions_are_equivalent(g, new_literal(1, 1, 1), false)) {
719  append_child(*factors, new_expression(EXPT_STRUCTURE, EXPI_LIST, 2,
720  copy_expression(g),
721  new_literal(1, i, 1)));
722  }
723 
724  temp = copy_expression(w);
725  free_expression(w, false);
726  poly_div(&w, NULL, temp, g, -1);
727  free_expression(temp, false);
728 
729  free_expression(y, false);
730  poly_div(&y, NULL, z, g, -1);
731 
732  derivative(&temp, w, symbol, true);
733  free_expression(z, false);
734  z = new_expression(EXPT_OPERATION, EXPI_SUBTRACTION, 2,
735  copy_expression(y),
736  copy_expression(temp));
737  free_expression(temp, false);
738  simplify(z, true);
739 
740  i++;
741 
742  }
743 
744  }
745 
746  append_child(*factors, new_expression(EXPT_STRUCTURE, EXPI_LIST, 2,
747  copy_expression(w),
748  new_literal(1, i, 1)));
749 
750  free_expressions(8, symbol, a, b, c, g, w, y, z);
751 
752  return RETS_SUCCESS;
753 
754 }
make_monic
void make_monic(expression *source)
Definition: polynomial.c:580
EXPI_LIST
Definition: expression.h:90
numeric_value::denominator
uintmax_t denominator
Definition: expression.h:109
symbolic4.h
EXPI_EXPONENTATION
Definition: expression.h:53
expression_to_sparse_polynomial
return_status expression_to_sparse_polynomial(expression *source, const expression *variable)
Definition: polynomial.c:208
EXPI_POLYNOMIAL_DENSE
Definition: expression.h:89
EXPI_SYMBOL
Definition: expression.h:45
derivative
uint8_t derivative(expression **result, expression *source, expression *variable, bool persistent)
Definition: derivative.c:209
replace_expression
void replace_expression(expression *a, expression *b)
Definition: expression.c:309
expression
Definition: expression.h:112
expression::identifier
expression_identifier identifier
Definition: expression.h:115
sparse_polynomial_to_dense_polynomial
return_status sparse_polynomial_to_dense_polynomial(expression *source)
Definition: polynomial.c:271
literal_to_double
double literal_to_double(expression *source)
Definition: expression.c:908
any_expression_to_dense_polynomial
return_status any_expression_to_dense_polynomial(expression *source, const expression *variable)
Definition: polynomial.c:67
EXPT_STRUCTURE
Definition: expression.h:36
validate_sparse_polynomial
return_status validate_sparse_polynomial(expression *source, bool allow_decimal_exponents, bool allow_negative_exponents, bool allow_arbitrary_base)
Definition: polynomial.c:82
expression::sign
int8_t sign
Definition: expression.h:117
subtract_rhs
void subtract_rhs(expression *source)
Definition: solve.c:46
ERROR_CHECK
#define ERROR_CHECK(F)
Check if the return status of a function is RETS_ERROR. If so, return RETS_ERROR.
Definition: foundation.h:31
new_symbol
expression * new_symbol(expression_identifier identifier, const char *value)
Allocates and initializes a new symbol/variable expression.
Definition: expression.c:252
get_symbol
expression * get_symbol(const expression *source)
Definition: expression.c:878
expression::value
union expression::@0 value
solve
uint8_t solve(expression *source, expression *variable)
Definition: solve.c:337
sort_sparse_polynomial
void sort_sparse_polynomial(expression *source)
Definition: polynomial.c:134
RETS_SUCCESS
Definition: foundation.h:67
poly_is_square_free
bool poly_is_square_free(expression *source)
Definition: polynomial.c:560
expressions_are_identical
bool expressions_are_identical(const expression *a, expression *b, bool persistent)
Definition: expression.c:467
RETS_ERROR
Definition: foundation.h:66
free_expression
void free_expression(expression *source, bool persistent)
Definition: expression.c:315
polysolve_quadratic
return_status polysolve_quadratic(expression *source)
Definition: polynomial.c:383
EXPI_MULTIPLICATION
Definition: expression.h:51
dense_polynomial_to_sparse_polynomial
void dense_polynomial_to_sparse_polynomial(expression *source)
Definition: polynomial.c:300
EXPI_POLYNOMIAL_SPARSE
Definition: expression.h:88
free_expressions
void free_expressions(uint8_t expression_count,...)
Definition: expression.c:338
count_occurrences
uint8_t count_occurrences(const expression *haystack, expression *needle, bool persistent)
Definition: expression.c:664
any_expression_to_sparse_polynomial
return_status any_expression_to_sparse_polynomial(expression *source, const expression *variable)
Definition: polynomial.c:53
EXPT_OPERATION
Definition: expression.h:34
any_expression_to_expression
void any_expression_to_expression(expression *source)
Definition: polynomial.c:33
expression::numeric
numeric_value numeric
Definition: expression.h:129
poly_log_gcd
void poly_log_gcd(expression **gcd, const expression *source)
Definition: polynomial.c:663
copy_expression
expression * copy_expression(const expression *source)
Returns a deep copy of an expression.
Definition: expression.c:286
EXPI_SUBTRACTION
Definition: expression.h:50
quadratic_formula
void quadratic_formula(expression **result, expression *a, expression *b, expression *c)
Definition: polynomial.c:320
sparse_polynomial_to_expression
void sparse_polynomial_to_expression(expression *source)
Definition: polynomial.c:253
poly_gcd
uint8_t poly_gcd(expression **gcd, const expression *a, const expression *b)
Definition: polynomial.c:603
poly_div
uint8_t poly_div(expression **quotient, expression **remainder, const expression *a, const expression *b, int8_t degree)
Definition: polynomial.c:467
expression_to_sparse_polynomial_term
void expression_to_sparse_polynomial_term(expression *source, const expression *variable)
Definition: polynomial.c:162
simplify
uint8_t simplify(expression *source, bool recursive)
Definition: simplify.c:1117
any_expression_to_expression_recursive
void any_expression_to_expression_recursive(expression *source)
Definition: polynomial.c:44
append_child
void append_child(expression *parent, expression *child)
Appends a child to an expression.
Definition: expression.c:383
new_expression
expression * new_expression(expression_type type, expression_identifier identifier, uint8_t child_count,...)
Allocates and initializes a new expression with the arguments provided.
Definition: expression.c:183
expression_is_greater_than
bool expression_is_greater_than(const expression *a, expression *b, bool persistent)
Definition: expression.c:547
EXPI_EQUATION
Definition: expression.h:48
guess_symbol
expression * guess_symbol(const expression *source, const char *custom_priorities, uint8_t rank)
Definition: expression.c:830
new_literal
expression * new_literal(int8_t sign, uintmax_t numerator, uintmax_t denominator)
Allocates and initializes a new literal expression.
Definition: expression.c:225
EXPI_ADDITION
Definition: expression.h:49
return_status
return_status
Definition: foundation.h:64
factor_square_free
uint8_t factor_square_free(expression **factors, const expression *source)
Definition: polynomial.c:680
expressions_are_equivalent
bool expressions_are_equivalent(const expression *a, expression *b, bool persistent)
Definition: expression.c:526
expression::child_count
uint8_t child_count
Definition: expression.h:119
expression::children
struct expression ** children
Definition: expression.h:124
polysolve
return_status polysolve(expression *source, expression *variable)
Definition: polynomial.c:440
numeric_value::numerator
uintmax_t numerator
Definition: expression.h:108
EXPI_DIVISION
Definition: expression.h:52
EXPI_LITERAL
Definition: expression.h:44