[VA] SRC #012b - Then and Now: Root

[Albert Chan]

It may help to explain PeterP's root squaring program.
This was a PM I sent to PeterP, and other members.

Albert Chan Wrote:Instead of min abs P roots, we solve for max abs Q root, Q(x) = P(1/x)

Graeffe's root squaring method (next row roots = previous roots^2)

We only show top 3 coefficients, because we only care for Q max abs root

q = [2,3,5,7,11,13,17,19,23,29, ...] // assumed infinite degree polynomial
→ [2^2, 11, 27]
→ [2^4, 95, 303]
→ [2^8, 671, 7775]
→ [2^16, 3.530559E6, 1.01291839E8]
→ [2^32, 8.11677068927E11, 4.099840909585279E15]
→ [2^64, 3.455854558672141E25, 1.816641529875401E31]
→ [2^128, −5.240706455638273E50, 2.748844184968018E62]
→ [2^256, 8.757340043013178E100, 7.559454552508339E124]
→ [2^512, 9.837400259693430E201, 5.714553957282261E249]
...

2nd column are not "pure squares" (note the negative sign), but 3rd column is.
Thus, roots to seek are complex conjugates.
Assuming roots are well separated now:

max abs Q root = surd(5.714553957282261E249/2^512, 512*2) = 1.2399046971021601
min abs P root = 1 / (max abs Q root) = 0.8065135992606103

---

[VA012b] is similar to [VA012a], a diffusion problem.
Root Squaring process also based from its neighbor cells.

b[n] = a[n]^2
b[n-1] = -a[n-1]^2 + 2*a[n]*a[n-2]
b[n-2] = +a[n-2]^2 - 2*a[n-1]*a[n-3] + 2*a[n]*a[n-4]
...

By the time big primes effect diffused to the top, its effects are miniscule.