id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
20571 Newton method for nth_root of polynomial Vincent Delecroix "In #20086 a `nth_root` method for polynomial was implemented using factorization. But we can use Newton method for that!
It is faster than factorization even over ZZ where factor is highly optimized:
{{{
sage: x = polygen(ZZ)
sage: p = x**14 + x**3 - 12
sage: q = p**13
sage: %timeit _ = q.nth_root(13)
1000 loops, best of 3: 416 µs per loop
sage: %timeit _ = q.factor()
1000 loops, best of 3: 895 µs per loop
sage: q = p**37
sage: %timeit _ = q.nth_root(37)
1000 loops, best of 3: 1.17 µs per loop
sage: %timeit _ = q.factor()
100 loops, best of 3: 3.92 ms per loop
}}}
And the Newton method also works over polynomial when factorization is not implemented
{{{
sage: R1. = QQ[]
sage: R2. = R1[]
sage: R3. = R2[]
sage: q = (x+y+z)**3
sage: q.factor()
Traceback (most recent call last):
...
NotImplementedError:
sage: q.nth_root(3)
z + y + x
}}}" enhancement closed major sage-7.3 algebra fixed Nils Bruin Benjamin Hackl Kiran Kedlaya Vincent Delecroix Bruno Grenet N/A 24ffc9fca48ab2ce4123ba83cefe5543a11114c8 24ffc9fca48ab2ce4123ba83cefe5543a11114c8