Opened 6 years ago
Last modified 4 years ago
#21067 needs_review defect
Symbolic factor_list() should do integer factorisation of integers/rationals
Reported by:  Ralf Stephan  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, GitHub, GitLab)  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 6 years ago by
Branch:  → u/rws/symbolic_factor___should_do_integer_factorisation_of_integers_rationals 

comment:2 Changed 6 years ago by
Authors:  → Ralf Stephan 

Commit:  → ac3d7cb0574701f2f5d94fa1e3b34239237674cd 
Description:  modified (diff) 
Status:  new → needs_review 
Summary:  Symbolic factor() should do integer factorisation of integers/rationals → Symbolic factor_li8st() should do integer factorisation of integers/rationals 
comment:3 Changed 6 years ago by
Summary:  Symbolic factor_li8st() should do integer factorisation of integers/rationals → Symbolic factor_list() should do integer factorisation of integers/rationals 

comment:4 Changed 6 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 6 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 6 years ago by
Commit:  ac3d7cb0574701f2f5d94fa1e3b34239237674cd → eca869e3fa641f8d8f6e4a4ed4fe47ec6745cde2 

Branch pushed to git repo; I updated commit sha1. New commits:
eca869e  21067: extend functionality

comment:7 Changed 6 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 6 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 6 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 6 years ago by
Status:  needs_review → needs_work 

comment:11 Changed 5 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 5 years ago by
Branch:  u/rws/symbolic_factor___should_do_integer_factorisation_of_integers_rationals → u/rws/21067 

comment:13 Changed 5 years ago by
Authors:  Ralf Stephan → Ralf Stephan, Vincent Delecroix 

Commit:  eca869e3fa641f8d8f6e4a4ed4fe47ec6745cde2 → 4769429fe76a63b3a8165c420e23c806fa501329 
Milestone:  sage7.3 → sage8.0 
Status:  needs_work → 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 5 years ago by
Commit:  4769429fe76a63b3a8165c420e23c806fa501329 → 8091ff3190ed0eeaf63821331bb6bfd728a5d8eb 

Branch pushed to git repo; I updated commit sha1. New commits:
8091ff3  Merge branch 'develop' into t/21067/21067

comment:16 Changed 5 years ago by
Commit:  8091ff3190ed0eeaf63821331bb6bfd728a5d8eb → a821fb6f91e6b8284eb492dcd4baf59c4cb9fe84 

comment:17 Changed 5 years ago by
Milestone:  sage8.0 → sage8.2 

Status:  needs_work → needs_review 
comment:18 Changed 4 years ago by
Reviewers:  → 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()