Fix for UnivariatePolynomial::eq #847

myluszczak · 2016-03-05T00:20:26Z

The current implementation of UnivariatePolynomial::__eq__ checks if the dictionaries of the two polynomials are exactly equal, and will return false if comparing polynomials with the dictionaries {{0,0},{1,2}} and {{1,2}} representing 0 + 2x and 2x respectively. Since addition does not remove the entries of a dictionary corresponding to terms that have zero coefficients, this can lead to a situation where SymEngine tells us that (x+1) + (x-1) != 2x, as shown below.
test.zip

My implementation replaces the call to map_uint_mpz_eq with a call to poly_dict_map_uint_mpz_eq, which returns true if two dictionaries are the same (excluding those entries where the coefficient is zero.)

certik · 2016-03-05T00:54:55Z

I wonder if we should just make sure when the polynomial is created, that it is always in a canonical form, so that then you can literally just compare the dictionaries?

@isuruf what do you think?

isuruf · 2016-03-05T02:56:45Z

Yes, that should be easier.
We can use UnivariatePolynomial::from_dict to do that. Current implementation is not necessary which checks if the dictionary size is 0 or 1, which is not needed. UnivariatePolynomial::from_dict should always return a polynomial.

… zero coefficients

myluszczak · 2016-03-05T05:35:07Z

@isuruf So, something like this?

If we do it this way, we should probably add code to is_canonical to check that the dictionary contains no terms with zero coefficients. This would make the canonical form of the polynomial "0" be a polynomial with an empty dictionary, which would require changing some code in the tester and some of the code in printer.cpp.

isuruf · 2016-03-05T05:37:04Z

@myluszczak, exactly. I think this looks good.

isuruf · 2016-03-05T05:37:20Z

symengine/polynomial.cpp

+    /*for(auto itter = dict.begin(); itter != dict.end(); itter++){
+        if(0 == itter->second)
+	    return false;
+    }*/


You can uncomment this code

isuruf · 2016-03-05T05:47:29Z

There are currently 3 ways of creating a polynomial.

UnivariatePolynomial(const RCP<const Symbol> &var, const unsigned int &degree, map_uint_mpz&& dict);
UnivariatePolynomial(const RCP<const Symbol> &var, const std::vector<integer_class> &v);
static RCP<const UnivariatePolynomial> from_dict(const RCP<const Symbol> &var, map_uint_mpz &&d);

Instead of that we can do,

UnivariatePolynomial(const RCP<const Symbol> &var, const unsigned int &degree, map_uint_mpz&& dict);
static RCP<const UnivariatePolynomial> from_vec(const RCP<const Symbol> &var, const std::vector<integer_class> &v);
static RCP<const UnivariatePolynomial> from_dict(const RCP<const Symbol> &var, map_uint_mpz &&d);

Only method 2 and 3 will call 1 and all other references to 1 will be replaced by 3.
What do you think?

myluszczak · 2016-03-05T06:35:27Z

@isuruf I think that's a good plan, and I'll put that in the next commit.

Thanks for the head's up on the redundant checks in get_args; I missed that when I copied the code form the original implementation of from_dict.

myluszczak · 2016-03-05T07:41:28Z

In the above commit I've done what I though would implement isuruf's idea above, however on my machine compilation stops when linking test_arit with the error message

