Changes between Initial Version and Version 2 of Ticket #20571
 Timestamp:
 May 8, 2016, 2:16:46 AM (7 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Ticket #20571 – Description
initial v2 1 1 We can use Newton method to compute nth root of polynomials. In all (?) cases, this should be much more efficient than relying on factorisation. 2 3 An example of a x4 faster compared to factorization 4 {{{ 5 sage: p = x**14 + x**3  12 6 7 sage: q = p**13 8 sage: %timeit _ = nth_root(q, 13) 9 1000 loops, best of 3: 216 µs per loop 10 sage: %timeit _ = q.factor() 11 1000 loops, best of 3: 895 µs per loop 12 13 sage: q = p**37 14 sage: %timeit _ = nth_root(q, 37) 15 1000 loops, best of 3: 625 µs per loop 16 sage: %timeit _ = q.factor() 17 100 loops, best of 3: 3.92 ms per loop 18 }}}