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: sage-8.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:

Status badges

Description (last modified by Ralf Stephan)

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 Ralf Stephan

Branch: u/rws/symbolic_factor___should_do_integer_factorisation_of_integers_rationals

comment:2 Changed 6 years ago by Ralf Stephan

Authors: Ralf Stephan
Commit: ac3d7cb0574701f2f5d94fa1e3b34239237674cd
Description: modified (diff)
Status: newneeds_review
Summary: Symbolic factor() should do integer factorisation of integers/rationalsSymbolic factor_li8st() should do integer factorisation of integers/rationals

New commits:

ac3d7cb21067: do ZZ/QQ factorization in ex.factor_list()

comment:3 Changed 6 years ago by Ralf Stephan

Summary: Symbolic factor_li8st() should do integer factorisation of integers/rationalsSymbolic factor_list() should do integer factorisation of integers/rationals

comment:4 Changed 6 years ago by Travis Scrimshaw

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 Nils Bruin

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 that self.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^2-5)).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 git

Commit: ac3d7cb0574701f2f5d94fa1e3b34239237674cdeca869e3fa641f8d8f6e4a4ed4fe47ec6745cde2

Branch pushed to git repo; I updated commit sha1. New commits:

eca869e21067: extend functionality

comment:7 Changed 6 years ago by Vincent Delecroix

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 Ralf Stephan

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 Nils Bruin

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: non-principal ideal in factorization
sage:  SR(2).pyobject().factor()
2
sage: (2+I-I).pyobject().factor() 
(-I) * (I + 1)^2

comment:10 Changed 6 years ago by Ralf Stephan

Status: needs_reviewneeds_work

comment:11 Changed 5 years ago by Ralf Stephan

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 Ralf Stephan

Branch: u/rws/symbolic_factor___should_do_integer_factorisation_of_integers_rationalsu/rws/21067

comment:13 Changed 5 years ago by Ralf Stephan

Authors: Ralf StephanRalf Stephan, Vincent Delecroix
Commit: eca869e3fa641f8d8f6e4a4ed4fe47ec6745cde24769429fe76a63b3a8165c420e23c806fa501329
Milestone: sage-7.3sage-8.0
Status: needs_workneeds_review

I used Vincent's code for a new version that tries also to separate the content in a univariate polynomial.


New commits:

476942921067: Symbolic factor_list() should do integer factorisation of

comment:14 Changed 5 years ago by git

Commit: 4769429fe76a63b3a8165c420e23c806fa5013298091ff3190ed0eeaf63821331bb6bfd728a5d8eb

Branch pushed to git repo; I updated commit sha1. New commits:

8091ff3Merge branch 'develop' into t/21067/21067

comment:15 Changed 5 years ago by Ralf Stephan

Status: needs_reviewneeds_work

Doctest errors, see patchbot.

comment:16 Changed 5 years ago by git

Commit: 8091ff3190ed0eeaf63821331bb6bfd728a5d8eba821fb6f91e6b8284eb492dcd4baf59c4cb9fe84

Branch pushed to git repo; I updated commit sha1. New commits:

933a75fMerge branch 'develop' into t/21067/21067
a821fb621067: simplification, doctest fix

comment:17 Changed 5 years ago by Ralf Stephan

Milestone: sage-8.0sage-8.2
Status: needs_workneeds_review

comment:18 Changed 4 years ago by Daniel Krenn

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 ;) )

Note: See TracTickets for help on using tickets.