MathSpecialFunctionsDiscreteFourierTransform

// This source code is subject to the terms of the Mozilla Public License 2.0 at https://mozilla.org/MPL/2.0/
// © RicardoSantos

//@version=5

//@description Method for Complex Discrete Fourier Transform (DFT).
library(title='MathSpecialFunctionsDiscreteFourierTransform')

import RicardoSantos/MathComplexCore/1 as complex
import RicardoSantos/MathComplexOperator/1 as complex_op
import RicardoSantos/MathComplexArray/1 as complex_array

// @function Complex Discrete Fourier Transform (DFT).
// @param inputs float array, pseudo complex array of paired values [(a0+b0i), ...].
// @param inverse bool, invert the transformation.
// @returns float array, pseudo complex array of paired values [(a0+b0i), ...].
export dft (float[] _inputs, bool _inverse) => //{
    int _size = int(math.floor(array.size(id=_inputs) / 2))
    float _pi = 3.14159265359
    float _pi2 = _inverse ? 2.0 * _pi : -2.0 * _pi
    float _invs = 1.0 / _size
//| @return:
//|     _output: Complex array
    float[] _output = complex_array.new(_size, complex.new(0.0, 0.0))

    for _y = 0 to _size - 1 by 1
        for _x = 0 to _size - 1 by 1
            _a = _pi2 * _y * _x * _invs
            _ca = math.cos(_a)

            _sa = -math.sin(_a)
            float[] _complex_input = complex_array.get(_inputs, _x)
            float[] _complex_output = complex_array.get(_output, _y)
            float _input_real = complex.get_real(_complex_input)
            float _input_imaginary = complex.get_imaginary(_complex_input)
            float _output_real = complex.get_real(_complex_output)
            float _output_imaginary = complex.get_imaginary(_complex_output)
            float _add_real = _output_real + _input_real * _ca - _input_imaginary * _sa
            float _add_imaginary = _output_imaginary + _input_real * _sa + _input_imaginary * _ca
            complex_array.set(_output, _y, complex.new(_add_real, _add_imaginary))

        if not _inverse
            float[] _mult = complex_op.multiply(complex_array.get(_output, _y), complex.new(_invs, _invs))
            complex_array.set(_output, _y, _mult)
    _output
//{ usage:
var float[] inputs = complex_array.new(8, complex.new(0.0, 0.0))

if barstate.islast
    for _i = 0 to 8 by 1
        complex_array.set(inputs, _i, complex.new(close[_i], _i))

// plot(series=f_Sre(0), color=acol, linewidth=aline, style=plot.style_histogram, transp=20, histbase=0, offset=-0, show_last=1)
// plot(series=f_Sim(0), color=bcol, linewidth=bline, style=plot.style_histogram, transp=20, histbase=0, offset=-0, show_last=1)

float[] S = dft(inputs, false)
float[] A = dft(S, true)

var table T = table.new(position.bottom_right, 3, 9, border_width=1)
table.cell(T, 0, 0, 'Original', text_color=color.silver, text_size=size.small, bgcolor=color.gray)
table.cell(T, 1, 0, 'DFT', text_color=color.silver, text_size=size.small, bgcolor=color.gray)
table.cell(T, 2, 0, 'Inverse', text_color=color.silver, text_size=size.small, bgcolor=color.gray)

if barstate.islast
    for _l = 0 to math.floor(array.size(inputs) / 2) - 1 by 1
        table.cell(T, 0, _l+1, str.tostring(complex_array.get(inputs, _l)), text_size=size.small, bgcolor=color.silver)
        table.cell(T, 1, _l+1, str.tostring(complex_array.get(S, _l)), text_size=size.small, bgcolor=color.silver)
        table.cell(T, 2, _l+1, str.tostring(complex_array.get(A, _l)), text_size=size.small, bgcolor=color.silver)

// interface to validate if there is values:
f_Sre(_i) => array.size(S) > 0 ? complex.get_real(complex_array.get(S, _i)) : na
f_Sim(_i) => array.size(S) > 0 ? complex.get_imaginary(complex_array.get(S, _i)) : na

color acol = input(#0000ff50)
color bcol = input(#8080a050)

int aline = 8
int bline = 3
plot(series=f_Sre(1), color=acol, linewidth=aline, style=plot.style_histogram, histbase=0, offset=-1, show_last=1)
plot(series=f_Sim(1), color=bcol, linewidth=bline, style=plot.style_histogram, histbase=0, offset=-1, show_last=1)
plot(series=f_Sre(2), color=acol, linewidth=aline, style=plot.style_histogram, histbase=0, offset=-2, show_last=1)
plot(series=f_Sim(2), color=bcol, linewidth=bline, style=plot.style_histogram, histbase=0, offset=-2, show_last=1)
plot(series=f_Sre(3), color=acol, linewidth=aline, style=plot.style_histogram, histbase=0, offset=-3, show_last=1)
plot(series=f_Sim(3), color=bcol, linewidth=bline, style=plot.style_histogram, histbase=0, offset=-3, show_last=1)
plot(series=f_Sre(4), color=acol, linewidth=aline, style=plot.style_histogram, histbase=0, offset=-4, show_last=1)
plot(series=f_Sim(4), color=bcol, linewidth=bline, style=plot.style_histogram, histbase=0, offset=-4, show_last=1)
plot(series=f_Sre(5), color=acol, linewidth=aline, style=plot.style_histogram, histbase=0, offset=-5, show_last=1)
plot(series=f_Sim(5), color=bcol, linewidth=bline, style=plot.style_histogram, histbase=0, offset=-5, show_last=1)
plot(series=f_Sre(6), color=acol, linewidth=aline, style=plot.style_histogram, histbase=0, offset=-6, show_last=1)
plot(series=f_Sim(6), color=bcol, linewidth=bline, style=plot.style_histogram, histbase=0, offset=-6, show_last=1)
plot(series=f_Sre(7), color=acol, linewidth=aline, style=plot.style_histogram, histbase=0, offset=-7, show_last=1)
plot(series=f_Sim(7), color=bcol, linewidth=bline, style=plot.style_histogram, histbase=0, offset=-7, show_last=1)
plot(series=f_Sre(8), color=acol, linewidth=aline, style=plot.style_histogram, histbase=0, offset=-8, show_last=1)
plot(series=f_Sim(8), color=bcol, linewidth=bline, style=plot.style_histogram, histbase=0, offset=-8, show_last=1)
//{ remarks:
//      https://en.wikipedia.org/wiki/Discrete_Fourier_transform
//      https://www.tradingview.com/script/XXBfMnVE-Function-Discrete-Fourier-Transform/
//      https://www.gaussianwaves.com/2015/11/interpreting-fft-results-complex-dft-frequency-bins-and-fftshift/
//}}}