C #include #include #include #include #include

/* complex mul: (a + bi)(c + di) = (ac - bd) + (bc + ad)i div (a + bi)/(c + di) = ((ac + bd) + (bc - ad)i)/(c^2 + d^2) */ void hornerZ(double &resRe, double &resIm, double xRe, double xIm, int n, double *P) { resIm = 0; if (n = 0; i--) { double origResRe = resRe; resRe = (resRe*xRe - resIm*xIm); resIm = resIm*xRe + origResRe*xIm; resRe += P[i];

void dhornerZ(double &resRe, double &resIm, double a, double b, int n, double *P) { resIm = 0; if (n = 1; i--) { double origResRe = resRe; resRe = (resRe*a - resIm*b); resIm = resIm*a + origResRe*b; resRe += P[i] * i;

void d2hornerZ(double &resRe, double &resIm, double a, double b, int n, double *P) { resIm = 0; if (n = 2; i--) { double origResRe = resRe; resRe = (resRe*a - resIm*b); resIm = resIm*a + origResRe*b; resRe += P[i] * i *(i - 1);

void dnthhornerZ(double &resRe, double &resIm, double a, double b, int n, double *P, int nth) { resIm = 0; if (nth > n) { resRe = 0; return; } double factor = 1; for (int j = n; j > n - nth; j--) factor *= j; resRe = P[n] * factor; for (int i = n - 1; i >= nth; i--) { double origResRe = resRe; resRe = (resRe*a - resIm*b); resIm = resIm*a + origResRe*b; factor = 1; for (int j = i; j > i - nth; j--) factor *= j; resRe += P[i] * factor;

double estimEps(double x, int n, double *P) { if (n= 0; i--) { value *= x; double esterror1 = esterror*x; double esterror2 = 0.35* value; esterror = sqrt(esterror1*esterror1 + esterror2*esterror2); value += P[i]; esterror = std::max(esterror, fabs(0.35*value)); } return esterror; }

double destimEps(double x, int n, double *P, int nth) { if (nth > n) return 0; double factor = 1; for (int j = n; j > n - nth; j--) factor *= j; double value = P[n] * factor; double esterror = 0; for (int i = n - 1; i >= 0; i--) { value *= x; double esterror1 = esterror*x; double esterror2 = 0.35* value; esterror = sqrt(esterror1*esterror1 + esterror2*esterror2); factor = 1; for (int j = i; j > i - nth; j--) factor *= j; value += P[i] * factor; esterror = std::max(esterror, fabs(0.35*value)); } return esterror; }

int dLaguerreZ(double &resRe, double &resIm, double xRe, double xIm, int n, double *P, int nth, double baseEstError) { int loopCnt = 0; if (n <= nth) { resRe = NAN; resIm = NAN; return loopCnt; } while (true) { double estError = destimEps(sqrt(xRe*xRe + xIm*xIm), n, P, nth); double hRe, hIm; dnthhornerZ(hRe, hIm, xRe, xIm, n, P, nth); double dhRe, dhIm; dnthhornerZ(dhRe, dhIm, xRe, xIm, n, P, nth + 1); if (sqrt(hRe*hRe + hIm*hIm) < DBL_EPSILON*sqrt(dhRe*dhRe + dhIm*dhIm + estError*estError))

double tryRe, tryIm; dLaguerreZ(tryRe, tryIm, xRe, xIm, n, P, nth + 1, estError); if (!isnan(tryRe))

xRe = tryRe; xIm = tryIm;

break;

double GRe, GIm; double denomh = hRe*hRe + hIm*hIm; GRe = (dhRe*hRe + dhIm*hIm) / denomh; GIm = (dhIm*hRe - dhRe*hIm) / denomh; double G2Re, G2Im; G2Re = GRe*GRe - GIm*GIm; G2Im = 2 * GRe * GIm; double d2hRe, d2hIm; dnthhornerZ(d2hRe, d2hIm, xRe, xIm, n, P, nth + 2); double GRe2, GIm2; GRe2 = (d2hRe*hRe + d2hIm*hIm) / denomh; GIm2 = (d2hIm*hRe - d2hRe*hIm) / denomh; double HRe, HIm; HRe = G2Re - GRe2; HIm = G2Im - GIm2; double vRe, vIm; vRe = (n - 1)*(n*HRe - G2Re); vIm = (n - 1)*(n*HIm - G2Im); double modv = sqrt(vRe*vRe + vIm*vIm); double sRe, sIm; sRe = sqrt((modv + vRe) / 2); sIm = sqrt((modv - vRe) / 2); if (vIm denom2Re*denom2Re + denom2Im*denom2Im)

denomRe = denom1Re; denomIm = denom1Im;

else

denomRe = denom2Re; denomIm = denom2Im;

double aRe, aIm; double denoma = denomRe*denomRe + denomIm*denomIm; aRe = n*denomRe / denoma; aIm = -n*denomIm / denoma; if (sqrt(aRe*aRe + aIm*aIm) = 2*DBL_EPSILON*baseEstError)

resRe = NAN; resIm = NAN; return loopCnt;

resRe = xRe; resIm = xIm; return loopCnt; }

int LaguerreMZ(double &resRe, double &resIm, double xRe, double xIm, int n, double *P) { int loopCnt = 0; if (n <= 0) { resRe = NAN; resIm = NAN; return loopCnt; } while (true) { double estError = estimEps(sqrt(xRe*xRe + xIm*xIm), n, P); double hRe, hIm; hornerZ(hRe, hIm, xRe, xIm, n, P); double dhRe, dhIm; dhornerZ(dhRe, dhIm, xRe, xIm, n, P); if (sqrt(hRe*hRe + hIm*hIm) < DBL_EPSILON*sqrt(dhRe*dhRe + dhIm*dhIm + 1.4*estError*estError))

double tryRe, tryIm; dLaguerreZ(tryRe, tryIm, xRe, xIm, n, P, 1, estError); if (!isnan(tryRe))

xRe = tryRe; xIm = tryIm;

break;

double GRe, GIm; double denomh = hRe*hRe + hIm*hIm; GRe = (dhRe*hRe + dhIm*hIm) / denomh; GIm = (dhIm*hRe - dhRe*hIm) / denomh; double G2Re, G2Im; G2Re = GRe*GRe - GIm*GIm; G2Im = 2 * GRe * GIm; double d2hRe, d2hIm; d2hornerZ(d2hRe, d2hIm, xRe, xIm, n, P); double GRe2, GIm2; GRe2 = (d2hRe*hRe + d2hIm*hIm) / denomh; GIm2 = (d2hIm*hRe - d2hRe*hIm) / denomh; double HRe, HIm; HRe = G2Re - GRe2; HIm = G2Im - GIm2; double vRe, vIm; vRe = (n - 1)*(n*HRe - G2Re); vIm = (n - 1)*(n*HIm - G2Im); double modv = sqrt(vRe*vRe + vIm*vIm); double sRe, sIm; sRe = sqrt((modv + vRe) / 2); sIm = sqrt((modv - vRe) / 2); if (vIm denom2Re*denom2Re + denom2Im*denom2Im)

denomRe = denom1Re; denomIm = denom1Im;

else

denomRe = denom2Re; denomIm = denom2Im;

double aRe, aIm; double denoma = denomRe*denomRe + denomIm*denomIm; aRe = n*denomRe / denoma; aIm = -n*denomIm / denoma; if (sqrt(aRe*aRe + aIm*aIm) < 2 * DBL_EPSILON*sqrt(xRe*xRe + xIm*xIm))

xRe -= 0.5*aRe; xIm -= 0.5*aIm; break;

xRe -= aRe; xIm -= aIm; loopCnt++; } resRe = xRe; resIm = xIm; return loopCnt; }

//const int degP = 6; //double P[degP + 1] = { 36,-48,-3,17,2,-5,1 }; //(x^2 + 3·x + 3)(x-1)(x-2)(x-2)(x-3) const int degP = 8; double P[degP + 1] = {1,-8,28,-56,70,-56,28,-8,1};//(x - 1) ^ 8

int main() { double a, b; LaguerreMZ(a,b, 0.99, 0, degP, P); printf("%.16f %.16f\n", a,b); return 0; }