How to implement a Pitch Effect in Java? (FFT, IFFT, Amplitude, Phase)

I use the apache commons math library for transforming the FFt and IFFT on my audio sample buffers. The outout of the FFT gives me an array of complex numbers. The frequencies mirror in the middle. With a sample buffer size of 4096 samples I get 2048 useful complex numbers.

I have two implementations in Java, one runs through the final array before the IFFT and computes an interpolation of the position where it should take the complex number from. So basically what I am doing is warping the complex numbers in another frequency scale.

FastFourierTransformer fft = new FastFourierTransformer(DftNormalization.STANDARD);
Complex[] freq, inverse, freqn;

for(int c = 0; c < in.length; c++){

    freq = fft.transform(in[c], TransformType.FORWARD);
    freqn = new Complex[freq.length];

    freqn[0] = Complex.valueOf(freq[0].getReal(), freq[0].getImaginary());

    for (int i = 1; i <= freq.length/2; i++) {

        double fOrig = i / factor + shift;

        int left = (int) Math.floor(fOrig);
        int right = (int) Math.ceil(fOrig);
        double weighting = fOrig - left;

        double new_Re = 0, new_Im = 0;

        if(left > 0 && left < freq.length / 2 && right > 0 && right < freq.length / 2){
            new_Re = interpolate(freq[left].getReal(), freq[right].getReal(), weighting);
            new_Im = interpolate(freq[left].getImaginary(), freq[right].getImaginary(), weighting);
        }
        freqn[i] = Complex.valueOf(new_Re, new_Im);
        freqn[freq.length-i] = Complex.valueOf(new_Re, new_Im);
    }
    inverse = fft.transform(freqn, TransformType.INVERSE);

    for(int i = 0; i < inverse.length; i++){
        in[c][i] = inverse[i].getReal();
    }
}

This implementation pitches the sound with side effect mostly in the high region since I get multiple pitched frequencies out of one due to the sample rate of my input audio signal. My other implementation calculates the amplitude as well as the phase out of the incoming complex numbers. It then warps only the amplitude scale to a new position and then calculates with the help of the original phase value and the new amplitude value the new complex number. While converting between rectangular to polar and back to rectangular I lose my signs. Since I only change the length of the Complex number vector I can force my input signs on the output complex numbers.

FastFourierTransformer fft = new FastFourierTransformer(DftNormalization.STANDARD);
Complex[] freq, inverse;

for(int c = 0; c < in.length; c++){

    freq = fft.transform(in[c], TransformType.FORWARD);

    double[] ampl = new double[freq.length];
    double[] angl = new double[freq.length];

    double re, im;

    boolean[] unitRe = new boolean[freq.length];
    boolean[] unitIm = new boolean[freq.length];

    double fctr = factor;

    for(int f = 0; f < freq.length; f++){
        re = freq[f].getReal();
        im = freq[f].getImaginary();
        unitRe[f] = re >= 0;
        unitIm[f] = im >= 0;

        ampl[f] = op.magn(re, im);
        angl[f] = op.agl(re, im);
    }

    for(int f = 0; f < freq.length; f++){
        int val = f < freq.length / 2 ? f : freq.length / 2 - (f - freq.length / 2);
        double weighting = ((double)val / fctr + shift) % 1;

        int left = (int) Math.floor(val / fctr + shift);
        int right = (int) Math.ceil(val / fctr + shift);
        double new_ampl = 0;

        if(left >= 0 && left < freq.length / 2 && right >= 0 && right < freq.length / 2){
            new_ampl = interpolate(ampl[left], ampl[right], weighting);
        }

        re = op.real(new_ampl, angl[f]);
        im = op.imag(new_ampl, angl[f]);

        re = unitRe[f] ? Math.abs(re) : Math.abs(re) * -1;
        im = unitIm[f] ? Math.abs(im) : Math.abs(im) * -1;

        freq[f] = Complex.valueOf(re, im);
    }

    inverse = fft.transform(freq, TransformType.INVERSE);

    for(int i = 0; i < inverse.length; i++){
        in[c][i] = inverse[i].getReal();
    }
}

The second implementation sounds way better than the first one. It actually even sounds better than in most of the Dj applications I used but I do not know why? Am I doing something wrong? I could not find any other implementation in Java to compare with. Do they usually just warp the whole frequency scale with amplitude and phase in a new scale or do they just take the amplitude and force it onto the original phase in another scale?

Your second algorithm is similar to the phase vocoder method of time pitch modification. Many audio processing libraries are reported to use variations on the phase vocoder technique, but usually only if sufficient processing power is available.