]> www.ginac.de Git - ginac.git/blob - ginac/pseries.cpp
Move ctors for classes matrix and pseries.
[ginac.git] / ginac / pseries.cpp
1 /** @file pseries.cpp
2  *
3  *  Implementation of class for extended truncated power series and
4  *  methods for series expansion. */
5
6 /*
7  *  GiNaC Copyright (C) 1999-2015 Johannes Gutenberg University Mainz, Germany
8  *
9  *  This program is free software; you can redistribute it and/or modify
10  *  it under the terms of the GNU General Public License as published by
11  *  the Free Software Foundation; either version 2 of the License, or
12  *  (at your option) any later version.
13  *
14  *  This program is distributed in the hope that it will be useful,
15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  *  GNU General Public License for more details.
18  *
19  *  You should have received a copy of the GNU General Public License
20  *  along with this program; if not, write to the Free Software
21  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
22  */
23
24 #include "pseries.h"
25 #include "add.h"
26 #include "inifcns.h" // for Order function
27 #include "lst.h"
28 #include "mul.h"
29 #include "power.h"
30 #include "relational.h"
31 #include "operators.h"
32 #include "symbol.h"
33 #include "integral.h"
34 #include "archive.h"
35 #include "utils.h"
36
37 #include <limits>
38 #include <numeric>
39 #include <stdexcept>
40
41 namespace GiNaC {
42
43 GINAC_IMPLEMENT_REGISTERED_CLASS_OPT(pseries, basic,
44   print_func<print_context>(&pseries::do_print).
45   print_func<print_latex>(&pseries::do_print_latex).
46   print_func<print_tree>(&pseries::do_print_tree).
47   print_func<print_python>(&pseries::do_print_python).
48   print_func<print_python_repr>(&pseries::do_print_python_repr))
49
50
51 /*
52  *  Default constructor
53  */
54
55 pseries::pseries() { }
56
57
58 /*
59  *  Other ctors
60  */
61
62 /** Construct pseries from a vector of coefficients and powers.
63  *  expair.rest holds the coefficient, expair.coeff holds the power.
64  *  The powers must be integers (positive or negative) and in ascending order;
65  *  the last coefficient can be Order(_ex1) to represent a truncated,
66  *  non-terminating series.
67  *
68  *  @param rel_  expansion variable and point (must hold a relational)
69  *  @param ops_  vector of {coefficient, power} pairs (coefficient must not be zero)
70  *  @return newly constructed pseries */
71 pseries::pseries(const ex &rel_, const epvector &ops_)
72   : seq(ops_)
73 {
74         GINAC_ASSERT(is_a<relational>(rel_));
75         GINAC_ASSERT(is_a<symbol>(rel_.lhs()));
76         point = rel_.rhs();
77         var = rel_.lhs();
78 }
79 pseries::pseries(const ex &rel_, epvector &&ops_)
80   : seq(std::move(ops_))
81 {
82         GINAC_ASSERT(is_a<relational>(rel_));
83         GINAC_ASSERT(is_a<symbol>(rel_.lhs()));
84         point = rel_.rhs();
85         var = rel_.lhs();
86 }
87
88
89 /*
90  *  Archiving
91  */
92
93 void pseries::read_archive(const archive_node &n, lst &sym_lst) 
94 {
95         inherited::read_archive(n, sym_lst);
96         auto first = n.find_first("coeff");
97         auto last = n.find_last("power");
98         ++last;
99         seq.reserve((last-first)/2);
100
101         for (auto loc = first; loc < last;) {
102                 ex rest;
103                 ex coeff;
104                 n.find_ex_by_loc(loc++, rest, sym_lst);
105                 n.find_ex_by_loc(loc++, coeff, sym_lst);
106                 seq.push_back(expair(rest, coeff));
107         }
108
109         n.find_ex("var", var, sym_lst);
110         n.find_ex("point", point, sym_lst);
111 }
112
113 void pseries::archive(archive_node &n) const
114 {
115         inherited::archive(n);
116         for (auto & it : seq) {
117                 n.add_ex("coeff", it.rest);
118                 n.add_ex("power", it.coeff);
119         }
120         n.add_ex("var", var);
121         n.add_ex("point", point);
122 }
123
124
125 //////////
126 // functions overriding virtual functions from base classes
127 //////////
128
129 void pseries::print_series(const print_context & c, const char *openbrace, const char *closebrace, const char *mul_sym, const char *pow_sym, unsigned level) const
130 {
131         if (precedence() <= level)
132                 c.s << '(';
133                 
134         // objects of type pseries must not have any zero entries, so the
135         // trivial (zero) pseries needs a special treatment here:
136         if (seq.empty())
137                 c.s << '0';
138
139         auto i = seq.begin(), end = seq.end();
140         while (i != end) {
141
142                 // print a sign, if needed
143                 if (i != seq.begin())
144                         c.s << '+';
145
146                 if (!is_order_function(i->rest)) {
147
148                         // print 'rest', i.e. the expansion coefficient
149                         if (i->rest.info(info_flags::numeric) &&
150                                 i->rest.info(info_flags::positive)) {
151                                 i->rest.print(c);
152                         } else {
153                                 c.s << openbrace << '(';
154                                 i->rest.print(c);
155                                 c.s << ')' << closebrace;
156                         }
157
158                         // print 'coeff', something like (x-1)^42
159                         if (!i->coeff.is_zero()) {
160                                 c.s << mul_sym;
161                                 if (!point.is_zero()) {
162                                         c.s << openbrace << '(';
163                                         (var-point).print(c);
164                                         c.s << ')' << closebrace;
165                                 } else
166                                         var.print(c);
167                                 if (i->coeff.compare(_ex1)) {
168                                         c.s << pow_sym;
169                                         c.s << openbrace;
170                                         if (i->coeff.info(info_flags::negative)) {
171                                                 c.s << '(';
172                                                 i->coeff.print(c);
173                                                 c.s << ')';
174                                         } else
175                                                 i->coeff.print(c);
176                                         c.s << closebrace;
177                                 }
178                         }
179                 } else
180                         Order(power(var-point,i->coeff)).print(c);
181                 ++i;
182         }
183
184         if (precedence() <= level)
185                 c.s << ')';
186 }
187
188 void pseries::do_print(const print_context & c, unsigned level) const
189 {
190         print_series(c, "", "", "*", "^", level);
191 }
192
193 void pseries::do_print_latex(const print_latex & c, unsigned level) const
194 {
195         print_series(c, "{", "}", " ", "^", level);
196 }
197
198 void pseries::do_print_python(const print_python & c, unsigned level) const
199 {
200         print_series(c, "", "", "*", "**", level);
201 }
202
203 void pseries::do_print_tree(const print_tree & c, unsigned level) const
204 {
205         c.s << std::string(level, ' ') << class_name() << " @" << this
206             << std::hex << ", hash=0x" << hashvalue << ", flags=0x" << flags << std::dec
207             << std::endl;
208         size_t num = seq.size();
209         for (size_t i=0; i<num; ++i) {
210                 seq[i].rest.print(c, level + c.delta_indent);
211                 seq[i].coeff.print(c, level + c.delta_indent);
212                 c.s << std::string(level + c.delta_indent, ' ') << "-----" << std::endl;
213         }
214         var.print(c, level + c.delta_indent);
215         point.print(c, level + c.delta_indent);
216 }
217
218 void pseries::do_print_python_repr(const print_python_repr & c, unsigned level) const
219 {
220         c.s << class_name() << "(relational(";
221         var.print(c);
222         c.s << ',';
223         point.print(c);
224         c.s << "),[";
225         size_t num = seq.size();
226         for (size_t i=0; i<num; ++i) {
227                 if (i)
228                         c.s << ',';
229                 c.s << '(';
230                 seq[i].rest.print(c);
231                 c.s << ',';
232                 seq[i].coeff.print(c);
233                 c.s << ')';
234         }
235         c.s << "])";
236 }
237
238 int pseries::compare_same_type(const basic & other) const
239 {
240         GINAC_ASSERT(is_a<pseries>(other));
241         const pseries &o = static_cast<const pseries &>(other);
242         
243         // first compare the lengths of the series...
244         if (seq.size()>o.seq.size())
245                 return 1;
246         if (seq.size()<o.seq.size())
247                 return -1;
248         
249         // ...then the expansion point...
250         int cmpval = var.compare(o.var);
251         if (cmpval)
252                 return cmpval;
253         cmpval = point.compare(o.point);
254         if (cmpval)
255                 return cmpval;
256         
257         // ...and if that failed the individual elements
258         epvector::const_iterator it = seq.begin(), o_it = o.seq.begin();
259         while (it!=seq.end() && o_it!=o.seq.end()) {
260                 cmpval = it->compare(*o_it);
261                 if (cmpval)
262                         return cmpval;
263                 ++it;
264                 ++o_it;
265         }
266
267         // so they are equal.
268         return 0;
269 }
270
271 /** Return the number of operands including a possible order term. */
272 size_t pseries::nops() const
273 {
274         return seq.size();
275 }
276
277 /** Return the ith term in the series when represented as a sum. */
278 ex pseries::op(size_t i) const
279 {
280         if (i >= seq.size())
281                 throw (std::out_of_range("op() out of range"));
282
283         if (is_order_function(seq[i].rest))
284                 return Order(power(var-point, seq[i].coeff));
285         return seq[i].rest * power(var - point, seq[i].coeff);
286 }
287
288 /** Return degree of highest power of the series.  This is usually the exponent
289  *  of the Order term.  If s is not the expansion variable of the series, the
290  *  series is examined termwise. */
291 int pseries::degree(const ex &s) const
292 {
293         if (var.is_equal(s)) {
294                 // Return last exponent
295                 if (seq.size())
296                         return ex_to<numeric>((seq.end()-1)->coeff).to_int();
297                 else
298                         return 0;
299         } else {
300                 epvector::const_iterator it = seq.begin(), itend = seq.end();
301                 if (it == itend)
302                         return 0;
303                 int max_pow = std::numeric_limits<int>::min();
304                 while (it != itend) {
305                         int pow = it->rest.degree(s);
306                         if (pow > max_pow)
307                                 max_pow = pow;
308                         ++it;
309                 }
310                 return max_pow;
311         }
312 }
313
314 /** Return degree of lowest power of the series.  This is usually the exponent
315  *  of the leading term.  If s is not the expansion variable of the series, the
316  *  series is examined termwise.  If s is the expansion variable but the
317  *  expansion point is not zero the series is not expanded to find the degree.
318  *  I.e.: (1-x) + (1-x)^2 + Order((1-x)^3) has ldegree(x) 1, not 0. */
319 int pseries::ldegree(const ex &s) const
320 {
321         if (var.is_equal(s)) {
322                 // Return first exponent
323                 if (seq.size())
324                         return ex_to<numeric>((seq.begin())->coeff).to_int();
325                 else
326                         return 0;
327         } else {
328                 epvector::const_iterator it = seq.begin(), itend = seq.end();
329                 if (it == itend)
330                         return 0;
331                 int min_pow = std::numeric_limits<int>::max();
332                 while (it != itend) {
333                         int pow = it->rest.ldegree(s);
334                         if (pow < min_pow)
335                                 min_pow = pow;
336                         ++it;
337                 }
338                 return min_pow;
339         }
340 }
341
342 /** Return coefficient of degree n in power series if s is the expansion
343  *  variable.  If the expansion point is nonzero, by definition the n=1
344  *  coefficient in s of a+b*(s-z)+c*(s-z)^2+Order((s-z)^3) is b (assuming
345  *  the expansion took place in the s in the first place).
346  *  If s is not the expansion variable, an attempt is made to convert the
347  *  series to a polynomial and return the corresponding coefficient from
348  *  there. */
349 ex pseries::coeff(const ex &s, int n) const
350 {
351         if (var.is_equal(s)) {
352                 if (seq.empty())
353                         return _ex0;
354                 
355                 // Binary search in sequence for given power
356                 numeric looking_for = numeric(n);
357                 int lo = 0, hi = seq.size() - 1;
358                 while (lo <= hi) {
359                         int mid = (lo + hi) / 2;
360                         GINAC_ASSERT(is_exactly_a<numeric>(seq[mid].coeff));
361                         int cmp = ex_to<numeric>(seq[mid].coeff).compare(looking_for);
362                         switch (cmp) {
363                                 case -1:
364                                         lo = mid + 1;
365                                         break;
366                                 case 0:
367                                         return seq[mid].rest;
368                                 case 1:
369                                         hi = mid - 1;
370                                         break;
371                                 default:
372                                         throw(std::logic_error("pseries::coeff: compare() didn't return -1, 0 or 1"));
373                         }
374                 }
375                 return _ex0;
376         } else
377                 return convert_to_poly().coeff(s, n);
378 }
379
380 /** Does nothing. */
381 ex pseries::collect(const ex &s, bool distributed) const
382 {
383         return *this;
384 }
385
386 /** Perform coefficient-wise automatic term rewriting rules in this class. */
387 ex pseries::eval(int level) const
388 {
389         if (level == 1)
390                 return this->hold();
391         
392         if (level == -max_recursion_level)
393                 throw (std::runtime_error("pseries::eval(): recursion limit exceeded"));
394         
395         // Construct a new series with evaluated coefficients
396         epvector new_seq;
397         new_seq.reserve(seq.size());
398         epvector::const_iterator it = seq.begin(), itend = seq.end();
399         while (it != itend) {
400                 new_seq.push_back(expair(it->rest.eval(level-1), it->coeff));
401                 ++it;
402         }
403         return (new pseries(relational(var,point), std::move(new_seq)))->setflag(status_flags::dynallocated | status_flags::evaluated);
404 }
405
406 /** Evaluate coefficients numerically. */
407 ex pseries::evalf(int level) const
408 {
409         if (level == 1)
410                 return *this;
411         
412         if (level == -max_recursion_level)
413                 throw (std::runtime_error("pseries::evalf(): recursion limit exceeded"));
414         
415         // Construct a new series with evaluated coefficients
416         epvector new_seq;
417         new_seq.reserve(seq.size());
418         epvector::const_iterator it = seq.begin(), itend = seq.end();
419         while (it != itend) {
420                 new_seq.push_back(expair(it->rest.evalf(level-1), it->coeff));
421                 ++it;
422         }
423         return (new pseries(relational(var,point), std::move(new_seq)))->setflag(status_flags::dynallocated | status_flags::evaluated);
424 }
425
426 ex pseries::conjugate() const
427 {
428         if(!var.info(info_flags::real))
429                 return conjugate_function(*this).hold();
430
431         std::unique_ptr<epvector> newseq(conjugateepvector(seq));
432         ex newpoint = point.conjugate();
433
434         if (!newseq && are_ex_trivially_equal(point, newpoint)) {
435                 return *this;
436         }
437
438         return (new pseries(var==newpoint, newseq ? std::move(*newseq) : seq))->setflag(status_flags::dynallocated);
439 }
440
441 ex pseries::real_part() const
442 {
443         if(!var.info(info_flags::real))
444                 return real_part_function(*this).hold();
445         ex newpoint = point.real_part();
446         if(newpoint != point)
447                 return real_part_function(*this).hold();
448
449         epvector v;
450         v.reserve(seq.size());
451         for (auto & it : seq)
452                 v.push_back(expair((it.rest).real_part(), it.coeff));
453         return (new pseries(var==point, std::move(v)))->setflag(status_flags::dynallocated);
454 }
455
456 ex pseries::imag_part() const
457 {
458         if(!var.info(info_flags::real))
459                 return imag_part_function(*this).hold();
460         ex newpoint = point.real_part();
461         if(newpoint != point)
462                 return imag_part_function(*this).hold();
463
464         epvector v;
465         v.reserve(seq.size());
466         for (auto & it : seq)
467                 v.push_back(expair((it.rest).imag_part(), it.coeff));
468         return (new pseries(var==point, std::move(v)))->setflag(status_flags::dynallocated);
469 }
470
471 ex pseries::eval_integ() const
472 {
473         std::unique_ptr<epvector> newseq(nullptr);
474         for (auto i=seq.begin(); i!=seq.end(); ++i) {
475                 if (newseq) {
476                         newseq->push_back(expair(i->rest.eval_integ(), i->coeff));
477                         continue;
478                 }
479                 ex newterm = i->rest.eval_integ();
480                 if (!are_ex_trivially_equal(newterm, i->rest)) {
481                         newseq.reset(new epvector);
482                         newseq->reserve(seq.size());
483                         for (auto j=seq.begin(); j!=i; ++j)
484                                 newseq->push_back(*j);
485                         newseq->push_back(expair(newterm, i->coeff));
486                 }
487         }
488
489         ex newpoint = point.eval_integ();
490         if (newseq || !are_ex_trivially_equal(newpoint, point))
491                 return (new pseries(var==newpoint, std::move(*newseq)))
492                        ->setflag(status_flags::dynallocated);
493         return *this;
494 }
495
496 ex pseries::evalm() const
497 {
498         // evalm each coefficient
499         epvector newseq;
500         bool something_changed = false;
501         for (auto i=seq.begin(); i!=seq.end(); ++i) {
502                 if (something_changed) {
503                         ex newcoeff = i->rest.evalm();
504                         if (!newcoeff.is_zero())
505                                 newseq.push_back(expair(newcoeff, i->coeff));
506                 }
507                 else {
508                         ex newcoeff = i->rest.evalm();
509                         if (!are_ex_trivially_equal(newcoeff, i->rest)) {
510                                 something_changed = true;
511                                 newseq.reserve(seq.size());
512                                 std::copy(seq.begin(), i, std::back_inserter<epvector>(newseq));
513                                 if (!newcoeff.is_zero())
514                                         newseq.push_back(expair(newcoeff, i->coeff));
515                         }
516                 }
517         }
518         if (something_changed)
519                 return (new pseries(var==point, std::move(newseq)))->setflag(status_flags::dynallocated);
520         else
521                 return *this;
522 }
523
524 ex pseries::subs(const exmap & m, unsigned options) const
525 {
526         // If expansion variable is being substituted, convert the series to a
527         // polynomial and do the substitution there because the result might
528         // no longer be a power series
529         if (m.find(var) != m.end())
530                 return convert_to_poly(true).subs(m, options);
531         
532         // Otherwise construct a new series with substituted coefficients and
533         // expansion point
534         epvector newseq;
535         newseq.reserve(seq.size());
536         for (auto & it : seq)
537                 newseq.push_back(expair(it.rest.subs(m, options), it.coeff));
538         return (new pseries(relational(var,point.subs(m, options)), std::move(newseq)))->setflag(status_flags::dynallocated);
539 }
540
541 /** Implementation of ex::expand() for a power series.  It expands all the
542  *  terms individually and returns the resulting series as a new pseries. */
543 ex pseries::expand(unsigned options) const
544 {
545         epvector newseq;
546         for (auto & it : seq) {
547                 ex restexp = it.rest.expand();
548                 if (!restexp.is_zero())
549                         newseq.push_back(expair(restexp, it.coeff));
550         }
551         return (new pseries(relational(var,point), std::move(newseq)))
552                 ->setflag(status_flags::dynallocated | (options == 0 ? status_flags::expanded : 0));
553 }
554
555 /** Implementation of ex::diff() for a power series.
556  *  @see ex::diff */
557 ex pseries::derivative(const symbol & s) const
558 {
559         epvector new_seq;
560
561         if (s == var) {
562                 
563                 // FIXME: coeff might depend on var
564                 for (auto & it : seq) {
565                         if (is_order_function(it.rest)) {
566                                 new_seq.push_back(expair(it.rest, it.coeff - 1));
567                         } else {
568                                 ex c = it.rest * it.coeff;
569                                 if (!c.is_zero())
570                                         new_seq.push_back(expair(c, it.coeff - 1));
571                         }
572                 }
573
574         } else {
575
576                 for (auto & it : seq) {
577                         if (is_order_function(it.rest)) {
578                                 new_seq.push_back(it);
579                         } else {
580                                 ex c = it.rest.diff(s);
581                                 if (!c.is_zero())
582                                         new_seq.push_back(expair(c, it.coeff));
583                         }
584                 }
585         }
586
587         return pseries(relational(var,point), std::move(new_seq));
588 }
589
590 ex pseries::convert_to_poly(bool no_order) const
591 {
592         ex e;
593         for (auto & it : seq) {
594                 if (is_order_function(it.rest)) {
595                         if (!no_order)
596                                 e += Order(power(var - point, it.coeff));
597                 } else
598                         e += it.rest * power(var - point, it.coeff);
599         }
600         return e;
601 }
602
603 bool pseries::is_terminating() const
604 {
605         return seq.empty() || !is_order_function((seq.end()-1)->rest);
606 }
607
608 ex pseries::coeffop(size_t i) const
609 {
610         if (i >= nops())
611                 throw (std::out_of_range("coeffop() out of range"));
612         return seq[i].rest;
613 }
614
615 ex pseries::exponop(size_t i) const
616 {
617         if (i >= nops())
618                 throw (std::out_of_range("exponop() out of range"));
619         return seq[i].coeff;
620 }
621
622
623 /*
624  *  Implementations of series expansion
625  */
626
627 /** Default implementation of ex::series(). This performs Taylor expansion.
628  *  @see ex::series */
629 ex basic::series(const relational & r, int order, unsigned options) const
630 {
631         epvector seq;
632         const symbol &s = ex_to<symbol>(r.lhs());
633
634         // default for order-values that make no sense for Taylor expansion
635         if ((order <= 0) && this->has(s)) {
636                 seq.push_back(expair(Order(_ex1), order));
637                 return pseries(r, std::move(seq));
638         }
639
640         // do Taylor expansion
641         numeric fac = 1;
642         ex deriv = *this;
643         ex coeff = deriv.subs(r, subs_options::no_pattern);
644
645         if (!coeff.is_zero()) {
646                 seq.push_back(expair(coeff, _ex0));
647         }
648
649         int n;
650         for (n=1; n<order; ++n) {
651                 fac = fac.mul(n);
652                 // We need to test for zero in order to see if the series terminates.
653                 // The problem is that there is no such thing as a perfect test for
654                 // zero.  Expanding the term occasionally helps a little...
655                 deriv = deriv.diff(s).expand();
656                 if (deriv.is_zero())  // Series terminates
657                         return pseries(r, std::move(seq));
658
659                 coeff = deriv.subs(r, subs_options::no_pattern);
660                 if (!coeff.is_zero())
661                         seq.push_back(expair(fac.inverse() * coeff, n));
662         }
663         
664         // Higher-order terms, if present
665         deriv = deriv.diff(s);
666         if (!deriv.expand().is_zero())
667                 seq.push_back(expair(Order(_ex1), n));
668         return pseries(r, std::move(seq));
669 }
670
671
672 /** Implementation of ex::series() for symbols.
673  *  @see ex::series */
674 ex symbol::series(const relational & r, int order, unsigned options) const
675 {
676         epvector seq;
677         const ex point = r.rhs();
678         GINAC_ASSERT(is_a<symbol>(r.lhs()));
679
680         if (this->is_equal_same_type(ex_to<symbol>(r.lhs()))) {
681                 if (order > 0 && !point.is_zero())
682                         seq.push_back(expair(point, _ex0));
683                 if (order > 1)
684                         seq.push_back(expair(_ex1, _ex1));
685                 else
686                         seq.push_back(expair(Order(_ex1), numeric(order)));
687         } else
688                 seq.push_back(expair(*this, _ex0));
689         return pseries(r, std::move(seq));
690 }
691
692
693 /** Add one series object to another, producing a pseries object that
694  *  represents the sum.
695  *
696  *  @param other  pseries object to add with
697  *  @return the sum as a pseries */
698 ex pseries::add_series(const pseries &other) const
699 {
700         // Adding two series with different variables or expansion points
701         // results in an empty (constant) series 
702         if (!is_compatible_to(other)) {
703                 epvector nul { expair(Order(_ex1), _ex0) };
704                 return pseries(relational(var,point), std::move(nul));
705         }
706         
707         // Series addition
708         epvector new_seq;
709         auto a = seq.begin(), a_end = seq.end();
710         auto b = other.seq.begin(), b_end = other.seq.end();
711         int pow_a = std::numeric_limits<int>::max(), pow_b = std::numeric_limits<int>::max();
712         for (;;) {
713                 // If a is empty, fill up with elements from b and stop
714                 if (a == a_end) {
715                         while (b != b_end) {
716                                 new_seq.push_back(*b);
717                                 ++b;
718                         }
719                         break;
720                 } else
721                         pow_a = ex_to<numeric>((*a).coeff).to_int();
722                 
723                 // If b is empty, fill up with elements from a and stop
724                 if (b == b_end) {
725                         while (a != a_end) {
726                                 new_seq.push_back(*a);
727                                 ++a;
728                         }
729                         break;
730                 } else
731                         pow_b = ex_to<numeric>((*b).coeff).to_int();
732                 
733                 // a and b are non-empty, compare powers
734                 if (pow_a < pow_b) {
735                         // a has lesser power, get coefficient from a
736                         new_seq.push_back(*a);
737                         if (is_order_function((*a).rest))
738                                 break;
739                         ++a;
740                 } else if (pow_b < pow_a) {
741                         // b has lesser power, get coefficient from b
742                         new_seq.push_back(*b);
743                         if (is_order_function((*b).rest))
744                                 break;
745                         ++b;
746                 } else {
747                         // Add coefficient of a and b
748                         if (is_order_function((*a).rest) || is_order_function((*b).rest)) {
749                                 new_seq.push_back(expair(Order(_ex1), (*a).coeff));
750                                 break;  // Order term ends the sequence
751                         } else {
752                                 ex sum = (*a).rest + (*b).rest;
753                                 if (!(sum.is_zero()))
754                                         new_seq.push_back(expair(sum, numeric(pow_a)));
755                                 ++a;
756                                 ++b;
757                         }
758                 }
759         }
760         return pseries(relational(var,point), std::move(new_seq));
761 }
762
763
764 /** Implementation of ex::series() for sums. This performs series addition when
765  *  adding pseries objects.
766  *  @see ex::series */
767 ex add::series(const relational & r, int order, unsigned options) const
768 {
769         ex acc; // Series accumulator
770         
771         // Get first term from overall_coeff
772         acc = overall_coeff.series(r, order, options);
773         
774         // Add remaining terms
775         for (auto & it : seq) {
776                 ex op;
777                 if (is_exactly_a<pseries>(it.rest))
778                         op = it.rest;
779                 else
780                         op = it.rest.series(r, order, options);
781                 if (!it.coeff.is_equal(_ex1))
782                         op = ex_to<pseries>(op).mul_const(ex_to<numeric>(it.coeff));
783                 
784                 // Series addition
785                 acc = ex_to<pseries>(acc).add_series(ex_to<pseries>(op));
786         }
787         return acc;
788 }
789
790
791 /** Multiply a pseries object with a numeric constant, producing a pseries
792  *  object that represents the product.
793  *
794  *  @param other  constant to multiply with
795  *  @return the product as a pseries */
796 ex pseries::mul_const(const numeric &other) const
797 {
798         epvector new_seq;
799         new_seq.reserve(seq.size());
800         
801         for (auto & it : seq) {
802                 if (!is_order_function(it.rest))
803                         new_seq.push_back(expair(it.rest * other, it.coeff));
804                 else
805                         new_seq.push_back(it);
806         }
807         return pseries(relational(var,point), std::move(new_seq));
808 }
809
810
811 /** Multiply one pseries object to another, producing a pseries object that
812  *  represents the product.
813  *
814  *  @param other  pseries object to multiply with
815  *  @return the product as a pseries */
816 ex pseries::mul_series(const pseries &other) const
817 {
818         // Multiplying two series with different variables or expansion points
819         // results in an empty (constant) series 
820         if (!is_compatible_to(other)) {
821                 epvector nul { expair(Order(_ex1), _ex0) };
822                 return pseries(relational(var,point), std::move(nul));
823         }
824
825         if (seq.empty() || other.seq.empty()) {
826                 return (new pseries(var==point, epvector()))
827                        ->setflag(status_flags::dynallocated);
828         }
829         
830         // Series multiplication
831         epvector new_seq;
832         int a_max = degree(var);
833         int b_max = other.degree(var);
834         int a_min = ldegree(var);
835         int b_min = other.ldegree(var);
836         int cdeg_min = a_min + b_min;
837         int cdeg_max = a_max + b_max;
838         
839         int higher_order_a = std::numeric_limits<int>::max();
840         int higher_order_b = std::numeric_limits<int>::max();
841         if (is_order_function(coeff(var, a_max)))
842                 higher_order_a = a_max + b_min;
843         if (is_order_function(other.coeff(var, b_max)))
844                 higher_order_b = b_max + a_min;
845         int higher_order_c = std::min(higher_order_a, higher_order_b);
846         if (cdeg_max >= higher_order_c)
847                 cdeg_max = higher_order_c - 1;
848         
849         for (int cdeg=cdeg_min; cdeg<=cdeg_max; ++cdeg) {
850                 ex co = _ex0;
851                 // c(i)=a(0)b(i)+...+a(i)b(0)
852                 for (int i=a_min; cdeg-i>=b_min; ++i) {
853                         ex a_coeff = coeff(var, i);
854                         ex b_coeff = other.coeff(var, cdeg-i);
855                         if (!is_order_function(a_coeff) && !is_order_function(b_coeff))
856                                 co += a_coeff * b_coeff;
857                 }
858                 if (!co.is_zero())
859                         new_seq.push_back(expair(co, numeric(cdeg)));
860         }
861         if (higher_order_c < std::numeric_limits<int>::max())
862                 new_seq.push_back(expair(Order(_ex1), numeric(higher_order_c)));
863         return pseries(relational(var, point), std::move(new_seq));
864 }
865
866
867 /** Implementation of ex::series() for product. This performs series
868  *  multiplication when multiplying series.
869  *  @see ex::series */
870 ex mul::series(const relational & r, int order, unsigned options) const
871 {
872         pseries acc; // Series accumulator
873
874         GINAC_ASSERT(is_a<symbol>(r.lhs()));
875         const ex& sym = r.lhs();
876                 
877         // holds ldegrees of the series of individual factors
878         std::vector<int> ldegrees;
879         std::vector<bool> ldegree_redo;
880
881         // find minimal degrees
882         // first round: obtain a bound up to which minimal degrees have to be
883         // considered
884         for (auto & it : seq) {
885
886                 ex expon = it.coeff;
887                 int factor = 1;
888                 ex buf;
889                 if (expon.info(info_flags::integer)) {
890                         buf = it.rest;
891                         factor = ex_to<numeric>(expon).to_int();
892                 } else {
893                         buf = recombine_pair_to_ex(it);
894                 }
895
896                 int real_ldegree = 0;
897                 bool flag_redo = false;
898                 try {
899                         real_ldegree = buf.expand().ldegree(sym-r.rhs());
900                 } catch (std::runtime_error) {}
901
902                 if (real_ldegree == 0) {
903                         if ( factor < 0 ) {
904                                 // This case must terminate, otherwise we would have division by
905                                 // zero.
906                                 int orderloop = 0;
907                                 do {
908                                         orderloop++;
909                                         real_ldegree = buf.series(r, orderloop, options).ldegree(sym);
910                                 } while (real_ldegree == orderloop);
911                         } else {
912                                 // Here it is possible that buf does not have a ldegree, therefore
913                                 // check only if ldegree is negative, otherwise reconsider the case
914                                 // in the second round.
915                                 real_ldegree = buf.series(r, 0, options).ldegree(sym);
916                                 if (real_ldegree == 0)
917                                         flag_redo = true;
918                         }
919                 }
920
921                 ldegrees.push_back(factor * real_ldegree);
922                 ldegree_redo.push_back(flag_redo);
923         }
924
925         int degbound = order-std::accumulate(ldegrees.begin(), ldegrees.end(), 0);
926         // Second round: determine the remaining positive ldegrees by the series
927         // method.
928         // here we can ignore ldegrees larger than degbound
929         size_t j = 0;
930         for (auto & it : seq) {
931                 if ( ldegree_redo[j] ) {
932                         ex expon = it.coeff;
933                         int factor = 1;
934                         ex buf;
935                         if (expon.info(info_flags::integer)) {
936                                 buf = it.rest;
937                                 factor = ex_to<numeric>(expon).to_int();
938                         } else {
939                                 buf = recombine_pair_to_ex(it);
940                         }
941                         int real_ldegree = 0;
942                         int orderloop = 0;
943                         do {
944                                 orderloop++;
945                                 real_ldegree = buf.series(r, orderloop, options).ldegree(sym);
946                         } while ((real_ldegree == orderloop)
947                               && (factor*real_ldegree < degbound));
948                         ldegrees[j] = factor * real_ldegree;
949                         degbound -= factor * real_ldegree;
950                 }
951                 j++;
952         }
953
954         int degsum = std::accumulate(ldegrees.begin(), ldegrees.end(), 0);
955
956         if (degsum >= order) {
957                 epvector epv { expair(Order(_ex1), order) };
958                 return (new pseries(r, std::move(epv)))->setflag(status_flags::dynallocated);
959         }
960
961         // Multiply with remaining terms
962         auto itd = ldegrees.begin();
963         for (auto it=seq.begin(), itend=seq.end(); it!=itend; ++it, ++itd) {
964
965                 // do series expansion with adjusted order
966                 ex op = recombine_pair_to_ex(*it).series(r, order-degsum+(*itd), options);
967
968                 // Series multiplication
969                 if (it == seq.begin())
970                         acc = ex_to<pseries>(op);
971                 else
972                         acc = ex_to<pseries>(acc.mul_series(ex_to<pseries>(op)));
973         }
974
975         return acc.mul_const(ex_to<numeric>(overall_coeff));
976 }
977
978
979 /** Compute the p-th power of a series.
980  *
981  *  @param p  power to compute
982  *  @param deg  truncation order of series calculation */
983 ex pseries::power_const(const numeric &p, int deg) const
984 {
985         // method:
986         // (due to Leonhard Euler)
987         // let A(x) be this series and for the time being let it start with a
988         // constant (later we'll generalize):
989         //     A(x) = a_0 + a_1*x + a_2*x^2 + ...
990         // We want to compute
991         //     C(x) = A(x)^p
992         //     C(x) = c_0 + c_1*x + c_2*x^2 + ...
993         // Taking the derivative on both sides and multiplying with A(x) one
994         // immediately arrives at
995         //     C'(x)*A(x) = p*C(x)*A'(x)
996         // Multiplying this out and comparing coefficients we get the recurrence
997         // formula
998         //     c_i = (i*p*a_i*c_0 + ((i-1)*p-1)*a_{i-1}*c_1 + ...
999         //                    ... + (p-(i-1))*a_1*c_{i-1})/(a_0*i)
1000         // which can easily be solved given the starting value c_0 = (a_0)^p.
1001         // For the more general case where the leading coefficient of A(x) is not
1002         // a constant, just consider A2(x) = A(x)*x^m, with some integer m and
1003         // repeat the above derivation.  The leading power of C2(x) = A2(x)^2 is
1004         // then of course x^(p*m) but the recurrence formula still holds.
1005         
1006         if (seq.empty()) {
1007                 // as a special case, handle the empty (zero) series honoring the
1008                 // usual power laws such as implemented in power::eval()
1009                 if (p.real().is_zero())
1010                         throw std::domain_error("pseries::power_const(): pow(0,I) is undefined");
1011                 else if (p.real().is_negative())
1012                         throw pole_error("pseries::power_const(): division by zero",1);
1013                 else
1014                         return *this;
1015         }
1016         
1017         const int ldeg = ldegree(var);
1018         if (!(p*ldeg).is_integer())
1019                 throw std::runtime_error("pseries::power_const(): trying to assemble a Puiseux series");
1020
1021         // adjust number of coefficients
1022         int numcoeff = deg - (p*ldeg).to_int();
1023         if (numcoeff <= 0) {
1024                 epvector epv { expair(Order(_ex1), deg) };
1025                 return (new pseries(relational(var,point), std::move(epv)))
1026                        ->setflag(status_flags::dynallocated);
1027         }
1028         
1029         // O(x^n)^(-m) is undefined
1030         if (seq.size() == 1 && is_order_function(seq[0].rest) && p.real().is_negative())
1031                 throw pole_error("pseries::power_const(): division by zero",1);
1032         
1033         // Compute coefficients of the powered series
1034         exvector co;
1035         co.reserve(numcoeff);
1036         co.push_back(power(coeff(var, ldeg), p));
1037         for (int i=1; i<numcoeff; ++i) {
1038                 ex sum = _ex0;
1039                 for (int j=1; j<=i; ++j) {
1040                         ex c = coeff(var, j + ldeg);
1041                         if (is_order_function(c)) {
1042                                 co.push_back(Order(_ex1));
1043                                 break;
1044                         } else
1045                                 sum += (p * j - (i - j)) * co[i - j] * c;
1046                 }
1047                 co.push_back(sum / coeff(var, ldeg) / i);
1048         }
1049         
1050         // Construct new series (of non-zero coefficients)
1051         epvector new_seq;
1052         bool higher_order = false;
1053         for (int i=0; i<numcoeff; ++i) {
1054                 if (!co[i].is_zero())
1055                         new_seq.push_back(expair(co[i], p * ldeg + i));
1056                 if (is_order_function(co[i])) {
1057                         higher_order = true;
1058                         break;
1059                 }
1060         }
1061         if (!higher_order)
1062                 new_seq.push_back(expair(Order(_ex1), p * ldeg + numcoeff));
1063
1064         return pseries(relational(var,point), std::move(new_seq));
1065 }
1066
1067
1068 /** Return a new pseries object with the powers shifted by deg. */
1069 pseries pseries::shift_exponents(int deg) const
1070 {
1071         epvector newseq = seq;
1072         for (auto & it : newseq)
1073                 it.coeff += deg;
1074         return pseries(relational(var, point), std::move(newseq));
1075 }
1076
1077
1078 /** Implementation of ex::series() for powers. This performs Laurent expansion
1079  *  of reciprocals of series at singularities.
1080  *  @see ex::series */
1081 ex power::series(const relational & r, int order, unsigned options) const
1082 {
1083         // If basis is already a series, just power it
1084         if (is_exactly_a<pseries>(basis))
1085                 return ex_to<pseries>(basis).power_const(ex_to<numeric>(exponent), order);
1086
1087         // Basis is not a series, may there be a singularity?
1088         bool must_expand_basis = false;
1089         try {
1090                 basis.subs(r, subs_options::no_pattern);
1091         } catch (pole_error) {
1092                 must_expand_basis = true;
1093         }
1094
1095         bool exponent_is_regular = true;
1096         try {
1097                 exponent.subs(r, subs_options::no_pattern);
1098         } catch (pole_error) {
1099                 exponent_is_regular = false;
1100         }
1101
1102         if (!exponent_is_regular) {
1103                 ex l = exponent*log(basis);
1104                 // this == exp(l);
1105                 ex le = l.series(r, order, options);
1106                 // Note: expanding exp(l) won't help, since that will attempt
1107                 // Taylor expansion, and fail (because exponent is "singular")
1108                 // Still l itself might be expanded in Taylor series.
1109                 // Examples:
1110                 // sin(x)/x*log(cos(x))
1111                 // 1/x*log(1 + x)
1112                 return exp(le).series(r, order, options);
1113                 // Note: if l happens to have a Laurent expansion (with
1114                 // negative powers of (var - point)), expanding exp(le)
1115                 // will barf (which is The Right Thing).
1116         }
1117
1118         // Is the expression of type something^(-int)?
1119         if (!must_expand_basis && !exponent.info(info_flags::negint)
1120          && (!is_a<add>(basis) || !is_a<numeric>(exponent)))
1121                 return basic::series(r, order, options);
1122
1123         // Is the expression of type 0^something?
1124         if (!must_expand_basis && !basis.subs(r, subs_options::no_pattern).is_zero()
1125          && (!is_a<add>(basis) || !is_a<numeric>(exponent)))
1126                 return basic::series(r, order, options);
1127
1128         // Singularity encountered, is the basis equal to (var - point)?
1129         if (basis.is_equal(r.lhs() - r.rhs())) {
1130                 epvector new_seq;
1131                 if (ex_to<numeric>(exponent).to_int() < order)
1132                         new_seq.push_back(expair(_ex1, exponent));
1133                 else
1134                         new_seq.push_back(expair(Order(_ex1), exponent));
1135                 return pseries(r, std::move(new_seq));
1136         }
1137
1138         // No, expand basis into series
1139
1140         numeric numexp;
1141         if (is_a<numeric>(exponent)) {
1142                 numexp = ex_to<numeric>(exponent);
1143         } else {
1144                 numexp = 0;
1145         }
1146         const ex& sym = r.lhs();
1147         // find existing minimal degree
1148         ex eb = basis.expand();
1149         int real_ldegree = 0;
1150         if (eb.info(info_flags::rational_function))
1151                 real_ldegree = eb.ldegree(sym-r.rhs());
1152         if (real_ldegree == 0) {
1153                 int orderloop = 0;
1154                 do {
1155                         orderloop++;
1156                         real_ldegree = basis.series(r, orderloop, options).ldegree(sym);
1157                 } while (real_ldegree == orderloop);
1158         }
1159
1160         if (!(real_ldegree*numexp).is_integer())
1161                 throw std::runtime_error("pseries::power_const(): trying to assemble a Puiseux series");
1162         ex e = basis.series(r, (order + real_ldegree*(1-numexp)).to_int(), options);
1163         
1164         ex result;
1165         try {
1166                 result = ex_to<pseries>(e).power_const(numexp, order);
1167         } catch (pole_error) {
1168                 epvector ser { expair(Order(_ex1), order) };
1169                 result = pseries(r, std::move(ser));
1170         }
1171
1172         return result;
1173 }
1174
1175
1176 /** Re-expansion of a pseries object. */
1177 ex pseries::series(const relational & r, int order, unsigned options) const
1178 {
1179         const ex p = r.rhs();
1180         GINAC_ASSERT(is_a<symbol>(r.lhs()));
1181         const symbol &s = ex_to<symbol>(r.lhs());
1182         
1183         if (var.is_equal(s) && point.is_equal(p)) {
1184                 if (order > degree(s))
1185                         return *this;
1186                 else {
1187                         epvector new_seq;
1188                         for (auto & it : seq) {
1189                                 int o = ex_to<numeric>(it.coeff).to_int();
1190                                 if (o >= order) {
1191                                         new_seq.push_back(expair(Order(_ex1), o));
1192                                         break;
1193                                 }
1194                                 new_seq.push_back(it);
1195                         }
1196                         return pseries(r, std::move(new_seq));
1197                 }
1198         } else
1199                 return convert_to_poly().series(r, order, options);
1200 }
1201
1202 ex integral::series(const relational & r, int order, unsigned options) const
1203 {
1204         if (x.subs(r) != x)
1205                 throw std::logic_error("Cannot series expand wrt dummy variable");
1206         
1207         // Expanding integrand with r substituted taken in boundaries.
1208         ex fseries = f.series(r, order, options);
1209         epvector fexpansion;
1210         fexpansion.reserve(fseries.nops());
1211         for (size_t i=0; i<fseries.nops(); ++i) {
1212                 ex currcoeff = ex_to<pseries>(fseries).coeffop(i);
1213                 currcoeff = (currcoeff == Order(_ex1))
1214                         ? currcoeff
1215                         : integral(x, a.subs(r), b.subs(r), currcoeff);
1216                 if (currcoeff != 0)
1217                         fexpansion.push_back(
1218                                 expair(currcoeff, ex_to<pseries>(fseries).exponop(i)));
1219         }
1220
1221         // Expanding lower boundary
1222         ex result = (new pseries(r, fexpansion))->setflag(status_flags::dynallocated);
1223         ex aseries = (a-a.subs(r)).series(r, order, options);
1224         fseries = f.series(x == (a.subs(r)), order, options);
1225         for (size_t i=0; i<fseries.nops(); ++i) {
1226                 ex currcoeff = ex_to<pseries>(fseries).coeffop(i);
1227                 if (is_order_function(currcoeff))
1228                         break;
1229                 ex currexpon = ex_to<pseries>(fseries).exponop(i);
1230                 int orderforf = order-ex_to<numeric>(currexpon).to_int()-1;
1231                 currcoeff = currcoeff.series(r, orderforf);
1232                 ex term = ex_to<pseries>(aseries).power_const(ex_to<numeric>(currexpon+1),order);
1233                 term = ex_to<pseries>(term).mul_const(ex_to<numeric>(-1/(currexpon+1)));
1234                 term = ex_to<pseries>(term).mul_series(ex_to<pseries>(currcoeff));
1235                 result = ex_to<pseries>(result).add_series(ex_to<pseries>(term));
1236         }
1237
1238         // Expanding upper boundary
1239         ex bseries = (b-b.subs(r)).series(r, order, options);
1240         fseries = f.series(x == (b.subs(r)), order, options);
1241         for (size_t i=0; i<fseries.nops(); ++i) {
1242                 ex currcoeff = ex_to<pseries>(fseries).coeffop(i);
1243                 if (is_order_function(currcoeff))
1244                         break;
1245                 ex currexpon = ex_to<pseries>(fseries).exponop(i);
1246                 int orderforf = order-ex_to<numeric>(currexpon).to_int()-1;
1247                 currcoeff = currcoeff.series(r, orderforf);
1248                 ex term = ex_to<pseries>(bseries).power_const(ex_to<numeric>(currexpon+1),order);
1249                 term = ex_to<pseries>(term).mul_const(ex_to<numeric>(1/(currexpon+1)));
1250                 term = ex_to<pseries>(term).mul_series(ex_to<pseries>(currcoeff));
1251                 result = ex_to<pseries>(result).add_series(ex_to<pseries>(term));
1252         }
1253
1254         return result;
1255 }
1256
1257
1258 /** Compute the truncated series expansion of an expression.
1259  *  This function returns an expression containing an object of class pseries 
1260  *  to represent the series. If the series does not terminate within the given
1261  *  truncation order, the last term of the series will be an order term.
1262  *
1263  *  @param r  expansion relation, lhs holds variable and rhs holds point
1264  *  @param order  truncation order of series calculations
1265  *  @param options  of class series_options
1266  *  @return an expression holding a pseries object */
1267 ex ex::series(const ex & r, int order, unsigned options) const
1268 {
1269         ex e;
1270         relational rel_;
1271         
1272         if (is_a<relational>(r))
1273                 rel_ = ex_to<relational>(r);
1274         else if (is_a<symbol>(r))
1275                 rel_ = relational(r,_ex0);
1276         else
1277                 throw (std::logic_error("ex::series(): expansion point has unknown type"));
1278         
1279         e = bp->series(rel_, order, options);
1280         return e;
1281 }
1282
1283 GINAC_BIND_UNARCHIVER(pseries);
1284
1285 } // namespace GiNaC