{"version":3,"file":"Roots.cjs","sources":["../../src/core/Roots.js"],"sourcesContent":["// Root finding algorithms\r\nimport { Cx } from \"./Complex.js\";\r\nimport { Poly } from \"./Polynomial.js\";\r\n\r\nfunction evalMonicAndDeriv(coeffsMonic, z){\r\n  const N = coeffsMonic.length - 1;\r\n  let p={re:1,im:0}, dp={re:0,im:0};\r\n  for(let k=1;k<=N;k++){ dp=Cx.add(Cx.mul(dp,z),p); p=Cx.add(Cx.mul(p,z),{re:coeffsMonic[k],im:0}); }\r\n  return {p,dp};\r\n}\r\n\r\nexport class Roots {\r\n  static aberthMonic(raw){\r\n    let i0=0; while(i0<raw.length-1 && Math.abs(raw[i0])<1e-18) i0++;\r\n    let cs = raw.slice(i0);\r\n    const N = cs.length - 1;\r\n    if (N <= 0) return [];\r\n    const a0 = cs[0];\r\n    cs = cs.map(c => c / a0); // monic [1, a1, ..., aN]\r\n\r\n    let maxRatio=0; for(let k=1;k<cs.length;k++) maxRatio=Math.max(maxRatio, Math.abs(cs[k]));\r\n    const r0 = Math.max(0.5, Math.min(1.5, 1+maxRatio));\r\n\r\n    const roots=new Array(N);\r\n    for(let k=0;k<N;k++){\r\n      const ang=2*Math.PI*(k+0.5)/N, jit=1+((k%2?1:-1)*1e-3);\r\n      roots[k]={re:r0*jit*Math.cos(ang), im:r0*jit*Math.sin(ang)};\r\n    }\r\n\r\n    const MAX_IT=200, TOL=1e-12, DEN_EPS=1e-14;\r\n    for(let it=0; it<MAX_IT; it++){\r\n      let moved=false;\r\n      for(let i=0;i<N;i++){\r\n        const zi=roots[i];\r\n        const {p,dp}=evalMonicAndDeriv(cs,zi);\r\n        let sumInv={re:0,im:0};\r\n        for(let j=0;j<N;j++) if(j!==i){\r\n          let dif=Cx.sub(zi,roots[j]);\r\n          const mag2=dif.re*dif.re+dif.im*dif.im;\r\n          if(mag2 < DEN_EPS*DEN_EPS) dif={re:dif.re+DEN_EPS, im:dif.im};\r\n          const inv={re:dif.re/(mag2||1e-300), im:-dif.im/(mag2||1e-300)};\r\n          sumInv=Cx.add(sumInv,inv);\r\n        }\r\n        const denom=Cx.sub(dp, Cx.mul(p,sumInv));\r\n        const delta=Cx.div(p,denom);\r\n        const ni=Cx.sub(zi,delta);\r\n        if(Math.hypot(ni.re-zi.re, ni.im-zi.im)>TOL) moved=true;\r\n        roots[i]=ni;\r\n      }\r\n      if(!moved) break;\r\n    }\r\n    return roots;\r\n  }\r\n\r\n  static dkScaled(raw){\r\n    let i0=0; while(i0<raw.length-1 && Math.abs(raw[i0])<1e-18) i0++;\r\n    const poly=raw.slice(i0);\r\n    const N=poly.length-1;\r\n    if(N<=0) return [];\r\n    const a0=poly[0];\r\n    const monic=poly.map(c=>c/a0);\r\n\r\n    const results=[];\r\n    for(const R of [0.8,1.1,1.5]){\r\n      const roots=new Array(N);\r\n      for(let k=0;k<N;k++){ const ang=2*Math.PI*(k+1)/N; roots[k]={re:R*Math.cos(ang), im:R*Math.sin(ang)}; }\r\n      for(let it=0;it<200;it++){\r\n        let moved=false;\r\n        for(let i=0;i<N;i++){\r\n          let denom={re:1,im:0};\r\n          for(let j=0;j<N;j++) if(i!==j) denom=Cx.mul(denom, Cx.sub(roots[i], roots[j]));\r\n          const f=Poly.evalRealAsc(monic, roots[i]);\r\n          const delta=Cx.div(f,denom);\r\n          const ni=Cx.sub(roots[i], delta);\r\n          if(Math.hypot(ni.re-roots[i].re, ni.im-roots[i].im)>1e-12) moved=true;\r\n          roots[i]=ni;\r\n        }\r\n        if(!moved) break;\r\n      }\r\n      results.push(...roots);\r\n    }\r\n    return results;\r\n  }\r\n}\r\n"],"names":["Cx","Poly"],"mappings":";;;;;AAAA;AAGA;AACA,SAAS,iBAAiB,CAAC,WAAW,EAAE,CAAC,CAAC;AAC1C,EAAE,MAAM,CAAC,GAAG,WAAW,CAAC,MAAM,GAAG,CAAC,CAAC;AACnC,EAAE,IAAI,CAAC,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,EAAE,EAAE,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,CAAC;AACpC,EAAE,IAAI,IAAI,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,EAAE,CAAC,EAAE,EAAE,CAACA,eAAE,CAAC,GAAG,CAACA,eAAE,CAAC,GAAG,CAAC,EAAE,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAACA,eAAE,CAAC,GAAG,CAACA,eAAE,CAAC,GAAG,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC,WAAW,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;AACrG,EAAE,OAAO,CAAC,CAAC,CAAC,EAAE,CAAC,CAAC;AAChB,CAAC;AACD;AACO,MAAM,KAAK,CAAC;AACnB,EAAE,OAAO,WAAW,CAAC,GAAG,CAAC;AACzB,IAAI,IAAI,EAAE,CAAC,CAAC,CAAC,CAAC,MAAM,EAAE,CAAC,GAAG,CAAC,MAAM,CAAC,CAAC,IAAI,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,EAAE,CAAC,CAAC,CAAC,KAAK,EAAE,EAAE,EAAE,CAAC;AACrE,IAAI,IAAI,EAAE,GAAG,GAAG,CAAC,KAAK,CAAC,EAAE,CAAC,CAAC;AAC3B,IAAI,MAAM,CAAC,GAAG,EAAE,CAAC,MAAM,GAAG,CAAC,CAAC;AAC5B,IAAI,IAAI,CAAC,IAAI,CAAC,EAAE,OAAO,EAAE,CAAC;AAC1B,IAAI,MAAM,EAAE,GAAG,EAAE,CAAC,CAAC,CAAC,CAAC;AACrB,IAAI,EAAE,GAAG,EAAE,CAAC,GAAG,CAAC,CAAC,IAAI,CAAC,GAAG,EAAE,CAAC,CAAC;AAC7B;AACA,IAAI,IAAI,QAAQ,CAAC,CAAC,CAAC,CAAC,IAAI,IAAI,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC,MAAM,CAAC,CAAC,EAAE,EAAE,QAAQ,CAAC,IAAI,CAAC,GAAG,CAAC,QAAQ,EAAE,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;AAC9F,IAAI,MAAM,EAAE,GAAG,IAAI,CAAC,GAAG,CAAC,GAAG,EAAE,IAAI,CAAC,GAAG,CAAC,GAAG,EAAE,CAAC,CAAC,QAAQ,CAAC,CAAC,CAAC;AACxD;AACA,IAAI,MAAM,KAAK,CAAC,IAAI,KAAK,CAAC,CAAC,CAAC,CAAC;AAC7B,IAAI,IAAI,IAAI,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC;AACxB,MAAM,MAAM,GAAG,CAAC,CAAC,CAAC,IAAI,CAAC,EAAE,EAAE,CAAC,CAAC,GAAG,CAAC,CAAC,CAAC,EAAE,GAAG,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE,EAAE,IAAI,CAAC,CAAC;AAC7D,MAAM,KAAK,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC,EAAE,CAAC,GAAG,CAAC,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,EAAE,EAAE,CAAC,EAAE,CAAC,GAAG,CAAC,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,CAAC,CAAC;AAClE,IAAI,CAAC;AACL;AACA,IAAI,MAAM,MAAM,CAAC,GAAG,EAAE,GAAG,CAAC,KAAK,EAAE,OAAO,CAAC,KAAK,CAAC;AAC/C,IAAI,IAAI,IAAI,EAAE,CAAC,CAAC,EAAE,EAAE,CAAC,MAAM,EAAE,EAAE,EAAE,CAAC;AAClC,MAAM,IAAI,KAAK,CAAC,KAAK,CAAC;AACtB,MAAM,IAAI,IAAI,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC;AAC1B,QAAQ,MAAM,EAAE,CAAC,KAAK,CAAC,CAAC,CAAC,CAAC;AAC1B,QAAQ,MAAM,CAAC,CAAC,CAAC,EAAE,CAAC,CAAC,iBAAiB,CAAC,EAAE,CAAC,EAAE,CAAC,CAAC;AAC9C,QAAQ,IAAI,MAAM,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,CAAC;AAC/B,QAAQ,IAAI,IAAI,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE,EAAE,GAAG,CAAC,GAAG,CAAC,CAAC;AACtC,UAAU,IAAI,GAAG,CAACA,eAAE,CAAC,GAAG,CAAC,EAAE,CAAC,KAAK,CAAC,CAAC,CAAC,CAAC,CAAC;AACtC,UAAU,MAAM,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC;AACjD,UAAU,GAAG,IAAI,GAAG,OAAO,CAAC,OAAO,EAAE,GAAG,CAAC,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC,OAAO,EAAE,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC,CAAC;AACxE,UAAU,MAAM,GAAG,CAAC,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,EAAE,IAAI,EAAE,MAAM,CAAC,EAAE,EAAE,CAAC,CAAC,GAAG,CAAC,EAAE,EAAE,IAAI,EAAE,MAAM,CAAC,CAAC,CAAC;AAC1E,UAAU,MAAM,CAACA,eAAE,CAAC,GAAG,CAAC,MAAM,CAAC,GAAG,CAAC,CAAC;AACpC,QAAQ,CAAC;AACT,QAAQ,MAAM,KAAK,CAACA,eAAE,CAAC,GAAG,CAAC,EAAE,EAAEA,eAAE,CAAC,GAAG,CAAC,CAAC,CAAC,MAAM,CAAC,CAAC,CAAC;AACjD,QAAQ,MAAM,KAAK,CAACA,eAAE,CAAC,GAAG,CAAC,CAAC,CAAC,KAAK,CAAC,CAAC;AACpC,QAAQ,MAAM,EAAE,CAACA,eAAE,CAAC,GAAG,CAAC,EAAE,CAAC,KAAK,CAAC,CAAC;AAClC,QAAQ,GAAG,IAAI,CAAC,KAAK,CAAC,EAAE,CAAC,EAAE,CAAC,EAAE,CAAC,EAAE,EAAE,EAAE,CAAC,EAAE,CAAC,EAAE,CAAC,EAAE,CAAC,CAAC,GAAG,EAAE,KAAK,CAAC,IAAI,CAAC;AAChE,QAAQ,KAAK,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC;AACpB,MAAM,CAAC;AACP,MAAM,GAAG,CAAC,KAAK,EAAE,MAAM;AACvB,IAAI,CAAC;AACL,IAAI,OAAO,KAAK,CAAC;AACjB,EAAE,CAAC;AACH;AACA,EAAE,OAAO,QAAQ,CAAC,GAAG,CAAC;AACtB,IAAI,IAAI,EAAE,CAAC,CAAC,CAAC,CAAC,MAAM,EAAE,CAAC,GAAG,CAAC,MAAM,CAAC,CAAC,IAAI,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,EAAE,CAAC,CAAC,CAAC,KAAK,EAAE,EAAE,EAAE,CAAC;AACrE,IAAI,MAAM,IAAI,CAAC,GAAG,CAAC,KAAK,CAAC,EAAE,CAAC,CAAC;AAC7B,IAAI,MAAM,CAAC,CAAC,IAAI,CAAC,MAAM,CAAC,CAAC,CAAC;AAC1B,IAAI,GAAG,CAAC,EAAE,CAAC,EAAE,OAAO,EAAE,CAAC;AACvB,IAAI,MAAM,EAAE,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC;AACrB,IAAI,MAAM,KAAK,CAAC,IAAI,CAAC,GAAG,CAAC,CAAC,EAAE,CAAC,CAAC,EAAE,CAAC,CAAC;AAClC;AACA,IAAI,MAAM,OAAO,CAAC,EAAE,CAAC;AACrB,IAAI,IAAI,MAAM,CAAC,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,GAAG,CAAC,CAAC;AACjC,MAAM,MAAM,KAAK,CAAC,IAAI,KAAK,CAAC,CAAC,CAAC,CAAC;AAC/B,MAAM,IAAI,IAAI,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC,EAAE,MAAM,GAAG,CAAC,CAAC,CAAC,IAAI,CAAC,EAAE,EAAE,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,KAAK,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,EAAE,EAAE,CAAC,CAAC,CAAC,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,CAAC,CAAC,CAAC,CAAC;AAC7G,MAAM,IAAI,IAAI,EAAE,CAAC,CAAC,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,EAAE,CAAC;AAC/B,QAAQ,IAAI,KAAK,CAAC,KAAK,CAAC;AACxB,QAAQ,IAAI,IAAI,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC;AAC5B,UAAU,IAAI,KAAK,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,CAAC;AAChC,UAAU,IAAI,IAAI,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE,EAAE,GAAG,CAAC,GAAG,CAAC,EAAE,KAAK,CAACA,eAAE,CAAC,GAAG,CAAC,KAAK,EAAEA,eAAE,CAAC,GAAG,CAAC,KAAK,CAAC,CAAC,CAAC,EAAE,KAAK,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;AACzF,UAAU,MAAM,CAAC,CAACC,oBAAI,CAAC,WAAW,CAAC,KAAK,EAAE,KAAK,CAAC,CAAC,CAAC,CAAC,CAAC;AACpD,UAAU,MAAM,KAAK,CAACD,eAAE,CAAC,GAAG,CAAC,CAAC,CAAC,KAAK,CAAC,CAAC;AACtC,UAAU,MAAM,EAAE,CAACA,eAAE,CAAC,GAAG,CAAC,KAAK,CAAC,CAAC,CAAC,EAAE,KAAK,CAAC,CAAC;AAC3C,UAAU,GAAG,IAAI,CAAC,KAAK,CAAC,EAAE,CAAC,EAAE,CAAC,KAAK,CAAC,CAAC,CAAC,CAAC,EAAE,EAAE,EAAE,CAAC,EAAE,CAAC,KAAK,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC,CAAC,KAAK,EAAE,KAAK,CAAC,IAAI,CAAC;AAChF,UAAU,KAAK,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC;AACtB,QAAQ,CAAC;AACT,QAAQ,GAAG,CAAC,KAAK,EAAE,MAAM;AACzB,MAAM,CAAC;AACP,MAAM,OAAO,CAAC,IAAI,CAAC,GAAG,KAAK,CAAC,CAAC;AAC7B,IAAI,CAAC;AACL,IAAI,OAAO,OAAO,CAAC;AACnB,EAAE,CAAC;AACH;;;;"}