Unexpected amplitude values in my implementation of DFT in java

Question

I am working on a project to draw a given figure using epicycles (by DFT). I am following this website: https://www.instructables.com/Drawing-With-Discrete-Fourier-Transform/ but I don't seem to be getting correct values for the amplitudes because for any sample of points, the amplitude increases in the end (at higher frequencies) while I don't think it should - at least not according to the examples in the website.

The function takes a double[][] as input containing x and y coordinates of sample points and Points.n is the number of sample points. Here is my DFT function:

public class Dft {
    public static double[][] dft(double[][] psamples){
        double[][] result = new double[Points.n][2];
        for (int i = 0; i < Points.n; i++){
            Complex x_i = new Complex(0, 0);
            for (int j = 0; j < Points.n; j++){
                Complex sample = new Complex(psamples[j][0], psamples[j][1]);
                double root = Math.PI*2*i*j/Points.n;
                Complex unity = new Complex(Math.cos(root), -Math.sin(root));
                x_i = Complex.add(x_i, Complex.multiply(sample, unity));
            }
            result[i][0] = x_i.amp()/Points.n; //amplitude
            result[i][1] = x_i.angle(); //phase change
            //frequency is equal to the index number i
            System.out.println(i + " amp: " + result[i][0] + " phase change: " + result[i][1]);
        }
        return result;
    } 
}

The Complex class is :

public class Complex {
    double[] num = {0,0};
    public Complex(double a, double b){
        num[0] = a;
        num[1] = b;
    }
    public void setReal(double a){
        num[0] = a;
    }
    public void setImaginary(double b){
        num[1] = b;
    }
    public double getReal(){
        return num[0];
    }
    public double getImaginary(){
        return num[1];
    }
    public static Complex add(Complex a, Complex b){
        Complex result = new Complex(a.getReal()+b.getReal(), a.getImaginary() + b.getImaginary());
        return result;
    }
    public static Complex euler(double r, double theta){
        Complex result = new Complex(r*Math.cos(theta), r*Math.sin(theta));
        return result;
    }
    public static Complex multiply(Complex a, Complex b){
        Complex result = new Complex(a.getReal()*b.getReal() - a.getImaginary()*b.getImaginary(), a.getReal()*b.getImaginary() + a.getImaginary()*b.getReal());
        return result;
    }
    public double amp(){
        double result = Math.sqrt(num[0]*num[0] + num[1]*num[1]);
        return result;
    }
    public double angle(){
        if (num[0] == 0){
            if (num[1]>0) return Math.PI/2;
            else if (num[1]<0) return -Math.PI/2;
            else return 0;
        }
        else {
        double result = Math.atan2(num[1],num[0]);
        return result;
        }
    }
}

