James Wanless on Sun, 13 Mar 2011 16:04:43 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Polroots/mod suggestion |
On 13 Mar 2011, at 14:45, Bill Allombert wrote:
On Sun, Mar 13, 2011 at 12:53:15PM +0000, James Wanless wrote:(Right, hopefully I really do mean to post to _this_ list this time :)I wonder if the devs would be interested in the following suggestion for finding roots of a general nth order polynomial, or same mod p: The idea is basically recursive completion of the square ie, solve for roots using the standard quadratic solution formula, but iterated. Each level of iteration would allow equations of up to 2^nth order to be solved, as n++How this is supposed to work ?
Maybe I should have used the word "nested' rather than 'iterated'...
This would necessitate the introduction/evaluation of "Wanlessians", defined recursively s.t. W[n] = sqrt(-W[n-1]). So for instance, W[0]=1, W[1]=i, W[2]=(-1+i)/(sqrt(2)), ... [in the mod p case, W[n] = sqrt(-W[n-1]) mod p] If this works, and you can successfully implement it in code, II would be quite surprised if it worked.
Am I correct in saying that every polynomial (/mod p) of degree d will have exactly d (including multiple) roots? If so, then the current implementation in PARI (and mine :), using Berlekamp, doesn't always find them all.
This was a suggestion for improvement...
Cheers, Bill.