[ 42%] Linking CXX executable test_arit
../../libsymengine.a(polynomial.cpp.o): In function `SymEngine::mul_uni_poly(Teuchos::RCP<SymEngine::UnivariatePolynomial const>, Teuchos::RCP<SymEngine::UnivariatePoly                                       nomial const>)':
/home/myluszcz/ECS193/SYMENGINE/symengine/symengine/polynomial.cpp:290: undefined reference to `SymEngine::UnivariatePolynomial::from_vec(Teuchos::RCP<SymEngine::Symbol                                        const> const&, std::vector<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, std::allocator<__gmp_expr<__mpz_struct [1], __mpz_struct [1]> > > const&)'
/home/myluszcz/ECS193/SYMENGINE/symengine/symengine/polynomial.cpp:292: undefined reference to `SymEngine::UnivariatePolynomial::from_vec(Teuchos::RCP<SymEngine::Symbol                                        const> const&, std::vector<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, std::allocator<__gmp_expr<__mpz_struct [1], __mpz_struct [1]> > > const&)'
../../libsymengine.a(series_generic.cpp.o): In function `SymEngine::UnivariatePolynomial::create(Teuchos::RCP<SymEngine::Symbol const> const&, std::vector<__gmp_expr<__                                       mpz_struct [1], __mpz_struct [1]>, std::allocator<__gmp_expr<__mpz_struct [1], __mpz_struct [1]> > > const&)':
/home/myluszcz/ECS193/SYMENGINE/symengine/symengine/polynomial.h:49: undefined reference to `SymEngine::UnivariatePolynomial::from_vec(Teuchos::RCP<SymEngine::Symbol co                                       nst> const&, std::vector<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, std::allocator<__gmp_expr<__mpz_struct [1], __mpz_struct [1]> > > const&)'
collect2: error: ld returned 1 exit status
symengine/tests/basic/CMakeFiles/test_arit.dir/build.make:104: recipe for target 'symengine/tests/basic/test_arit' failed
make[2]: *** [symengine/tests/basic/test_arit] Error 1
CMakeFiles/Makefile2:381: recipe for target 'symengine/tests/basic/CMakeFiles/test_arit.dir/all' failed
make[1]: *** [symengine/tests/basic/CMakeFiles/test_arit.dir/all] Error 2
Makefile:138: recipe for target 'all' failed
make: *** [all] Error 2

Since it's late, I'm going to shower and go to bed.

isuruf · 2016-03-05T09:31:20Z

symengine/polynomial.cpp

+    return make_rcp<const UnivariatePolynomial>(var, (--(d.end()))->first, std::move(d));
+}
+
+RCP<const UnivariatePolynomial> from_vec(const RCP<const Symbol> &var, const std::vector<integer_class> &v){


Change the name to UnivariatePolynomial::from_vec

isuruf · 2016-03-05T11:23:33Z

Can you rebase on top of master and fix merge conflicts? @chenchfort should be able to help you out. If not let me know if you need my help.

shivamvats · 2016-03-06T04:24:42Z

@myluszczak Are you developing in debug mode?

myluszczak · 2016-03-06T04:50:10Z

@shivamvats Not in general, no. I just compiled and tested it in debug mode, though, and it still works on my machine. The main difference between the behavior of release and debug modes is that in debug mode we call the SYMENGINE_ASSERTs, right?

isuruf · 2016-03-06T05:19:56Z

symengine/polynomial.cpp

-                    {{var, integer(d.begin()->first)}});
+    for(auto itter = d.begin(); itter != d.end(); itter++){
+        if(integer_class(0) == itter->second)
+  	    d.erase(itter);


This is probably what is causing the segfault. If you delete while iterating, the iterator becomes invalid.

myluszczak · 2016-03-06T05:33:11Z

@isuruf So, a better implementation would be to create a new dictionary and only add to that if the coefficient is nonzero?

isuruf · 2016-03-06T09:09:48Z

symengine/polynomial.cpp

    }
+    if(dict_.empty())


Space after if

isuruf · 2016-03-06T18:57:28Z

+1. If you can rebase on top of master, we can get this merged

myluszczak · 2016-03-06T19:03:23Z

I'm a bit new to git. That'd be git rebase master in the polydicteq branch, right?

isuruf · 2016-03-06T19:04:27Z

Yes

char-chen · 2016-03-06T19:04:47Z

You'll need to resolve the conflict.

myluszczak · 2016-03-06T19:05:49Z

@chenchfort wait, which conflict?

char-chen · 2016-03-06T19:07:45Z

Have you rebased? Did it complain about conflicts?

myluszczak · 2016-03-06T19:08:40Z

I'm rebasing now, and it is complaining about conflicts currently. I am currently resolving them.

myluszczak · 2016-03-06T20:36:46Z

@chenchfort Alright, so I finished the rebase, but now git refuses to push

``To https://github.com/chenchfort/symengine
! [rejected] polydicteq -> polydicteq (non-fast-forward)
error: failed to push some refs to 'https://github.com/chenchfort/symengine'
hint: Updates were rejected because the tip of your current branch is behind
hint: its remote counterpart. Integrate the remote changes (e.g.
hint: 'git pull ...') before pushing again.
hint: See the 'Note about fast-forwards' in 'git push --help' for details.

--resolved

char-chen · 2016-03-06T20:39:19Z

Ok force pushed. Looks good.

isuruf · 2016-03-07T02:45:35Z

Closed in favour of #855

char-chen and others added 12 commits January 26, 2016 22:32

Adding wiki

ee78f3f

rm wiki

31bee36

Merge remote-tracking branch 'upstream/master'

86dea6e

Merge remote-tracking branch 'upstream/master'

07dfd38

Merge remote-tracking branch 'upstream/master'

8cd78bc

Merge remote-tracking branch 'upstream/master'

5f9c7a6

Merge remote-tracking branch 'upstream/master'

eb390e0

Merge remote-tracking branch 'upstream/master'

07daf45

Merge remote-tracking branch 'upstream/master'

17ef88c

Merge remote-tracking branch 'upstream/master'

199826b

Merge remote-tracking branch 'upstream/master'

13f9730

fix for UnivariatePolynomial::__eq__

ec35443

myluszczak mentioned this pull request Mar 5, 2016

UnivariatePolynomial::__eq__ gives (x+1) + (x-1) != 2x #848

Closed

myluszczak added 2 commits March 4, 2016 20:36

add_uni_poly now returns polynomial whose dictionary lacks terms with…

bf518ee

… zero coefficients

fixed UnivariatePolynomial::get_args()

2bf38b7

isuruf reviewed Mar 5, 2016
View reviewed changes

isuruf reviewed Mar 6, 2016
View reviewed changes

symengine/polynomial.cpp

}

if(dict_.empty())

Copy link

Member

isuruf Mar 6, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Space after if

myluszczak force-pushed the polydicteq branch from 399e428 to d4d5236 Compare March 6, 2016 20:38

myluszczak force-pushed the polydicteq branch from 7516542 to 2114377 Compare March 7, 2016 00:38

char-chen force-pushed the polydicteq branch from 2114377 to 2bf38b7 Compare March 7, 2016 02:40

isuruf mentioned this pull request Mar 7, 2016

Fix for UnivariatePolynomial::__eq__ #855

Merged

isuruf closed this Mar 7, 2016

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fix for UnivariatePolynomial::eq #847

Fix for UnivariatePolynomial::eq #847

myluszczak commented Mar 5, 2016

certik commented Mar 5, 2016

isuruf commented Mar 5, 2016

myluszczak commented Mar 5, 2016

isuruf commented Mar 5, 2016

isuruf Mar 5, 2016

isuruf commented Mar 5, 2016

myluszczak commented Mar 5, 2016

myluszczak commented Mar 5, 2016

isuruf Mar 5, 2016

isuruf commented Mar 5, 2016

shivamvats commented Mar 6, 2016

myluszczak commented Mar 6, 2016

isuruf Mar 6, 2016

myluszczak commented Mar 6, 2016

isuruf Mar 6, 2016

isuruf commented Mar 6, 2016

myluszczak commented Mar 6, 2016

isuruf commented Mar 6, 2016

char-chen commented Mar 6, 2016

myluszczak commented Mar 6, 2016

char-chen commented Mar 6, 2016

myluszczak commented Mar 6, 2016

myluszczak commented Mar 6, 2016

char-chen commented Mar 6, 2016

isuruf commented Mar 7, 2016

Fix for UnivariatePolynomial::__eq__ #847

Fix for UnivariatePolynomial::__eq__ #847

Conversation

myluszczak commented Mar 5, 2016

certik commented Mar 5, 2016

isuruf commented Mar 5, 2016

myluszczak commented Mar 5, 2016

isuruf commented Mar 5, 2016

isuruf Mar 5, 2016

Choose a reason for hiding this comment

isuruf commented Mar 5, 2016

myluszczak commented Mar 5, 2016

myluszczak commented Mar 5, 2016

isuruf Mar 5, 2016

Choose a reason for hiding this comment

isuruf commented Mar 5, 2016

shivamvats commented Mar 6, 2016

myluszczak commented Mar 6, 2016

isuruf Mar 6, 2016

Choose a reason for hiding this comment

myluszczak commented Mar 6, 2016

isuruf Mar 6, 2016

Choose a reason for hiding this comment

isuruf commented Mar 6, 2016

myluszczak commented Mar 6, 2016

isuruf commented Mar 6, 2016

char-chen commented Mar 6, 2016

myluszczak commented Mar 6, 2016

char-chen commented Mar 6, 2016

myluszczak commented Mar 6, 2016

myluszczak commented Mar 6, 2016

char-chen commented Mar 6, 2016

isuruf commented Mar 7, 2016

Fix for UnivariatePolynomial::eq #847

Fix for UnivariatePolynomial::eq #847