I can't directly compare them because in this website: https://www.dynamicmath.xyz/fourier-epicycles/ I can not directly input the sample points (as x and y coordinates) so I have to draw a new input. However if I draw similar inputs, for example a rectangle, I can see that the demo in the website has lesser amplitudes as frequency increases. In my function, the amplitude generally continues to decrease but at the end it increases again. I know the points being inputted are correct, I have checked those. If you have any particular inputs, I can run and tell you my results. — Momin Ahmed, May 21 '23 at 13:38
Could you then guide me to a forum where this would be acceptable? I am really stuck here and I need help. — Momin Ahmed, May 21 '23 at 14:23
first check your DFT correctness (if you do iDFT you should get the original signal) and only then move on. See [How to compute Discrete Fourier Transform?](https://stackoverflow.com/a/26355569/2521214) and its sublinks so you have something for cross-comparison — Spektre, May 22 '23 at 07:02
Ahmed, it looks like you have made a good attempt. Problems like this can be approached in a fairly systematic way. First try some cases for which you can predict the results from mathematical identities. For example, what is the expected output for input which is all 0? What about all 0, except one 1? What about all 1? What about replacing every nonzero value with the negative of that value? What about a single value? two values? four? ten? etc. If you get past those cases, try other identities. When you get cases based on identities working, then try your "real" input. Good luck. — Robert Dodier, May 22 '23 at 18:05

Spektre · Answer 1 · 2023-05-23T11:36:20.043

not coding in JAVA but I was curious so I tried it in C++/VCL

load some 2D polygon data

I used SVG hand-drawed image (in my SVG editor):

 <svg width="512" height="512" viewBox="7.16534 14.370463 81.713727 78.871962" >
  <g fill="none" stroke="blue" stroke-width="1px" data-tool="-1" data-cfg="-1" data-group="-1" data-hair="0" data-dir="0" transform="matrix(1,0,0,1,0,0">
   <path d="M 48.516651 35.319958 c -0.219755 -0.329888 -0.879021 -1.319554 -1.318532 -1.979331 c -0.43951 -0.659777 -0.824082 -1.209591 -1.318532 -1.979331 c -0.494449 -0.76974 -1.153715 -1.979331 -1.648165 -2.639108 c -0.494449 -0.659777 -0.879021 -0.824721 -1.318532 -1.319554 c -0.43951 -0.494832 -0.824082 -1.209591 -1.318532 -1.649442 c -0.494449 -0.439851 -0.879021 -0.714758 -1.648165 -0.989665 c -0.769143 -0.274907 -2.142614 -0.439851 -2.966697 -0.659777 c -0.824082 -0.219925 -1.208654 -0.549814 -1.977798 -0.659777 c -0.769143 -0.109962 -1.758042 0 -2.637064 0 c -0.879021 0 -1.758042 0 -2.637064 0 c -0.879021 0 -1.703103 0 -2.637064 0 c -0.93396 0 -2.197553 -0.054981 -2.966697 0 c -0.769143 0.054981 -1.098776 0.109962 -1.648165 0.329888 c -0.549388 0.219925 -0.9889 0.549814 -1.648165 0.989665 c -0.659266 0.439851 -1.593226 1.15461 -2.307431 1.649442 c -0.714204 0.494832 -1.483348 0.76974 -1.977798 1.319554 c -0.494449 0.549814 -0.714204 1.319554 -0.9889 1.979331 c -0.274694 0.659777 -0.43951 1.264572 -0.659266 1.979331 c -0.219755 0.714758 -0.494449 1.484498 -0.659266 2.30922 c -0.164816 0.824721 -0.274694 1.979331 -0.329633 2.639108 c -0.054938 0.659777 0 0.659777 0 1.319554 c 0 0.659777 0 1.869368 0 2.639108 c 0 0.76974 0 1.209591 0 1.979331 c 0 0.76974 -0.109877 1.979331 0 2.639108 c 0.109877 0.659777 0.274694 0.659777 0.659266 1.319554 c 0.384571 0.659777 1.208654 1.92435 1.648165 2.639108 c 0.43951 0.714758 0.494449 1.044647 0.9889 1.649442 c 0.494449 0.604795 1.483348 1.374535 1.977798 1.979331 c 0.494449 0.604795 0.604327 1.099628 0.9889 1.649442 c 0.384571 0.549814 0.93396 1.209591 1.318532 1.649442 c 0.384571 0.439851 0.494449 0.549814 0.9889 0.989665 c 0.494449 0.439851 1.37347 1.209591 1.977798 1.649442 c 0.604327 0.439851 1.043837 0.494832 1.648165 0.989665 c 0.604327 0.494832 1.428409 1.53948 1.977798 1.979331 c 0.549388 0.439851 0.824082 0.439851 1.318532 0.659777 c 0.494449 0.219925 1.043837 0.439851 1.648165 0.659777 c 0.604327 0.219925 1.318532 0.329888 1.977798 0.659777 c 0.659266 0.329888 1.318532 0.934684 1.977798 1.319554 c 0.659266 0.38487 1.428409 0.604795 1.977798 0.989665 c 0.549388 0.38487 0.769143 0.934684 1.318532 1.319554 c 0.549388 0.38487 1.318532 0.604795 1.977798 0.989665 c 0.659266 0.38487 1.37347 0.824721 1.977798 1.319554 c 0.604327 0.494832 1.098776 1.15461 1.648165 1.649442 c 0.549388 0.494832 1.043837 0.824721 1.648165 1.319554 c 0.604327 0.494832 1.428409 1.099628 1.977798 1.649442 c 0.549388 0.549814 0.879021 0.989665 1.318532 1.649442 c 0.43951 0.659777 0.9889 1.649442 1.318532 2.30922 c 0.329633 0.659777 0.329633 1.044647 0.659266 1.649442 c 0.329633 0.604795 0.9889 1.319554 1.318532 1.979331 c 0.329633 0.659777 0.43951 1.209591 0.659266 1.979331 c 0.219755 0.76974 0.549388 2.30922 0.659266 2.639108 c 0.109877 0.329888 0 -0.219925 0 -0.659777 c 0 -0.439851 -0.054938 -1.209591 0 -1.979331 c 0.054938 -0.76974 0.219755 -1.814387 0.329633 -2.639108 c 0.109877 -0.824721 0.164816 -1.594461 0.329633 -2.30922 c 0.164816 -0.714758 0.549388 -1.319554 0.659266 -1.979331 c 0.109877 -0.659777 -0.109877 -1.209591 0 -1.979331 c 0.109877 -0.76974 0.384571 -1.869368 0.659266 -2.639108 c 0.274694 -0.76974 0.769143 -1.264572 0.9889 -1.979331 c 0.219755 -0.714758 0.164816 -1.649442 0.329633 -2.30922 c 0.164816 -0.659777 0.329633 -0.879702 0.659266 -1.649442 c 0.329633 -0.76974 0.9889 -2.144275 1.318532 -2.968997 c 0.329633 -0.824721 0.43951 -1.484498 0.659266 -1.979331 c 0.219755 -0.494832 0.43951 -0.604795 0.659266 -0.989665 c 0.219755 -0.38487 0.384571 -0.824721 0.659266 -1.319554 c 0.274694 -0.494832 0.659266 -1.044647 0.9889 -1.649442 c 0.329633 -0.604795 0.604327 -1.319554 0.9889 -1.979331 c 0.384571 -0.659777 0.769143 -1.319554 1.318532 -1.979331 c 0.549388 -0.659777 1.318532 -1.429517 1.977798 -1.979331 c 0.659266 -0.549814 1.37347 -0.824721 1.977798 -1.319554 c 0.604327 -0.494832 1.098776 -1.209591 1.648165 -1.649442 c 0.549388 -0.439851 0.9889 -0.604795 1.648165 -0.989665 c 0.659266 -0.38487 1.648165 -0.879702 2.307431 -1.319554 c 0.659266 -0.439851 1.098776 -0.879702 1.648165 -1.319554 c 0.549388 -0.439851 1.043837 -0.824721 1.648165 -1.319554 c 0.604327 -0.494832 1.37347 -1.099628 1.977798 -1.649442 c 0.604327 -0.549814 1.208654 -1.099628 1.648165 -1.649442 c 0.43951 -0.549814 0.714204 -0.934684 0.9889 -1.649442 c 0.274694 -0.714758 0.549388 -1.704424 0.659266 -2.639108 c 0.109877 -0.934684 0 -2.199257 0 -2.968997 c 0 -0.76974 0.109877 -1.044647 0 -1.649442 c -0.109877 -0.604795 -0.274694 -1.209591 -0.659266 -1.979331 c -0.384571 -0.76974 -1.043837 -1.869368 -1.648165 -2.639108 c -0.604327 -0.76974 -1.428409 -1.484498 -1.977798 -1.979331 c -0.549388 -0.494832 -0.769143 -0.76974 -1.318532 -0.989665 c -0.549388 -0.219925 -1.37347 -0.164944 -1.977798 -0.329888 c -0.604327 -0.164944 -1.043837 -0.439851 -1.648165 -0.659777 c -0.604327 -0.219925 -1.37347 -0.549814 -1.977798 -0.659777 c -0.604327 -0.109962 -1.153715 0.054981 -1.648165 0 c -0.494449 -0.054981 -0.659266 -0.219925 -1.318532 -0.329888 c -0.659266 -0.109962 -1.922859 -0.274907 -2.637064 -0.329888 c -0.714204 -0.054981 -1.098776 0.054981 -1.648165 0 c -0.549388 -0.054981 -0.93396 -0.274907 -1.648165 -0.329888 c -0.714204 -0.054981 -1.86792 0 -2.637064 0 c -0.769143 0 -1.208654 0 -1.977798 0 c -0.769143 0 -1.922859 -0.164944 -2.637064 0 c -0.714204 0.164944 -0.9889 0.604795 -1.648165 0.989665 c -0.659266 0.38487 -1.703103 0.879702 -2.307431 1.319554 c -0.604327 0.439851 -0.879021 0.879702 -1.318532 1.319554 c -0.43951 0.439851 -1.043837 0.824721 -1.318532 1.319554 c -0.274694 0.494832 -0.109877 0.879702 -0.329633 1.649442 c -0.219755 0.76974 -0.824082 2.034312 -0.9889 2.968997 c -0.164816 0.934684 -0.054938 2.034312 0 2.639108 c 0.054938 0.604795 0.274694 0.824721 0.329633 0.989665 "/>
  </g>
 </svg>

and stored the data as set of 2D points (see pic[] in data.h below)

do 1D DFFT on input polygon (complex input and output)

each 2D point is represented as single complex number. As I used DFFT (DFT was ~1sec too slow to my taste) the input data must be power of 2 size so "pad" themissing data (I duplicated last point).
during rendering do iDFT (complex input and output) and render line/circle in each inner loop iteration

however this step is different from iDFT as we do not use the outer loop and instead we select only single output (not computing whole array). The selected index is like animation time/parameter. However the change must be discrete (you can not interpolate between 2 values without more heavy computations).

Here simplified (without SVG importer, with fixed size and static data and removed all unimportant stuff) C++/VCL example:

//---------------------------------------------------------------------------
#include <math.h>
#include "data.h"
//---------------------------------------------------------------------------
int tepi=0;             // animation time <0,N)
//---------------------------------------------------------------------------
void DFFTcc(float *dst,float *src,int n)    // n must be power of 2 !!!
    {
    // precompute sin,cos LUTs if not computed yet
    static float _cos[N]={0.0},_sin[N];
    if (_cos[0]<=0.9)
        {
        float a,da; int i;
        da=2.0*M_PI/float(N);
        for (a=0.0,i=0;i<N;i++,a+=da) { _cos[i]=cos(a); _sin[i]=sin(a); }
        }
    // DFFT
    if (n<=1) { if (n==1) { dst[0]=src[0]*2.0; dst[1]=src[1]*2.0; } return; }
    int i,j,n2=n>>1,q,dq=+N/n,mq=N-1;
    // reorder even,odd (buterfly)
    for (j=0,i=0;i<n+n;) { dst[j]=src[i]; i++; j++; dst[j]=src[i]; i+=3; j++; }
    for (    i=2;i<n+n;) { dst[j]=src[i]; i++; j++; dst[j]=src[i]; i+=3; j++; }
    // recursion
    float tmp[N2];
    DFFTcc(tmp  ,dst  ,n2); // even
    DFFTcc(tmp+n,dst+n,n2); // odd
    // reorder and weight back (buterfly)
    float a0,a1,b0,b1,a,b;
    for (q=0,i=0,j=n;i<n;i+=2,j+=2,q=(q+dq)&mq)
        {
        a0=tmp[j  ]; a1=+_cos[q];
        b0=tmp[j+1]; b1=+_sin[q];
        a=(a0*a1)-(b0*b1);
        b=(a0*b1)+(a1*b0);
        a0=tmp[i  ]; a1=a;
        b0=tmp[i+1]; b1=b;
        dst[i  ]=(a0+a1)*0.5;
        dst[i+1]=(b0+b1)*0.5;
        dst[j  ]=(a0-a1)*0.5;
        dst[j+1]=(b0-b1)*0.5;
        }
    }
//---------------------------------------------------------------------------
void draw(TCanvas *scr,int xs,int ys) // target canvas, resolution
    {
    int xs2,ys2;
    Graphics::TBitmap *bmp;
    xs2=xs>>1;
    ys2=ys>>1;
    bmp=new Graphics::TBitmap;
    bmp->HandleType=bmDIB;
    bmp->PixelFormat=pf32bit;
    bmp->Width=xs;
    bmp->Height=ys;
    bmp->Canvas->Brush->Color=0x00000000;
    bmp->Canvas->FillRect(TRect(0,0,xs,ys));

    int i;
    float x,y,scale=float(ys)/100.0;

    // render image
    bmp->Canvas->Pen->Color=0x00204080;
                      i=0;      // DC offset
    x=pic[i]*scale; i++;
    y=pic[i]*scale; i++;
    bmp->Canvas->MoveTo(x,y);
    for (;i<N2;)
        {
        x=pic[i]*scale; i++;
        y=pic[i]*scale; i++;
        bmp->Canvas->LineTo(x,y);
        }

    // render epicycles
    bmp->Canvas->Pen->Color=0x00804020;
    bmp->Canvas->Brush->Style=bsClear;

    // iDFTcc src,dst
    float dx,dy,a0,a1,b0,b1,q,qq,r,m;
    q=+2.0*M_PI*tepi/float(N); x=0.0; y=0.0; m=0.5*scale;
    for (qq=0.0,i=0;i<N;i++,qq+=q)
        {
        a0=epi[i+i  ]; a1=+cos(qq);
        b0=epi[i+i+1]; b1=-sin(qq);
        dx=(a0*a1)-(b0*b1);
        dy=(a0*b1)+(b0*a1);
        r=sqrt((dx*dx)+(dy*dy));
        bmp->Canvas->Ellipse((x-r)*m,(y-r)*m,(x+r)*m,(y+r)*m);
        bmp->Canvas->MoveTo(x*m,y*m);
        x+=dx; y+=dy;
        bmp->Canvas->LineTo(x*m,y*m);
        }
    bmp->Canvas->Brush->Style=bsSolid;

    scr->Draw(0,0,bmp);
    delete bmp;
    }
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner) // window init
    {
    // polygon -> epicycles
    DFFTcc(epi,pic,N);      // epi = DFFT(pic)
    }
