# DFT-[FFT].awk
# The original awk version translated by Corona688 a moderator at:
# https://www.unix.com
# On this thread started by myself:
# https://www.unix.com/os-x-apple-/279710-slow-fft-ksh93-awk.html
#
# $VER DFT-[FFT].awk_19-09-2018_CC0_Licence-Public_Domain.
#
# Many thanks to Corona688 for his input.
#
# This is a modified version for the A1200 using ADE; WAY COOL!
# Don't feed it REAL/IMAG/K/T, those are local variables!

function fft(REAL_ARRAY, IMAG_ARRAY, K, T, SUMREAL, SUMIMAG, ANGLE)
{
        # PI to 14 decimal places.
        PI=3.14159265358979;
        for(K=1; K in REAL_ARRAY; K++)
        {
                SUMREAL=0;
                SUMIMAG=0;
                for(T=1; T in REAL_ARRAY; T++)
                {
                        ANGLE=(2*PI*(T-1)*(K-1))/N;
                        SUMREAL=SUMREAL+REAL_ARRAY[T]*cos(ANGLE)+IMAG_ARRAY[T]*sin(ANGLE);
                        SUMIMAG=SUMIMAG-REAL_ARRAY[T]*sin(ANGLE)+IMAG_ARRAY[T]*cos(ANGLE);
                }
                REAL[K]=SUMREAL;
                IMAG[K]=SUMIMAG;
        }
}

BEGIN {
        # REALSTR="1.0 1.0 1.0 1.0 1.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.5 0.5 0.5"
        # IMAGSTR="0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0"
        # 'IMAGSTR' can be builtin but not done in this DEMO.

        # Split into arrays, (INDEXES 1-16, not 0-15)!
        # N=<number_of_elements_in_the_REAL_ARRAY>
        # The total number of elements must be powers of 2 in size!
        N=split(REALSTR, REAL_ARRAY, " ");
        split(IMAGSTR, IMAG_ARRAY, " ");
        # Convert strings to floats.
        for(X in REAL_ARRAY) REAL_ARRAY[X]=REAL_ARRAY[X]+0.0;
        for(X in IMAG_ARRAY) IMAG_ARRAY[X]=IMAG_ARRAY[X]+0.0;

        fft(REAL_ARRAY, IMAG_ARRAY);

        printf("Real:\n");
        for(X=1; X in REAL; X++)
                printf(" %.5f", REAL[X]);
        printf("\n\n");

        printf("Imaginary:\n");
        for(X=1; X in IMAG; X++)
                printf(" %.5f", IMAG[X]);
        printf("\n\n");

        printf("Absolute Values:\n");
        for(X=1; X<=N; X++)
                printf(" %.5f", sqrt(((REAL[X])^2)+((IMAG[X])^2)));
        printf("\n");

# Call in this DEMO as:
# awk -f DFT-[FFT].awk -v REALSTR="1.0 1.0 1.0 1.0 1.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.5 0.5 0.5" -v IMAGSTR="0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0" /dev/null
# OR, use this shell script to call it:
# #!/bin/sh
# # DFT.sh
# awk -f DFT-[FFT].awk -v REALSTR="1.0 1.0 1.0 1.0 1.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.5 0.5 0.5" -v IMAGSTR="0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0" /dev/null
#
# Real:
#  8.50000 3.63782 -1.70711 0.05143 1.50000 -0.17275 -0.29289 0.48350 0.50000 0.48350 -0.29289 -0.17275 1.50000 0.05143 -1.70711 3.63782
#
# Imaginary:
#  0.00000 -1.93071 -0.50000 -0.24147 -1.00000 0.46564 0.50000 -1.22361 0.00000 1.22361 -0.50000 -0.46564 1.00000 0.24147 0.50000 1.93071
#
# Absolute Values:
#  8.50000 4.11842 1.77882 0.24688 1.80278 0.49665 0.57947 1.31567 0.50000 1.31567 0.57947 0.49665 1.80278 0.24688 1.77882 4.11842
}