src/com/michaelho/DivideAndConquer/DC5.java
/**
     * Calculate the multiplication of 2 polynomials.
     *
     * @param p The coefficients of the first polynomials in double.
     * @param q The coefficients of the second polynomials in double.
     * @param omega The omega w in the FFT formula.
     * @param omegaInv The omega inverse w^-1 in the FFT formula.
     *
     * @return The result of the multiplication.
     * */
Calculate the multiplication of 2 polynomials.
@param p The coefficients of the first polynomials in double.
@param q The coefficients of the second polynomials in double.
@param omega The omega w in the FFT formula.
@param omegaInv The omega inverse w^-1 in the FFT formula.

@return The result of the multiplication.
Calculate the multiplication of 2 polynomials . @param p The coefficients of the first polynomials in double . @param q The coefficients of the second polynomials in double . @param omega The omega w in the FFT formula . @param omegaInv The omega inverse w^ - 1 in the FFT formula . @return The result of the multiplication .
double[] multiply(double[] p, double[] q, int n, Complex[] omega, Complex[] omegaInv) {
        Complex[] pInteger = new Complex[n];
        Complex[] qInteger = new Complex[n];
        for (int i = 0; i < n/2; i++) {
            pInteger[i] = new Complex(p[i], 0);
            qInteger[i] = new Complex(q[i], 0);
        }
        for (int i = n/2; i < n; i++) {
            pInteger[i] = new Complex(0, 0);
            qInteger[i] = new Complex(0, 0);
        }
        int pow = 1;
        Complex[] solp = dc4.fft.FFT(pInteger, omega, n, pow);
        Complex[] solq = dc4.fft.FFT(qInteger, omega, n, pow);
        Complex[] finalSol = new Complex[n];
        for (int i = 0; i < n; i++)
            finalSol[i] = solp[i].multiply(solq[i]);
        Complex[] poly = dc4.fft.FFT(finalSol, omegaInv, n, pow);
        double[] result = new double[n-1];
        for (int i=0; i < n-1; i++)
            result[i] = poly[i].getReal() / n;
        return result;
    }
double [ ] multiply ( double [ ] p , double [ ] q , int n , Complex [ ] omega , Complex [ ] omegaInv ) { Complex [ ] pInteger = new Complex [ n ] ; Complex [ ] qInteger = new Complex [ n ] ; for ( int i = 0 ; i < n / 2 ; i ++ ) { pInteger [ i ] = new Complex ( p [ i ] , 0 ) ; qInteger [ i ] = new Complex ( q [ i ] , 0 ) ; } for ( int i = n / 2 ; i < n ; i ++ ) { pInteger [ i ] = new Complex ( 0 , 0 ) ; qInteger [ i ] = new Complex ( 0 , 0 ) ; } int pow = 1 ; Complex [ ] solp = dc4 . fft . FFT ( pInteger , omega , n , pow ) ; Complex [ ] solq = dc4 . fft . FFT ( qInteger , omega , n , pow ) ; Complex [ ] finalSol = new Complex [ n ] ; for ( int i = 0 ; i < n ; i ++ ) finalSol [ i ] = solp [ i ] . multiply ( solq [ i ] ) ; Complex [ ] poly = dc4 . fft . FFT ( finalSol , omegaInv , n , pow ) ; double [ ] result = new double [ n - 1 ] ; for ( int i = 0 ; i < n - 1 ; i ++ ) result [ i ] = poly [ i ] . getReal ( ) / n ; return result ; }
Calculate the multiplication of 2 polynomials.
Calculate the multiplication of 2 polynomials .
// Generate complex objects with 2 times the size // Copy the coefficents into the real part of complex number and pad zeros to remaining terms. // Apply the FFT to the two factors // Multiply the results point-wise recursive // Apply the FFT to the point-wise product