Square root of a polynomial
Use single point evaluation to transform the polynomial square root problem into the integer square root problem. Then find the integer square root and use to reconstruct the polynomial .
Create a problem from its solution.
> ans := randpoly(x,degree=9,dense,coeffs=rand(10^8));
> que := sort(expand(ans^2));
Bound the coefficients in the answer.
> L := length(maxnorm(que));
> M := 10^(iquo(L,2)+1);
Convert the polynomial problem to an integer problem.
> queM := subs(x=M,que);
Compute the integer square root. Note that both the input number and the output number to the integer square root procedure contain numbers with more than 16 digits.
> ansM := isqrt(queM);
Check the integer square root.
> check1 := queM-ansM^2;
Convert the integer to a polynomial.
> ans1 := sort(genpoly(ansM,M,x));
Check the answer.
> check2 := ans-ans1;