Graeffe's root squaring method

[Albert Chan]

11-23-2022, 01:26 PM

Werner Wrote:

Albert Chan Wrote:We may get answer directly with plain root squaring.
This post may be relevant.

Oh no, it is certainly relevant, and may *aid* in determining the answer. It is the only method that will give us an idea of what the real min abs root is. You got 12 correct digits after all - but only because you knew the answer already? To verify the correctness, you would have to square further once or twice, but you'd run into overflow.

Nice to know prime gap trick work

This is a quick and dirty way to do root powering. (symbolically, thus slow)
BTW, I had trouble translate a[::n] to HP Prime Cas.

Code:

rootpow(a,n) := { local w;
     w := exp(2*pi/n*i);
     a := symb2poly(product(horner(a,x*w^k),k=0..n-1));
     return normal(a[::n])
}

Below is for illustration purpose only.
We could use integer coefficients without worrying about overflow.
Or, numerically by XCas mpfr float, with exponents range into billions.

XCas> p := makelist(ithprime,124+1,1,-1)      → [691,683,677,673,661,...]
XCas> k, q := 2, reverse(p - p[1:]) .* .25       → 2, [0.5,0.25,0.5,0.5,1.0,...]
XCas> q := rootpow(q, 2) :; k*=2; surd(q[0]/q[2],k), surd(q[2]/q[4],k)

Repeat last expression until k=1024, we have:

Code:

4   , 0.707106781187, 0.816496580928
8   , 0.725699929618, 0.874520449757
16  , 0.812448915479, 0.827434355334
32  , 0.79583362162 , 0.901285129669
64  , 0.80643033679 , 0.852976123366
128 , 0.805938612598, 0.850214544854
256 , 0.806514291756, 0.851660093256
512 , 0.80651360183 , 0.851658832026
1024, 0.806513599261, 0.851662531880

Final check for min abs root does not require full root squaring.
For next P 2 minimum roots, we need 4*2+1 = 9 columns
(same idea for the next after, we need 8*2+1 = 17 columns)

XCas> q := q[:9]
XCas> q := rootpow(q, 2) :; k*=2; surd(q[0]/q[2],k), surd(q[2]/q[4],k)

2048, 0.806513599261, 0.85166253289      # P min abs root, and 2nd min

For rough estimate, P 2nd min is probably more important than actual min.
If we get a root with abs below its 2nd min, we've locked to min root.
All is left is to improve the root, to required accuracy.