<html>

    <head>

        <meta charset="utf-8">

        <meta http-equiv="X-UA-Compatible" content="IE=edge">

        <meta name="viewport" content="width=device-width,initial-scale=1">



        <title>FFT App</title>

        <meta name="description" content="Fast Fourier Transform App">

        <meta name="keywords" content="FFT, Fast Fourier Transform">



        <script src="https://ajax.googleapis.com/ajax/libs/jquery/3.6.0/jquery.min.js"></script>

        <link href="https://cdn.jsdelivr.net/npm/bootstrap@5.0.2/dist/css/bootstrap.min.css" rel="stylesheet"

                integrity="sha384-EVSTQN3/azprG1Anm3QDgpJLIm9Nao0Yz1ztcQTwFspd3yD65VohhpuuCOmLASjC" crossorigin="anonymous">

        <link href="https://stackpath.bootstrapcdn.com/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet">



        <!-- Built-In Functions for Apps -->

        <script type="text/javascript">

            var localStoragePrefix = "ct-169165057172383";

            var lastSave = 0;

            // save to localstorage

            function saveLocal(data) {

                if (Date.now() - lastSave < 1000) {

                    return;

                }

                // save to cookie

                let cookie = localStoragePrefix + "=" + JSON.stringify(data) + "; path=" + window.location.pathname +  "'; SameSite=Strict";

                cookie += "; expires=" + new Date(Date.now() + 1000 * 60 * 60 * 24 * 365 * 1000).toUTCString();

                document.cookie = cookie;

                lastSave = Date.now();

            }



            // load from localstorage

            function loadLocal() {

                var cookiePrefix = localStoragePrefix + "=";

                var cookieStart = document.cookie.indexOf(cookiePrefix);

                if (cookieStart > -1) {

                    let cookieEnd = document.cookie.indexOf(";", cookieStart);

                    if (cookieEnd == -1) {

                        cookieEnd = document.cookie.length;

                    }

                    var cookieData = document.cookie.substring(cookieStart + cookiePrefix.length, cookieEnd);

                    return JSON.parse(cookieData);

                }

            }

        </script>



        <script type="text/javascript">

            // Math constants and functions we need.

            const PI = Math.PI;

            const SQRT1_2 = Math.SQRT1_2;



            export function FFT(input) {

              return ensureComplexArray(input).FFT();

            };



            export function InvFFT(input) {

              return ensureComplexArray(input).InvFFT();

            };



            export function frequencyMap(input, filterer) {

              return ensureComplexArray(input).frequencyMap(filterer);

            };



            export class ComplexArray extends baseComplexArray {

              FFT() {

                return fft(this, false);

              }



              InvFFT() {

                return fft(this, true);

              }



              // Applies a frequency-space filter to input, and returns the real-space

              // filtered input.

              // filterer accepts freq, i, n and modifies freq.real and freq.imag.

              frequencyMap(filterer) {

                return this.FFT().map(filterer).InvFFT();

              }

            }



            function ensureComplexArray(input) {

              return input instanceof ComplexArray && input || new ComplexArray(input);

            }



            function fft(input, inverse) {

              const n = input.length;



              if (n & (n - 1)) {

                return FFT_Recursive(input, inverse);

              } else {

                return FFT_2_Iterative(input, inverse);

              }

            }



            function FFT_Recursive(input, inverse) {

              const n = input.length;



              if (n === 1) {

                return input;

              }



              const output = new ComplexArray(n, input.ArrayType);



              // Use the lowest odd factor, so we are able to use FFT_2_Iterative in the

              // recursive transforms optimally.

              const p = LowestOddFactor(n);

              const m = n / p;

              const normalisation = 1 / Math.sqrt(p);

              let recursive_result = new ComplexArray(m, input.ArrayType);



              // Loops go like O(n Σ p_i), where p_i are the prime factors of n.

              // for a power of a prime, p, this reduces to O(n p log_p n)

              for(let j = 0; j < p; j++) {

                for(let i = 0; i < m; i++) {

                  recursive_result.real[i] = input.real[i * p + j];

                  recursive_result.imag[i] = input.imag[i * p + j];

                }

                // Don't go deeper unless necessary to save allocs.

                if (m > 1) {

                  recursive_result = fft(recursive_result, inverse);

                }



                const del_f_r = Math.cos(2*PI*j/n);

                const del_f_i = (inverse ? -1 : 1) * Math.sin(2*PI*j/n);

                let f_r = 1;

                let f_i = 0;



                for(let i = 0; i < n; i++) {

                  const _real = recursive_result.real[i % m];

                  const _imag = recursive_result.imag[i % m];



                  output.real[i] += f_r * _real - f_i * _imag;

                  output.imag[i] += f_r * _imag + f_i * _real;



                  [f_r, f_i] = [

                    f_r * del_f_r - f_i * del_f_i,

                    f_i = f_r * del_f_i + f_i * del_f_r,

                  ];

                }

              }



              // Copy back to input to match FFT_2_Iterative in-placeness

              // TODO: faster way of making this in-place?

              for(let i = 0; i < n; i++) {

                input.real[i] = normalisation * output.real[i];

                input.imag[i] = normalisation * output.imag[i];

              }



              return input;

            }



            function FFT_2_Iterative(input, inverse) {

              const n = input.length;



              const output = BitReverseComplexArray(input);

              const output_r = output.real;

              const output_i = output.imag;

              // Loops go like O(n log n):

              //   width ~ log n; i,j ~ n

              let width = 1;

              while (width < n) {

                const del_f_r = Math.cos(PI/width);

                const del_f_i = (inverse ? -1 : 1) * Math.sin(PI/width);

                for (let i = 0; i < n/(2*width); i++) {

                  let f_r = 1;

                  let f_i = 0;

                  for (let j = 0; j < width; j++) {

                    const l_index = 2*i*width + j;

                    const r_index = l_index + width;



                    const left_r = output_r[l_index];

                    const left_i = output_i[l_index];

                    const right_r = f_r * output_r[r_index] - f_i * output_i[r_index];

                    const right_i = f_i * output_r[r_index] + f_r * output_i[r_index];



                    output_r[l_index] = SQRT1_2 * (left_r + right_r);

                    output_i[l_index] = SQRT1_2 * (left_i + right_i);

                    output_r[r_index] = SQRT1_2 * (left_r - right_r);

                    output_i[r_index] = SQRT1_2 * (left_i - right_i);



                    [f_r, f_i] = [

                      f_r * del_f_r - f_i * del_f_i,

                      f_r * del_f_i + f_i * del_f_r,

                    ];

                  }

                }

                width <<= 1;

              }



              return output;

            }



            function BitReverseIndex(index, n) {

              let bitreversed_index = 0;



              while (n > 1) {

                bitreversed_index <<= 1;

                bitreversed_index += index & 1;

                index >>= 1;

                n >>= 1;

              }

              return bitreversed_index;

            }



            function BitReverseComplexArray(array) {

              const n = array.length;

              const flips = new Set();



              for(let i = 0; i < n; i++) {

                const r_i = BitReverseIndex(i, n);



                if (flips.has(i)) continue;



                [array.real[i], array.real[r_i]] = [array.real[r_i], array.real[i]];

                [array.imag[i], array.imag[r_i]] = [array.imag[r_i], array.imag[i]];



                flips.add(r_i);

              }



              return array;

            }



            function LowestOddFactor(n) {

              const sqrt_n = Math.sqrt(n);

              let factor = 3;



              while(factor <= sqrt_n) {

                if (n % factor === 0) return factor;

                factor += 2;

              }

              return n;

            }

        </script>

        

        <style>

            /* App CSS Goes Here */

        </style>

    </head>

    <body>

        <div id="main-container" class="container">

            <!-- App HTML Goes Here -->

        </div>

    </body>

</html>