java - Inverse 2D FFT is outputting correct values in wrong order -

my 2d fft algorithm outputting correct values, in wrong order. example, input:

1050.0  1147.0  1061.0  1143.0   1046.0  1148.0  1118.0  1073.0   1072.0  1111.0  1154.0  1101.0   1078.0  1101.0  1106.0  1062.0   

taking fft, , inverse fft results in:

1050.0  1143.0  1061.0  1147.0   1078.0  1062.0  1106.0  1101.0   1072.0  1101.0  1154.0  1111.0   1046.0  1073.0  1118.0  1148.0   

you can see if flip last 3 columns horizontally, last 3 rows vertically, data correct. far can tell true input sizes it's easy (albeit hacky) fix. worried about computational time of fix because may have perform on 1024x1024 or 2048x2048 images in future.

i confident 1d fft algorithm dofft() correct, , getting expected values forward 2d fft. inverse 2d fft causing me trouble.

does see error is?

code

private static double[] cose; private static double[] sin;  public static void main(string[] args) {      float[][] img = new float[][]{         { 1050.0f, 1147.0f, 1061.0f, 1143.0f},         { 1046.0f, 1148.0f, 1118.0f, 1073.0f},         { 1072.0f, 1111.0f, 1154.0f, 1101.0f},         { 1078.0f, 1101.0f, 1106.0f, 1062.0f}     };      int size = img.length;      system.out.println("image");     (int = 0; < size; i++)     {         (int j = 0; j < size; j++)         {             system.out.print(img[i][j] + "\t");         }         system.out.println();     }      complex[][] fft = fft2d(tocomplex(img), false);      complex[][] inverse = fft2d(fft, true);      system.out.println("\ninverse");     (int = 0; < size; i++)     {         (int j = 0; j < size; j++)         {             system.out.print(inverse[i][j].getreal()  + "\t");         }         system.out.println();     }  }  public static complex[][] fft2d(complex[][] pixels, boolean inverse){      int size = pixels.length;     computecossin(size);      complex[][] data = transpose(pixels.clone());      complex[] temp;      // fft of rows     (int = 0; < size; i++)     {         temp = dofft(data[i], size);         data[i] = temp;     }      // fft of columns     (int = 0; < size; i++)     {         temp = new complex[size];         (int j = 0; j < size; j++)         {             temp[j] = data[j][i];         }         complex[] temp2 = dofft(temp, size);         (int j = 0; j < size; j++)         {             data[j][i] = temp2[j];         }     }      if (!inverse)     {         (int = 0; < size; i++)         {             (int j = 0; j < size; j++)             {                 data[i][j] = data[i][j].divide(size*size);             }         }     }     return data; }  public static complex[] dofft(complex[] data, int size){      complex[] temp = new complex[size];      int j = 0;     (int = 0; < size; i++) {         temp[i] = data[j];         int k = size / 2;          while ((j >= k) && (k > 0)) {             j -= k;             k /= 2;         }         j += k;     }      complex n,m,h,f;     for(int i=0; i<size;i+=4){         n = temp[i].add(temp[i+1]);         m = temp[i+2].add(temp[i+3]);         h = temp[i].subtract(temp[i+1]);         f = temp[i+2].subtract(temp[i+3]);         complex mult = h.add(f.multiply(complex.i));         complex sub = h.subtract(f.multiply(complex.i));          temp[i] = n.add(m);         temp[i+2] = n.subtract(m);         temp[i+1] = sub;         temp[i+3] = mult;     }      int u;     for(int i=4; i< size;i<<=1){         int v = size/(i <<1);          for(int c=0; c< size;c +=i<<1){             for(int x=0; x < i; x++){                 u = v*x;                  double calc = temp[i+c+x].getreal()*cose[u] - temp[i+c+x].getimaginary()*sin[u];                 double calc2 = temp[i+c+x].getreal()*sin[u] + temp[i+c+x].getimaginary()*cose[u];                 complex fftarray = new complex(calc,calc2);                  temp[(i+c+x)] =temp[(c+x)].subtract(fftarray);                 temp[(c+x)] = temp[(c+x)].add(fftarray);             }         }     }      return temp; }  public static complex[][] tocomplex(float[][] arr) {     complex[][] newarr = new complex[arr.length][arr.length];     (int = 0; < arr.length; i++)     {         (int j = 0; j < arr.length; j++)         {             newarr[i][j] = new complex(arr[i][j], 0.0);         }     }     return newarr; }  public static complex[][] transpose(complex[][] array) {     (int = 0; < array.length; i++)     {         (int j = i+1; j < array[i].length; j++)         {             complex temp = array[i][j];             array[i][j] = array[j][i];             array[j][i] = temp;          }     }     return array; }  public static void computecossin(int size){      double num = (2.0*math.pi)/size;     double cos = math.cos(num);     double sine = math.sin(num);      cose = new double[size];     sin = new double[size];      cose[0] =1.0;      for(int i=1; i<size;i++){         cose[i] = cos*cose[i-1] + sine*sin[i-1];         sin[i] = cos*sin[i-1] - sine*cose[i-1];     }  } 

}

this doesn't solve root problem, change data i'm getting data expect serve purpose now. worry incredibly slow on large arrays.

this function swaps row row n-i , swaps every column column n-i, 0 < < n, (assuming square, power of 2 input array)

public complex[][] inversefix(complex[][] array) {     int size = array.length;      // swap rows     complex[] temp;     (int = 1; < size/2; i++)     {         temp = array[i];         array[i] = array[size-i];         array[size-i] = temp;     }      // swap columns     complex temp2;     (int = 0; < size; i++)     {         (int j = 1; j < size/2; j++)         {             temp2 = array[i][j];             array[i][j] = array[i][size-j];             array[i][size-j] = temp2;         }     }     return array; }