Changes between Initial Version and Version 2 of Ticket #20571


Ignore:
Timestamp:
May 8, 2016, 2:16:46 AM (7 years ago)
Author:
Vincent Delecroix
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #20571 – Description

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