Opened 3 years ago
Last modified 9 months ago
#21067 needs_review defect
Symbolic factor_list() should do integer factorisation of integers/rationals
Reported by:  rws  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  symbolics  Keywords:  
Cc:  Merged in:  
Authors:  Ralf Stephan, Vincent Delecroix  Reviewers:  Daniel Krenn 
Report Upstream:  N/A  Work issues:  
Branch:  u/rws/21067 (Commits)  Commit:  a821fb6f91e6b8284eb492dcd4baf59c4cb9fe84 
Dependencies:  Stopgaps: 
Description (last modified by )
Let symbolic factor_list()
do integer factorisation if given an integer or fraction.
sage: SR(50).factor_list() [(50, 1)] sage: SR(49/100).factor_list() [(49/100, 1)]
Too much surprise for new users.
Change History (18)
comment:1 Changed 3 years ago by
 Branch set to u/rws/symbolic_factor___should_do_integer_factorisation_of_integers_rationals
comment:2 Changed 3 years ago by
 Commit set to ac3d7cb0574701f2f5d94fa1e3b34239237674cd
 Description modified (diff)
 Status changed from new to needs_review
 Summary changed from Symbolic factor() should do integer factorisation of integers/rationals to Symbolic factor_li8st() should do integer factorisation of integers/rationals
comment:3 Changed 3 years ago by
 Summary changed from Symbolic factor_li8st() should do integer factorisation of integers/rationals to Symbolic factor_list() should do integer factorisation of integers/rationals
comment:4 Changed 3 years ago by
One minor thing: could you move the import into the factor_list
method? I worry that this could lead to import hell.
comment:5 Changed 3 years ago by
Two comments:
 I don't think SR needs to be imported at all. The very fact that we land in this
factor_list
implementation should mean thatself.parent()
should be SR. And if it isn't, that's probably the better parent to use anyway.
 If we're going to do this anyway, I think it's better if we have
sage: (5/3*x/(x+1)).factor_list() [(x + 1, 1), (x, 1), (5, 1), (3,1)]
because it's closer to the idea that the factorisation of a product U*V has a tendency to be the concatenation of the factorisations of U and V.
It should be clear that factor_list
just returns *a* factorisation:
sage: ((sqrt(5)+1)^2*(x^25)).expand_rational().factor_list() [(x^2  5, 1), (sqrt(5) + 3, 1), (2, 1)]
but keeping the convention that we factor rational numbers into their prime factors should be fine and could be nice for newbies.
comment:6 Changed 3 years ago by
 Commit changed from ac3d7cb0574701f2f5d94fa1e3b34239237674cd to eca869e3fa641f8d8f6e4a4ed4fe47ec6745cde2
Branch pushed to git repo; I updated commit sha1. New commits:
eca869e  21067: extend functionality

comment:7 Changed 3 years ago by
Instead of having a special check and a special method for integer/rationals couldn't we use something simpler and more generic like
def _factorization_from_pyobject(self): try: a = self.pyobject() except TypeError: return try: f = a.factor() except (AttributeError, NotImplementedError): return # from here I assume that a is a Sage object which might not be the case... P = self.parent() facs = [(P(p), P(e)) for p,e in f] if f.unit().is_one(): return facs else: return [(P(f.unit()), P(1))] + facs
comment:8 Changed 3 years ago by
Vincent, if you think it's better, then please go ahead on a new branch. I'm not so deep in Python that I could object.
comment:9 Changed 3 years ago by
I think "factor" in general could be a little fickle to depend on:
sage: K.<a>=NumberField(x^2+5) sage: K(2).factor() ArithmeticError: nonprincipal ideal in factorization sage: SR(2).pyobject().factor() 2 sage: (2+II).pyobject().factor() (I) * (I + 1)^2
comment:10 Changed 3 years ago by
 Status changed from needs_review to needs_work
comment:11 Changed 3 years ago by
I think this ticket should also do:
sage: (2+6*x).factor_list() [(3*x + 1, 1), (2, 1)]
comment:12 Changed 3 years ago by
 Branch changed from u/rws/symbolic_factor___should_do_integer_factorisation_of_integers_rationals to u/rws/21067
comment:13 Changed 3 years ago by
 Commit changed from eca869e3fa641f8d8f6e4a4ed4fe47ec6745cde2 to 4769429fe76a63b3a8165c420e23c806fa501329
 Milestone changed from sage7.3 to sage8.0
 Status changed from needs_work to needs_review
I used Vincent's code for a new version that tries also to separate the content in a univariate polynomial.
New commits:
4769429  21067: Symbolic factor_list() should do integer factorisation of

comment:14 Changed 2 years ago by
 Commit changed from 4769429fe76a63b3a8165c420e23c806fa501329 to 8091ff3190ed0eeaf63821331bb6bfd728a5d8eb
Branch pushed to git repo; I updated commit sha1. New commits:
8091ff3  Merge branch 'develop' into t/21067/21067

comment:15 Changed 2 years ago by
 Status changed from needs_review to needs_work
Doctest errors, see patchbot.
comment:16 Changed 2 years ago by
 Commit changed from 8091ff3190ed0eeaf63821331bb6bfd728a5d8eb to a821fb6f91e6b8284eb492dcd4baf59c4cb9fe84
comment:17 Changed 2 years ago by
 Milestone changed from sage8.0 to sage8.2
 Status changed from needs_work to needs_review
comment:18 Changed 9 months ago by
 Reviewers set to Daniel Krenn
LGTM, I only have one comment:
+ raise ValueError
This is only used internally, so it might be good to consider a customized exception:
class CannotFactor(RuntimeError): pass
And yes, I think RuntimeError
is more appropriate (but if you insist on ValueError
then I am good with it as well, although wanting to hear your arguments for that ;) )
New commits:
21067: do ZZ/QQ factorization in ex.factor_list()