1 /* Copyright 2009-2016 Francesco Biscani (bluescarni@gmail.com)
2 
3 This file is part of the Piranha library.
4 
5 The Piranha library is free software; you can redistribute it and/or modify
6 it under the terms of either:
7 
8   * the GNU Lesser General Public License as published by the Free
9     Software Foundation; either version 3 of the License, or (at your
10     option) any later version.
11 
12 or
13 
14   * the GNU General Public License as published by the Free Software
15     Foundation; either version 3 of the License, or (at your option) any
16     later version.
17 
18 or both in parallel, as here.
19 
20 The Piranha library is distributed in the hope that it will be useful, but
21 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
22 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
23 for more details.
24 
25 You should have received copies of the GNU General Public License and the
26 GNU Lesser General Public License along with the Piranha library.  If not,
27 see https://www.gnu.org/licenses/. */
28 
29 #include "../src/power_series.hpp"
30 
31 #define BOOST_TEST_MODULE power_series_02_test
32 #include <boost/test/included/unit_test.hpp>
33 
34 #include <boost/mpl/for_each.hpp>
35 #include <boost/mpl/vector.hpp>
36 #include <cstddef>
37 #include <functional>
38 #include <iostream>
39 #include <limits>
40 #include <sstream>
41 #include <stdexcept>
42 #include <string>
43 #include <type_traits>
44 #include <vector>
45 
46 #include "../src/init.hpp"
47 #include "../src/math.hpp"
48 #include "../src/monomial.hpp"
49 #include "../src/mp_integer.hpp"
50 #include "../src/mp_rational.hpp"
51 #include "../src/poisson_series.hpp"
52 #include "../src/polynomial.hpp"
53 #include "../src/real.hpp"
54 #include "../src/real_trigonometric_kronecker_monomial.hpp"
55 #include "../src/s11n.hpp"
56 #include "../src/series.hpp"
57 
58 using namespace piranha;
59 
60 typedef boost::mpl::vector<double, integer, real> cf_types;
61 typedef boost::mpl::vector<int, integer> expo_types;
62 
63 template <typename Cf, typename Expo>
64 class g_series_type : public power_series<series<Cf, monomial<Expo>, g_series_type<Cf, Expo>>, g_series_type<Cf, Expo>>
65 {
66     using base = power_series<series<Cf, monomial<Expo>, g_series_type<Cf, Expo>>, g_series_type<Cf, Expo>>;
67 
68 public:
69     g_series_type() = default;
70     g_series_type(const g_series_type &) = default;
71     g_series_type(g_series_type &&) = default;
72     g_series_type &operator=(const g_series_type &) = default;
73     g_series_type &operator=(g_series_type &&) = default;
74     PIRANHA_FORWARDING_CTOR(g_series_type, base)
75     PIRANHA_FORWARDING_ASSIGNMENT(g_series_type, base)
76 };
77 
78 template <typename Cf>
79 class g_series_type2 : public power_series<series<Cf, rtk_monomial, g_series_type2<Cf>>, g_series_type2<Cf>>
80 {
81     typedef power_series<series<Cf, rtk_monomial, g_series_type2<Cf>>, g_series_type2<Cf>> base;
82 
83 public:
84     g_series_type2() = default;
85     g_series_type2(const g_series_type2 &) = default;
86     g_series_type2(g_series_type2 &&) = default;
87     g_series_type2 &operator=(const g_series_type2 &) = default;
88     g_series_type2 &operator=(g_series_type2 &&) = default;
89     PIRANHA_FORWARDING_CTOR(g_series_type2, base)
90     PIRANHA_FORWARDING_ASSIGNMENT(g_series_type2, base)
91 };
92 
93 struct fake_int {
94     fake_int();
95     explicit fake_int(int);
96     fake_int(const fake_int &);
97     fake_int(fake_int &&) noexcept;
98     fake_int &operator=(const fake_int &);
99     fake_int &operator=(fake_int &&) noexcept;
100     ~fake_int();
101     bool operator==(const fake_int &) const;
102     bool operator!=(const fake_int &) const;
103     bool operator<(const fake_int &) const;
104     fake_int operator+(const fake_int &) const;
105     fake_int &operator+=(const fake_int &);
106     fake_int operator-(const fake_int &) const;
107     fake_int &operator-=(const fake_int &);
108     friend std::ostream &operator<<(std::ostream &, const fake_int &);
109 };
110 
111 namespace piranha
112 {
113 
114 namespace math
115 {
116 
117 template <>
118 struct negate_impl<fake_int> {
119     void operator()(fake_int &) const;
120 };
121 }
122 }
123 
124 namespace std
125 {
126 
127 template <>
128 struct hash<fake_int> {
129     typedef size_t result_type;
130     typedef fake_int argument_type;
131     result_type operator()(const argument_type &) const;
132 };
133 }
134 
BOOST_AUTO_TEST_CASE(power_series_test_02)135 BOOST_AUTO_TEST_CASE(power_series_test_02)
136 {
137     init();
138     // Check the rational degree.
139     typedef g_series_type<double, rational> stype0;
140     BOOST_CHECK((has_degree<stype0>::value));
141     BOOST_CHECK((has_ldegree<stype0>::value));
142     BOOST_CHECK((std::is_same<decltype(math::degree(std::declval<stype0>())), rational>::value));
143     BOOST_CHECK((std::is_same<decltype(math::ldegree(std::declval<stype0>())), rational>::value));
144     BOOST_CHECK(
145         (std::is_same<decltype(math::degree(std::declval<stype0>(), std::vector<std::string>{})), rational>::value));
146     BOOST_CHECK(
147         (std::is_same<decltype(math::ldegree(std::declval<stype0>(), std::vector<std::string>{})), rational>::value));
148     typedef g_series_type<double, int> stype1;
149     BOOST_CHECK((has_degree<stype1>::value));
150     BOOST_CHECK((has_ldegree<stype1>::value));
151     BOOST_CHECK((std::is_same<decltype(math::degree(std::declval<stype1>())), int>::value));
152     BOOST_CHECK((std::is_same<decltype(math::ldegree(std::declval<stype1>())), int>::value));
153     BOOST_CHECK((std::is_same<decltype(math::degree(std::declval<stype1>(), std::vector<std::string>{})), int>::value));
154     BOOST_CHECK(
155         (std::is_same<decltype(math::ldegree(std::declval<stype1>(), std::vector<std::string>{})), int>::value));
156     typedef g_series_type<stype1, long> stype2;
157     BOOST_CHECK((has_degree<stype2>::value));
158     BOOST_CHECK((has_ldegree<stype2>::value));
159     BOOST_CHECK((std::is_same<decltype(math::degree(std::declval<stype2>())), long>::value));
160     BOOST_CHECK((std::is_same<decltype(math::ldegree(std::declval<stype2>())), long>::value));
161     BOOST_CHECK(
162         (std::is_same<decltype(math::degree(std::declval<stype2>(), std::vector<std::string>{})), long>::value));
163     BOOST_CHECK(
164         (std::is_same<decltype(math::ldegree(std::declval<stype2>(), std::vector<std::string>{})), long>::value));
165     typedef g_series_type2<double> stype3;
166     BOOST_CHECK((!has_degree<stype3>::value));
167     BOOST_CHECK((!has_ldegree<stype3>::value));
168     typedef g_series_type2<g_series_type<g_series_type<double, int>, integer>> stype4;
169     BOOST_CHECK((has_degree<stype4>::value));
170     BOOST_CHECK((has_ldegree<stype4>::value));
171     BOOST_CHECK((std::is_same<decltype(math::degree(std::declval<stype4>())), integer>::value));
172     BOOST_CHECK((std::is_same<decltype(math::ldegree(std::declval<stype4>())), integer>::value));
173     BOOST_CHECK(
174         (std::is_same<decltype(math::degree(std::declval<stype4>(), std::vector<std::string>{})), integer>::value));
175     BOOST_CHECK(
176         (std::is_same<decltype(math::ldegree(std::declval<stype4>(), std::vector<std::string>{})), integer>::value));
177     // Check actual instantiations as well.
178     std::vector<std::string> ss;
179     BOOST_CHECK_EQUAL(math::degree(stype1{}), 0);
180     BOOST_CHECK_EQUAL(math::ldegree(stype1{}), 0);
181     BOOST_CHECK_EQUAL(math::degree(stype1{}, ss), 0);
182     BOOST_CHECK_EQUAL(math::ldegree(stype1{}, ss), 0);
183     BOOST_CHECK_EQUAL(math::degree(stype2{}), 0);
184     BOOST_CHECK_EQUAL(math::ldegree(stype2{}), 0);
185     BOOST_CHECK_EQUAL(math::degree(stype2{}, ss), 0);
186     BOOST_CHECK_EQUAL(math::ldegree(stype2{}, ss), 0);
187     BOOST_CHECK_EQUAL(math::degree(stype4{}), 0);
188     BOOST_CHECK_EQUAL(math::ldegree(stype4{}), 0);
189     BOOST_CHECK_EQUAL(math::degree(stype4{}, ss), 0);
190     BOOST_CHECK_EQUAL(math::ldegree(stype4{}, ss), 0);
191     // Tests with fake int.
192     typedef g_series_type<double, fake_int> stype5;
193     BOOST_CHECK((has_degree<stype5>::value));
194     BOOST_CHECK((has_ldegree<stype5>::value));
195     BOOST_CHECK((std::is_same<decltype(math::degree(std::declval<stype5>())), fake_int>::value));
196     BOOST_CHECK((std::is_same<decltype(math::ldegree(std::declval<stype5>())), fake_int>::value));
197     BOOST_CHECK(
198         (std::is_same<decltype(math::degree(std::declval<stype5>(), std::vector<std::string>{})), fake_int>::value));
199     BOOST_CHECK(
200         (std::is_same<decltype(math::ldegree(std::declval<stype5>(), std::vector<std::string>{})), fake_int>::value));
201     typedef g_series_type<stype5, int> stype6;
202     // This does not have a degree type because fake_int cannot be added to integer.
203     BOOST_CHECK((!has_degree<stype6>::value));
204     BOOST_CHECK((!has_ldegree<stype6>::value));
205 }
206 
BOOST_AUTO_TEST_CASE(power_series_serialization_test)207 BOOST_AUTO_TEST_CASE(power_series_serialization_test)
208 {
209     typedef g_series_type<polynomial<rational, monomial<rational>>, rational> stype;
210     stype x("x"), y("y"), z = x + y, tmp;
211     std::stringstream ss;
212     {
213         boost::archive::text_oarchive oa(ss);
214         oa << z;
215     }
216     {
217         boost::archive::text_iarchive ia(ss);
218         ia >> tmp;
219     }
220     BOOST_CHECK_EQUAL(z, tmp);
221 }
222 
BOOST_AUTO_TEST_CASE(power_series_truncation_test)223 BOOST_AUTO_TEST_CASE(power_series_truncation_test)
224 {
225     // A test with polynomial, degree only in the key.
226     {
227         typedef polynomial<double, monomial<rational>> stype0;
228         BOOST_CHECK((has_truncate_degree<stype0, int>::value));
229         BOOST_CHECK((has_truncate_degree<stype0, rational>::value));
230         BOOST_CHECK((has_truncate_degree<stype0, integer>::value));
231         BOOST_CHECK((!has_truncate_degree<stype0, std::string>::value));
232         stype0 x{"x"}, y{"y"}, z{"z"};
233         stype0 s0;
234         BOOST_CHECK((std::is_same<stype0, decltype(s0.truncate_degree(5))>::value));
235         BOOST_CHECK_EQUAL(s0.truncate_degree(5), s0);
236         s0 = x.pow(rational(10, 3));
237         BOOST_CHECK_EQUAL(s0.truncate_degree(5), s0);
238         BOOST_CHECK_EQUAL(s0.truncate_degree(3 / 2_q), 0);
239         // x**5*y+1/2*z**-5*x*y+x*y*z/4
240         s0 = x.pow(5) * y + z.pow(-5) / 2 * x * y + x * y * z / 4;
241         BOOST_CHECK_EQUAL(s0.truncate_degree(3), z.pow(-5) / 2 * x * y + x * y * z / 4);
242         BOOST_CHECK_EQUAL(math::truncate_degree(s0, -1), z.pow(-5) / 2 * x * y);
243         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 2, {"x"}), z.pow(-5) / 2 * x * y + x * y * z / 4);
244         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 5, {"x", "y"}), z.pow(-5) / 2 * x * y + x * y * z / 4);
245         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 5, {"y", "x", "y"}), z.pow(-5) / 2 * x * y + x * y * z / 4);
246         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 5, {"z", "x"}), s0);
247         // Test with non-existing variable.
248         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 0, {"a", "b"}), s0);
249     }
250     {
251         // Poisson series, degree only in the coefficient.
252         typedef poisson_series<polynomial<rational, monomial<rational>>> st;
253         BOOST_CHECK((has_truncate_degree<st, int>::value));
254         BOOST_CHECK((has_truncate_degree<st, rational>::value));
255         BOOST_CHECK((has_truncate_degree<st, integer>::value));
256         BOOST_CHECK((!has_truncate_degree<st, std::string>::value));
257         st x("x"), y("y"), z("z"), a("a"), b("b");
258         // (x + y**2/4 + 3*x*y*z/7) * cos(a) + (x*y+y*z/3+3*z**2*x/8) * sin(a+b)
259         st s0 = (x + y * y / 4 + 3 * z * x * y / 7) * math::cos(a)
260                 + (x * y + z * y / 3 + 3 * z * z * x / 8) * math::sin(a + b);
261         BOOST_CHECK_EQUAL(s0.truncate_degree(2),
262                           (x + y * y / 4) * math::cos(a) + (x * y + z * y / 3) * math::sin(a + b));
263         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 1l), x * math::cos(a));
264         BOOST_CHECK_EQUAL(math::truncate_degree(s0, -1ll), 0);
265         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 1l, {"x"}),
266                           (x + y * y / 4 + 3 * z * x * y / 7) * math::cos(a)
267                               + (x * y + z * y / 3 + 3 * z * z * x / 8) * math::sin(a + b));
268         BOOST_CHECK_EQUAL(math::truncate_degree(s0, char(0), {"x"}),
269                           y * y / 4 * math::cos(a) + z * y / 3 * math::sin(a + b));
270         BOOST_CHECK_EQUAL(math::truncate_degree(s0, char(1), {"y", "x"}),
271                           x * math::cos(a) + (z * y / 3 + 3 * z * z * x / 8) * math::sin(a + b));
272         BOOST_CHECK_EQUAL(math::truncate_degree(s0, integer(1), {"z"}),
273                           (x + y * y / 4 + 3 * z * x * y / 7) * math::cos(a) + (x * y + z * y / 3) * math::sin(a + b));
274         // Test with non-existing variable.
275         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 0, {"foo", "bar"}), s0);
276     }
277     {
278         // Recursive poly.
279         typedef polynomial<rational, monomial<rational>> st0;
280         typedef polynomial<st0, monomial<rational>> st1;
281         BOOST_CHECK((has_truncate_degree<st1, int>::value));
282         BOOST_CHECK((has_truncate_degree<st1, rational>::value));
283         BOOST_CHECK((has_truncate_degree<st1, integer>::value));
284         BOOST_CHECK((!has_truncate_degree<st1, std::string>::value));
285         // (x*y+x**2+x+1/4)*z + (x+y**2+x**2*y)*z**2 + 3
286         st0 x{"x"}, y{"y"};
287         st1 z{"z"};
288         auto s0 = (x * y + x * x + x + 1_q / 4) * z + (x + y * y + x * x * y) * z * z + 3;
289         BOOST_CHECK_EQUAL(s0.truncate_degree(1), 1 / 4_q * z + 3);
290         BOOST_CHECK_EQUAL(s0.truncate_degree(0), 3);
291         BOOST_CHECK_EQUAL(s0.truncate_degree(2), (x + 1_q / 4) * z + 3);
292         BOOST_CHECK_EQUAL(math::truncate_degree(s0, -3), 0);
293         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 3_q), (x * y + x * x + x + 1_q / 4) * z + x * z * z + 3);
294         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 1, {"x"}), (x * y + x + 1_q / 4) * z + (x + y * y) * z * z + 3);
295         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 1ll, {"x", "y"}), (x + 1_q / 4) * z + x * z * z + 3);
296         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 1, {"x", "z"}), 1_q / 4 * z + 3);
297         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 2, {"x", "z"}), (x * y + x + 1_q / 4) * z + y * y * z * z + 3);
298         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 3, {"x", "z"}),
299                           (x * y + x * x + x + 1_q / 4) * z + (x + y * y) * z * z + 3);
300         // Test with non-existing variable.
301         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 0, {"foo", "bar"}), s0);
302     }
303     {
304         // Recursive poly, integers and rational exponent mixed, same example as above.
305         typedef polynomial<rational, monomial<integer>> st0;
306         typedef polynomial<st0, monomial<rational>> st1;
307         BOOST_CHECK((has_truncate_degree<st1, int>::value));
308         BOOST_CHECK((has_truncate_degree<st1, rational>::value));
309         BOOST_CHECK((has_truncate_degree<st1, integer>::value));
310         BOOST_CHECK((!has_truncate_degree<st1, std::string>::value));
311         // (x*y+x**2+x+1/4)*z + (x+y**2+x**2*y)*z**2 + 3
312         st0 x{"x"}, y{"y"};
313         st1 z{"z"};
314         auto s0 = (x * y + x * x + x + 1_q / 4) * z + (x + y * y + x * x * y) * z * z + 3;
315         BOOST_CHECK_EQUAL(s0.truncate_degree(1), 1 / 4_q * z + 3);
316         BOOST_CHECK_EQUAL(s0.truncate_degree(0), 3);
317         BOOST_CHECK_EQUAL(s0.truncate_degree(2), (x + 1_q / 4) * z + 3);
318         BOOST_CHECK_EQUAL(math::truncate_degree(s0, -3), 0);
319         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 3_q), (x * y + x * x + x + 1_q / 4) * z + x * z * z + 3);
320         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 1, {"x"}), (x * y + x + 1_q / 4) * z + (x + y * y) * z * z + 3);
321         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 1ll, {"x", "y"}), (x + 1_q / 4) * z + x * z * z + 3);
322         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 1, {"x", "z"}), 1_q / 4 * z + 3);
323         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 2, {"x", "z"}), (x * y + x + 1_q / 4) * z + y * y * z * z + 3);
324         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 3, {"x", "z"}),
325                           (x * y + x * x + x + 1_q / 4) * z + (x + y * y) * z * z + 3);
326         // Test with non-existing variable.
327         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 0_q, {"foo", "bar"}), s0);
328     }
329     {
330         // Recursive poly, integers and rational exponent mixed, same example as above but switched.
331         typedef polynomial<rational, monomial<rational>> st0;
332         typedef polynomial<st0, monomial<integer>> st1;
333         BOOST_CHECK((has_truncate_degree<st1, int>::value));
334         BOOST_CHECK((has_truncate_degree<st1, rational>::value));
335         BOOST_CHECK((has_truncate_degree<st1, integer>::value));
336         BOOST_CHECK((!has_truncate_degree<st1, std::string>::value));
337         // (x*y+x**2+x+1/4)*z + (x+y**2+x**2*y)*z**2 + 3
338         st0 x{"x"}, y{"y"};
339         st1 z{"z"};
340         auto s0 = (x * y + x * x + x + 1_q / 4) * z + (x + y * y + x * x * y) * z * z + 3;
341         BOOST_CHECK_EQUAL(s0.truncate_degree(1), 1 / 4_q * z + 3);
342         BOOST_CHECK_EQUAL(s0.truncate_degree(0), 3);
343         BOOST_CHECK_EQUAL(s0.truncate_degree(2), (x + 1_q / 4) * z + 3);
344         BOOST_CHECK_EQUAL(math::truncate_degree(s0, -3), 0);
345         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 3_q), (x * y + x * x + x + 1_q / 4) * z + x * z * z + 3);
346         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 1, {"x"}), (x * y + x + 1_q / 4) * z + (x + y * y) * z * z + 3);
347         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 1ll, {"x", "y"}), (x + 1_q / 4) * z + x * z * z + 3);
348         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 1, {"x", "z"}), 1_q / 4 * z + 3);
349         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 2, {"x", "z"}), (x * y + x + 1_q / 4) * z + y * y * z * z + 3);
350         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 3, {"x", "z"}),
351                           (x * y + x * x + x + 1_q / 4) * z + (x + y * y) * z * z + 3);
352         // Test with non-existing variable.
353         BOOST_CHECK_EQUAL(math::truncate_degree(s0, 0_z, {"foo", "bar"}), s0);
354     }
355 }
356 
BOOST_AUTO_TEST_CASE(power_series_degree_overflow_test)357 BOOST_AUTO_TEST_CASE(power_series_degree_overflow_test)
358 {
359     using p_type = polynomial<integer, monomial<int>>;
360     using pp_type = polynomial<p_type, monomial<int>>;
361     p_type x{"x"};
362     pp_type y{"y"};
363     BOOST_CHECK_THROW((x * y.pow(std::numeric_limits<int>::max())).degree(), std::overflow_error);
364     BOOST_CHECK_THROW((x.pow(-1) * y.pow(std::numeric_limits<int>::min())).degree(), std::overflow_error);
365     BOOST_CHECK_EQUAL((x * y.pow(std::numeric_limits<int>::min())).degree(), std::numeric_limits<int>::min() + 1);
366 }
367 
BOOST_AUTO_TEST_CASE(power_series_mixed_degree_test)368 BOOST_AUTO_TEST_CASE(power_series_mixed_degree_test)
369 {
370     using p_type = polynomial<integer, monomial<int>>;
371     using pp_type = polynomial<p_type, monomial<integer>>;
372     using pp_type2 = polynomial<p_type, monomial<long>>;
373     using pp_type3 = polynomial<p_type, monomial<int>>;
374     using pp_type4 = polynomial<polynomial<rational, monomial<rational>>, monomial<long long>>;
375     p_type x{"x"};
376     pp_type y{"y"};
377     pp_type2 z{"z"};
378     pp_type3 a{"a"};
379     pp_type4 b{"b"};
380     BOOST_CHECK((std::is_same<decltype(x.degree()), int>::value));
381     BOOST_CHECK((std::is_same<decltype(y.degree()), integer>::value));
382     BOOST_CHECK((std::is_same<decltype(z.degree()), long>::value));
383     BOOST_CHECK((std::is_same<decltype(a.degree()), int>::value));
384     BOOST_CHECK((std::is_same<decltype(b.degree()), rational>::value));
385 }
386