c - 缩小共轭对的合成除法算法

Question

我正在用 C 实现一个合成除法算法，如下所示:

int deflate( double r, double im, double* poly, int n ) {
    int retval;
    int i;
    if( im == 0 ) {
            if( n < 1 ) {
                    retval = 1;
            } else {
                    double* out = ( double* )malloc( ( n )*sizeof( double ) );
                    out[ n - 1 ] = poly[ n ];
                    for( i = n - 2; i >= 0; i-- ) {
                            out[ i ] = out[ i + 1 ]*r + poly[ i + 1 ];
                    }

                    for( i = 0; i < n; i++ ) {
                            poly[ i ] = out[ i ];
                    }
                    poly[ n ] = 0;
                    free( out );
                    retval = 0;
            }
    } else {
            if( n < 2 ) {
                    retval = 1;
            } else {
                    /*code to handle complex numbers here*/
                    retval = 0;
            }
    }
    return retval;
}

我正在尝试想出一种有效的方法来为非零虚数组件实现这一点。具体来说，我想一次缩小两个共轭复根，而不必使用复系数多项式。谁能想办法做到这一点？

Answer 1

我已经想出了一个办法来做到这一点。解决方案很简单，理解压缩共轭对只是同时压缩两个根，这两个根构成第二个多项式，即运算的除数:

double div1 = -2*r;
double div0 = r*r + im*im;

现在使用这两个值进行合成除法，就像在多项式和前导系数为 1 的二次方程之间进行长除法一样(这实际上是实数情况下的合成除法)根，除了除数是线性的还是二次的):

int i;
out[ n - 2 ] = poly[ n ];
out[ n - 3 ] = -out[ n - 2 ]*div1 + poly[ n - 1 ];
for( i = n - 4; i >= 0; i-- ) {
    out[ i ] = -out[ i + 2 ]*div0 + -out[ i + 1 ]*div1 + poly[ i + 2 ];
}
for( i = 0; i < n; i++ ) {
    poly[ i ] = out[ i ];
}
poly[ n - 1 ] = 0.0;
poly[ n ] = 0.0;
free( out );
retval = 0;

这完全绕过了形成复系数多项式的需要，并在一次通过中对两个复根都进行了压缩。