//---------------------------------------------------------------------------
void __fastcall TForm1::Timer1Timer(TObject *Sender) // animation timer
    {
    tepi++; if (tepi>=N) tepi=0;
    draw(Canvas,ClientWidth,ClientHeight);
    }
//---------------------------------------------------------------------------

here the data.h (both input and output so you can cross compare):

const int N=256;        // max num of points
const int N2=N+N;
float pic[N2]=
    {48.096,34.688,47.443,33.708,46.917,32.922,46.362,32.097,45.831,31.285,45.305,30.419,44.749,29.497,44.231,28.722,
    43.585,28.030,42.913,27.403,42.365,26.683,41.731,25.885,41.067,25.326,40.175,24.850,39.323,24.587,38.265,24.372,
    37.240,24.168,36.361,23.896,35.495,23.555,34.632,23.408,33.618,23.406,32.567,23.442,31.654,23.444,30.639,23.444,
    29.728,23.444,28.727,23.444,27.720,23.444,26.791,23.442,25.709,23.426,24.655,23.423,23.733,23.476,22.765,23.667,
    21.977,24.015,21.123,24.564,20.370,25.080,19.519,25.696,18.674,26.305,17.889,26.802,17.035,27.310,16.414,27.888,
    15.924,28.776,15.553,29.712,15.234,30.585,14.926,31.587,14.662,32.425,14.376,33.394,14.180,34.298,14.029,35.383,
    13.926,36.395,13.883,37.262,13.905,38.121,13.905,39.128,13.905,40.218,13.905,41.150,13.905,42.131,13.895,43.064,
    13.859,44.161,13.894,45.140,14.153,45.910,14.644,46.671,15.162,47.508,15.754,48.444,16.213,49.175,16.708,50.081,
    17.202,50.825,17.876,51.522,18.659,52.254,19.254,52.899,19.780,53.777,20.224,54.533,20.862,55.361,21.487,56.103,
    22.064,56.718,22.740,57.327,23.554,58.027,24.381,58.689,25.154,59.155,26.009,59.658,26.662,60.264,27.410,61.062,
    28.079,61.711,28.879,62.171,29.665,62.487,30.630,62.876,31.495,63.174,32.451,63.454,33.282,63.833,34.143,64.425,
    35.002,65.010,35.844,65.422,36.745,65.851,37.423,66.404,38.061,67.127,38.790,67.604,39.720,68.025,40.537,68.462,
    41.418,69.015,42.254,69.628,42.923,70.266,43.621,71.008,44.287,71.608,45.056,72.207,45.776,72.780,46.603,73.436,
    47.393,74.115,48.017,74.773,48.606,75.542,49.110,76.309,49.654,77.242,50.127,78.130,50.467,78.966,50.824,79.855,
    51.324,80.606,51.945,81.488,52.354,82.314,52.653,83.274,52.906,84.200,53.187,85.357,53.417,86.302,53.505,86.444,
    53.460,85.643,53.437,84.646,53.476,83.631,53.591,82.619,53.737,81.567,53.856,80.644,53.982,79.630,54.145,78.764,
    54.490,77.808,54.780,76.886,54.788,76.031,54.766,75.018,54.917,74.152,55.171,73.121,55.439,72.267,55.904,71.341,
    56.362,70.476,56.566,69.588,56.665,68.541,56.846,67.665,57.210,66.793,57.593,65.928,58.030,64.966,58.480,63.966,
    58.828,63.118,59.163,62.053,59.450,61.265,59.999,60.481,60.408,59.677,60.851,58.833,61.379,57.978,61.834,57.169,
    62.263,56.268,62.691,55.443,63.207,54.582,63.804,53.720,64.390,53.027,65.106,52.285,65.846,51.604,66.575,51.061,
    67.414,50.553,68.120,50.031,68.845,49.280,69.543,48.573,70.274,48.069,71.161,47.584,71.945,47.144,72.887,46.622,
    73.662,46.143,74.472,45.514,75.217,44.887,75.907,44.338,76.697,43.704,77.405,43.129,78.224,42.456,78.922,41.846,
    79.693,41.128,80.374,40.410,80.918,39.702,81.394,38.832,81.691,38.013,81.958,37.022,82.139,35.980,82.188,35.038,
    82.165,33.948,82.139,33.011,82.185,32.034,82.106,31.188,81.866,30.293,81.480,29.382,81.033,28.555,80.480,27.656,
    79.889,26.816,79.271,26.100,78.524,25.369,77.854,24.764,77.122,24.107,76.363,23.716,75.355,23.568,74.453,23.414,
    73.501,23.030,72.627,22.679,71.611,22.306,70.707,22.095,69.663,22.132,68.812,22.021,67.886,21.782,66.890,21.638,
    65.791,21.507,64.846,21.449,63.878,21.478,63.050,21.336,62.032,21.135,61.165,21.110,60.081,21.126,59.162,21.135,
    58.164,21.135,57.233,21.132,56.186,21.078,55.135,21.080,54.313,21.305,53.566,21.831,52.803,22.309,51.859,22.817,
    50.969,23.343,50.239,23.958,49.576,24.691,48.899,25.303,48.232,26.007,48.005,26.761,47.857,27.733,47.552,28.605,
    47.172,29.621,46.885,30.613,46.785,31.593,46.812,32.663,46.890,33.511,47.198,34.330,47.198,34.330,47.198,34.330,
    47.198,34.330,47.198,34.330,47.198,34.330,47.198,34.330,47.198,34.330,47.198,34.330,47.198,34.330,47.198,34.330,
    47.198,34.330,47.198,34.330,47.198,34.330,47.198,34.330,47.198,34.330,47.198,34.330,47.198,34.330,47.198,34.330,
    };
