Changes between Version 3 and Version 7 of Ticket #20571


Ignore:
Timestamp:
May 24, 2016, 1:10:37 AM (7 years ago)
Author:
Vincent Delecroix
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #20571

    • Property Status changed from new to needs_review
    • Property Dependencies changed from #20086 to
    • Property Branch changed from to u/vdelecroix/20571
    • Property Milestone changed from sage-7.2 to sage-7.3
    • Property Commit changed from to 530a5639eb44d9f6feccb1b4d382ca356faf3146
  • Ticket #20571 – Description

    v3 v7  
    1 We can use Newton method to compute n-th root of polynomials. In all (?) cases, this should be much more efficient than relying on factorisation.
     1We can use Newton method to compute n-th root of polynomials.
    22
    3 Much faster than factorization
     3It is faster than factorization even over ZZ where factor is highly optimized:
    44{{{
     5sage: x = polygen(ZZ)
    56sage: p = x**14 + x**3 - 12
    67
    78sage: q = p**13
    8 sage: %timeit _ = nth_root(q, 13)
    9 1000 loops, best of 3: 216 µs per loop
     9sage: %timeit _ = q.nth_root(13)
     101000 loops, best of 3: 416 µs per loop
    1011sage: %timeit _ = q.factor()
    11121000 loops, best of 3: 895 µs per loop
    1213
    1314sage: q = p**37
    14 sage: %timeit _ = nth_root(q, 37)
    15 1000 loops, best of 3: 625 µs per loop
     15sage: %timeit _ = q.nth_root(37)
     161000 loops, best of 3: 1.17 µs per loop
    1617sage: %timeit _ = q.factor()
    1718100 loops, best of 3: 3.92 ms per loop
    1819}}}
     20And the Newton method also works over polynomial when factorization is not implemented
     21{{{
     22sage: R1.<x> = QQ[]
     23sage: R2.<y> = R1[]
     24sage: R3.<z> = R2[]
     25sage: q = (x+y+z)**3
     26sage: q.factor()
     27Traceback (most recent call last):
     28...
     29NotImplementedError:
     30sage: q.nth_root(3)
     31z + y + x
     32}}}