On Monday 18 August 2008 12:06:06 pm Bill Hart wrote: > Doh, there's another simple way. Maybe Joel already does this. Simply > substitute a large prime or sufficiently high power of 2 and take the > square root of the resulting integer. Read off the square root of the > polynomial from the p-adic expansion of the square root. This should > be asymptotically fast and has the advantage of being easy to > implement. It's not necessarily as fast as the power series way, but > should be relatively quick in practice. Guaranteeing you picked the > prime large enough without checking the result at the end is probably > hard though. > > Sorry Joel I didn't read your patch yet, but given that this is a > method you championed for polynomial factorisation I'm guessing you > already thought of it.
Yep, I should've thought of that. No, I didn't do it that way. One strike against that method is it's not so general for different base rings (unless there is another trick I'm missing). My implementation works unchanged against number fields, finite fields, QQ, ZZ modulo some bugs I found and trac'ed in various base rings. -- Joel --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
