#include <iostream.h>
#include <math.h>
#include <iomanip.h>
#include <stdlib.h>
#include <fstream.h>
#include <string>
#include <process.h>
#include<stdio.h>

void four1(double data[65], int nn, int isign)
{
	int n,j,i,m,mmax,istep;
	double tempr,tempi,theta,wpr,wpi,wr,wi,wtemp;
    n = 2 * nn;
    j = 1;
    for (i = 1;i<=n ;i=i+2)
	{
        if( j > i)
		{
            tempr = data[j];
            tempi = data[j + 1];
            data[j] = data[i];
            data[j + 1] = data[i + 1];
            data[i] = tempr;
            data[i + 1] = tempi;
        }
        m = n / 2;
        while (m >= 2 && j > m)
		{
            j = j - m;
            m = m / 2;
        }
        j = j + m;
    }
    mmax = 2;
    while(n > mmax)
	{
        istep = 2 * mmax;
        theta = 6.28318530717959 / (isign * mmax);
        wpr = -2.0 * sin(0.5 * theta)*sin(0.5 * theta);
        wpi = sin(theta);
        wr = 1.0;
        wi = 0.0;
        for( m = 1;m<=mmax;m=m+2)
		{
            for (i = m ;i<=n;i=i+istep)
			{
                j = i + mmax;
                tempr = double(wr) * data[j] - double(wi) * data[j + 1];
                tempi = double(wr) * data[j + 1] + double(wi) * data[j];
                data[j] = data[i] - tempr;
                data[j + 1] = data[i + 1] - tempi;
                data[i] = data[i] + tempr;
                data[i + 1] = data[i + 1] + tempi;
            }
            wtemp = wr;
            wr = wr * wpr - wi * wpi + wr;
            wi = wi * wpr + wtemp * wpi + wi;
        }
        mmax = istep;
    }
}

void realft(double data[], int &n, int &isign)
{
	int n2p3,i,i1,i2,i3,i4;
	double theta,c1,c2,wpr,wpi,wr,wi,wrs,wis,h1r,h1i,h2r,h2i,wtemp,wri;
	wri=0.0;
    theta = 6.28318530717959 / 2.0 / n;
    c1 = 0.5;
    if (isign == 1)
	{
        c2 = -0.5;
        four1(data, n, 1);
	}
    else
	{
        c2 = 0.5;
        theta = -theta;
	}
    wpr = -2.0 * sin(0.5 * theta)*sin(0.5 * theta);
    wpi = sin(theta);
    wr = 1.0 + wpr;
    wi = wpi;
    n2p3 = 2 * n + 3;
    for (i = 2; i<=n / 2 + 1; i++)
	{
        i1 = 2 * i - 1;
        i2 = i1 + 1;
        i3 = n2p3 - i2;
        i4 = i3 + 1;
        wrs = float(wr);
        wis = float(wi);
        h1r = c1 * (data[i1] + data[i3]);
        h1i = c1 * (data[i2] - data[i4]);
        h2r = -c2 * (data[i2] + data[i4]);
        h2i = c2 * (data[i1] - data[i3]);
        data[i1] = h1r + wrs * h2r - wis * h2i;
        data[i2] = h1i + wrs * h2i + wis * h2r;
        data[i3] = h1r - wrs * h2r + wis * h2i;
        data[i4] = -h1i + wrs * h2i + wis * h2r;
        wtemp = wr;
        wr = wr * wpr - wi * wri + wr;
        wi = wi * wpr + wtemp * wpi + wi;
    }
    if( isign == 1 )
	{
        h1r = data[1];
        data[1] = h1r + data[2];
        data[2] = h1r - data[2];
	}
    else
	{
        h1r = data[1];
        data[1] = c1 * (h1r + data[2]);
        data[2] = c1 * (h1r - data[2]);
        four1(data, n, -1);
    }
}

void main()
{
    //program d12r3
    //driver for routine realft
	int i,np,npp2,n,temp,j,temp1;
    double data[35], size1[33],eps,width1,per,big,small,scal1,nlim;
	temp=1;
	temp1=-1;
    eps = 0.001;
    np = 32;
    npp2 = np + 2;
    width1 = 50.0;
    const double pi = 3.14159;
    n = np / 2;
    cout<<"Period of sinusoid in channels (2-"<<np<<")"<<endl;
    per = 32;
	cout<<per<<endl;
    if (per <= 0.0)
		exit(1);
    for (i = 1; i<=np; i++)
	{
        data[i] = cos(2.0 * pi * (i - 1) / per);
    }
    realft(data, n, temp);
    big = -10000000000.0;
    for( i = 1; i<=n; i++)
	{
        size1[i] = sqrt(data[2 * i - 1]*data[2 * i - 1] + data[2 * i]*data[2 * i]);
        if (i == 1)
		    size1[i] = data[i];
        if (size1[i] > big )
			big = size1[i];
    }
    scal1 = width1 / big;
    for (i = 1; i<=n; i++)
	{
        nlim = scal1 * size1[i] + eps;
        cout<<setw(4)<<i<<"  ";
        for (j = 1; j<=nlim + 1; j++)
		{
            cout<<"*";
		}
		cout<<endl;
    }
    realft(data, n, temp1);
    big = -10000000000.0;
    small = 10000000000.0;
    for (i = 1;i<=np;i++)
	{
        if (data[i] < small)
			small = data[i];
        if (data[i] > big)
			big = data[i];
    }
    scal1 = width1 / (big - small);
    for (i = 1; i<=np; i++)
	{
        nlim = int(scal1 * (data[i] - small) + eps);
        cout<<setw(4)<<i<<"  ";
        for (j = 1; j<=nlim + 1; j++)
		{
            cout<<"*";
        }
		cout<<endl;
    }
}