float epi[N2]=
    {95.280,89.953,-17.550,-49.533,6.344,7.333,6.259,7.659,4.980,2.621,-0.481,-0.499,0.779,0.595,0.154,-0.154,
    0.239,-0.574,-0.535,0.244,-0.004,0.195,-0.152,0.501,0.046,0.143,-0.059,0.386,-0.024,-0.042,0.122,0.147,
    0.034,0.009,0.129,0.086,-0.032,-0.036,0.101,0.007,0.018,-0.023,0.051,-0.006,-0.078,0.053,-0.004,0.016,
    -0.010,0.063,0.000,0.028,-0.022,0.076,0.057,0.007,0.028,0.068,0.020,0.020,0.074,0.051,-0.024,0.018,
    0.034,0.037,-0.050,-0.034,0.039,-0.006,-0.038,0.012,-0.003,0.010,-0.023,0.024,0.014,0.029,-0.012,0.007,
    0.015,0.020,0.042,0.019,0.014,-0.022,0.045,0.015,-0.016,0.021,0.015,0.017,0.017,0.005,0.034,-0.001,
    -0.018,0.013,-0.003,0.013,-0.014,0.033,0.017,0.016,0.017,0.023,-0.005,-0.015,0.020,0.022,-0.004,0.018,
    0.009,0.008,0.009,0.001,0.012,0.025,-0.008,0.018,0.017,0.001,0.003,0.003,0.008,0.005,-0.003,0.001,
    -0.006,0.015,-0.011,0.004,0.006,0.010,0.005,0.016,0.016,0.008,0.014,0.006,0.006,0.008,0.014,0.002,
    -0.002,0.005,0.011,0.002,0.002,0.002,0.006,0.009,0.005,0.009,0.004,0.010,-0.001,0.012,0.004,0.005,
    0.005,0.018,0.005,0.001,0.009,0.006,0.005,0.001,0.004,0.009,0.008,0.010,0.006,0.002,0.004,0.002,
    0.002,0.002,0.002,0.007,0.005,0.005,0.001,0.002,0.004,0.001,0.005,0.007,0.005,0.011,0.004,0.008,
    0.011,0.005,0.006,0.006,0.005,0.004,0.007,0.000,0.003,0.001,0.007,0.005,0.002,-0.000,0.006,0.002,
    0.008,-0.003,0.002,0.013,0.018,0.010,-0.003,0.004,0.010,0.011,0.003,0.013,0.004,0.002,0.001,0.003,
    0.013,0.009,0.014,-0.000,0.001,0.009,-0.003,-0.003,0.001,-0.003,0.002,0.006,0.002,0.008,0.002,0.005,
    0.011,0.009,0.003,0.004,0.009,0.000,0.003,0.004,0.009,0.006,0.005,0.003,0.011,-0.001,0.006,-0.002,
    -0.002,-0.001,0.005,0.007,0.007,0.010,0.010,0.006,-0.000,-0.001,0.002,0.006,-0.000,0.009,0.009,0.003,
    0.007,0.005,0.004,0.004,0.005,0.002,0.009,0.001,0.004,0.006,0.004,-0.007,0.007,0.002,0.005,0.006,
    -0.002,-0.005,0.005,0.002,0.003,0.005,0.013,0.012,-0.001,0.013,0.016,0.003,0.008,-0.006,0.007,0.007,
    0.013,-0.000,0.003,0.001,0.004,0.007,0.004,0.009,-0.003,0.002,-0.002,0.002,0.001,0.001,0.008,0.005,
    0.007,-0.000,0.005,0.005,0.008,0.004,0.011,0.003,0.005,0.000,0.007,-0.003,0.004,0.004,0.004,0.007,
    0.002,0.001,0.010,-0.001,0.002,0.001,0.001,0.005,0.006,0.005,0.008,0.001,0.005,0.004,0.005,0.004,
    0.002,0.004,0.008,0.004,0.009,0.004,0.014,-0.009,0.004,-0.000,0.000,0.005,0.002,-0.005,0.008,0.006,
    0.005,-0.006,0.001,0.007,0.012,-0.004,0.007,0.011,0.012,-0.002,0.002,0.017,0.019,-0.017,0.020,0.004,
    0.004,0.008,-0.002,0.006,0.002,0.005,0.012,0.011,-0.003,-0.001,0.025,-0.001,0.000,0.005,-0.001,-0.015,
    0.010,0.000,-0.003,-0.001,0.003,0.031,0.004,0.014,0.020,0.006,0.012,-0.005,0.024,0.003,0.003,0.016,
    0.009,-0.019,-0.019,-0.006,-0.010,-0.015,0.010,0.024,-0.003,-0.008,0.003,-0.002,0.023,-0.022,-0.007,0.038,
    0.017,-0.027,0.042,0.010,0.032,-0.022,0.051,0.029,0.002,0.003,0.005,0.016,0.003,-0.014,-0.000,0.009,
    -0.013,0.038,0.028,-0.008,0.031,0.017,0.055,-0.033,-0.053,0.073,-0.053,-0.032,0.074,0.053,-0.060,-0.058,
    0.121,0.042,0.051,0.008,0.122,0.034,-0.051,-0.036,0.103,-0.025,-0.055,0.073,0.016,-0.064,-0.052,0.111,
    0.085,-0.081,0.008,0.202,0.077,0.025,0.065,0.290,-0.002,-0.096,0.331,0.331,-0.079,0.070,0.467,0.246,
    -0.526,-0.281,0.451,-0.037,-0.880,0.214,0.847,-0.670,-0.752,2.921,2.253,-4.359,-4.025,8.680,0.724,1.383,
    };

and preview:

Now you just add the sorting of circles by radius if you want (now they are sorted by frequency)...

score 0 · Answer 2 · answered May 23 '23 at 09:48

0

As far as I remember, this is absolutely normal with DFT - the frequency domain values are basically mirrored thru the middle - amplitude of the i-th element is equal to the amplitude of the N-ith element (they are complex conjugates of each other). See the examples in https://en.wikipedia.org/wiki/Discrete_Fourier_transform

From back then when I was actually using it, we stored the data just up to N/2.

answered May 23 '23 at 09:48

MBobrik

318
1
6

Yes you are absolutely correct. I was viewing a preview sorted by amplitude instead of frequency but I didn't realize it then. Thank you! – Momin Ahmed May 23 '23 at 10:48
@MominAhmed this is true only for real input ... however for 2D real input you have to do both DFT/iDFT twice ... if you do this in complex domain from the start (almost no performance hit) then you need just single DFT/iDFT ... – Spektre May 23 '23 at 11:39

Unexpected amplitude values in my implementation of DFT in java

2 Answers2