Implemente a Transformada discreta de Fourier (DFT) para uma sequência de qualquer comprimento. Isso pode ser implementado como uma função ou um programa e a sequência pode ser dada como um argumento ou usando entrada padrão.

O algoritmo calculará um resultado com base na DFT padrão na direção direta. A sequência de entrada tem comprimento Ne consiste em [x(0), x(1), ..., x(N-1)]. A sequência de saída terá o mesmo comprimento e consiste em [X(0), X(1), ..., X(N-1)]onde cada um X(k)é definido pela relação abaixo.

Regras

Isso é código-golfe, então a solução mais curta vence.
Os componentes internos que calculam a DFT nas direções para frente ou para trás (também conhecidos como inversos) não são permitidos.
Imprecisões de ponto flutuante não serão contadas contra você.

Casos de teste

DFT([1, 1, 1, 1]) = [4, 0, 0, 0]
DFT([1, 0, 2, 0, 3, 0, 4, 0]) = [10, -2+2j, -2, -2-2j, 10, -2+2j, -2, -2-2j]
DFT([1, 2, 3, 4, 5]) = [15, -2.5+3.44j, -2.5+0.81j, -2.5-0.81j, -2.5-3.44j]
DFT([5-3.28571j, -0.816474-0.837162j, 0.523306-0.303902j, 0.806172-3.69346j, -4.41953+2.59494j, -0.360252+2.59411j, 1.26678+2.93119j] = [2, -3j, 5, -7j, 11, -13j, 17]

Socorro

Havia um desafio anterior para encontrar a DFT usando um algoritmo FFT para seqüências com comprimentos iguais a uma potência de 2. Você pode encontrar alguns truques lá que podem ajudá-lo aqui. Lembre-se de que esse desafio não o limita a nenhuma complexidade e também exige que sua solução funcione para sequências de qualquer tamanho.

code-golf math milhas
fonte

2

Geléia , 16 15 bytes

LR’µ×'÷L-*²³÷S€

Experimente online!

Como funciona

LR’µ×'÷L-*²³÷S€  Main link. Argument [x(0), ..., x(N-1)].

L                Length; yield N.
 R               Range; yield [1, ..., N].
  ’              Decrement; yield [0, ..., N-1].
   µ             Begin a new, monadic chain. Argument: [0, ..., N-1]
    ×'           Spawned multiply [0, ..., N-1] with itself, yielding the matrix
                 of all possible products k×n.
      ÷L         Divide each product by N.
        -*       Compute (-1)**(kn÷L) for each kn.
          ²      Square each result, computing (-1)**(2kn÷L).
           ³÷    Divide [x(0), ..., x(N-1)] by the results.
             S€  Compute the sum for each row, i.e., each X(k).

Dennis
fonte

ninja'd :(

Leaky Nun

5

Python 3, 77 bytes

lambda x,e=enumerate:[sum(t/1j**(4*k*n/len(x))for n,t in e(x))for k,_ in e(x)]

Teste em Ideone .

O código usa a fórmula equivalente

Fórmula

Dennis
fonte

Uau, figuras enormes. É bom ver as fórmulas equivalentes que podem permitir um código mais curto.

milhas

4

J, 30 20 bytes

3 bytes graças a @miles .

Usa o fato de que e^ipi = -1 .

A fórmula se torna X_k = sum(x_n / ((-1)^(2nk/N))).

+/@:%_1^2**/~@i.@#%#

Uso

>> DCT =: +/@:%_1^2**/~@i.@#%#
>> DCT 1 2 3 4 5
<< 15 _2.5j3.44095 _2.5j0.812299 _2.5j_0.812299 _2.5j_3.44095

onde >>é STDIN e <<STDOUT.

"Imprecisões de ponto flutuante não serão contadas contra você."

Freira Furada
fonte

3

MATL , 20 16 bytes

-1yn:qt!Gn/E*^/s

Input é um vetor de coluna, ou seja, substitua vírgulas por ponto e vírgula:

[1; 1; 1; 1]
[1; 0; 2; 0; 3; 0; 4; 0]
[1; 2; 3; 4; 5]
[5-3.28571j; -0.816474-0.837162j; 0.523306-0.303902j; 0.806172-3.69346j; -4.41953+2.59494j; -0.360252+2.59411j; 1.26678+2.93119j]

Isso usa a fórmula na resposta de Leaky Nun , com base nos fatos que exp ( iπ ) = -1, e que a operação de potência do MATL com expoente não inteiro produz (como na maioria das linguagens de programação) o resultado do ramo principal .

Experimente online!

Devido ao espaçamento estranho da Oitava com números complexos, as partes reais e imaginárias são separadas por um espaço, assim como as diferentes entradas do vetor resultante. Se isso parecer muito feio, adicione um !no final ( 17 bytes ) para ter cada entrada da saída em uma linha diferente.

Explicação

-1      % Push -1
y       % Get input implicitly. Push a copy below and one on top of -1
n:q     % Row vector [0 1 ... N-1] where N is implicit input length
t!      % Duplicate and transpose: column vector
Gn      % Push input length
/       % Divide
E       % Multiply by 2
*       % Multiply, element-wise with broadcast. Gives the exponent as a matrix
^       % Power (base is -1), element-wise. Gives a matrix
/       % Divide matrix by input (column vector), element-wise with broadcast
s       % Sum

Luis Mendo
fonte

2

Pyth, 30

ms.e*b^.n1****c_2lQk.n0d.j0)QU

Suíte de teste

Abordagem muito ingênua, apenas uma implementação da fórmula. É executado em vários problemas menores de ponto flutuante com valores que devem ser inversos aditivos, resultando em valores ligeiramente fora de zero.

Estranhamente .j, parece não funcionar sem argumentos, mas não tenho certeza se estou usando corretamente.

FryAmTheEggman
fonte

11

Parabéns por 10k !!

Luis Mendo

2

Pitão, 18 bytes

Usa o fato de que e^ipi = -1 .

A fórmula se torna X_k = sum(x_n / ((-1)^(2nk/N))).

ms.ecb^_1*cyklQdQU

Suíte de teste.

Freira Furada
fonte

2

Julia, 45 bytes

~=endof
!x=sum(x./im.^(4(r=0:~x-1).*r'/~x),1)

Experimente online!

O código usa a fórmula equivalente

Fórmula

Dennis
fonte

2

Python 2, 78 bytes

l=input();p=1
for _ in l:print reduce(lambda a,b:a*p+b,l)*p;p*=1j**(4./len(l))

O polinômio é avaliado para cada potência pde 1j**(4./len(l)).

A expressão reduce(lambda a,b:a*p+b,l)avalia o polinômio dado por lno valor pvia método de Horner:

reduce(lambda a,b:a*10+b,[1,2,3,4,5])
=> 12345

Exceto, a lista de entrada externa é revertida, com termo constante no final. Poderíamos revertê-lo, mas, como p**len(l)==1para os coeficientes de Fourier, podemos usar um truque para inverter pe multiplicar todo o resultado porp .

Algumas tentativas de igual comprimento:

l=input();i=0
for _ in l:print reduce(lambda a,b:(a+b)*1j**i,l,0);i+=4./len(l)

l=input();i=0
for _ in l:print reduce(lambda a,b:a*1j**i+b,l+[0]);i+=4./len(l)

Em função de mais 1 byte (79):

lambda l:[reduce(lambda a,b:a*1j**(i*4./len(l))+b,l+[0])for i in range(len(l))]

Uma tentativa de recursão (80):

f=lambda l,i=0:l[i:]and[reduce(lambda a,b:(a+b)*1j**(i*4./len(l)),l,0)]+f(l,i+1)

Simulação iterativa reduce(80):

l=input();p=1;N=len(l)
exec"s=0\nfor x in l:s=s*p+x\nprint s*p;p*=1j**(4./N);"*N

xnor
fonte

2

C (gcc) , 86 78 bytes

k;d(a,b,c)_Complex*a,*b;{for(k=c*c;k--;)b[k/c]+=a[k%c]/cpow(1i,k/c*k%c*4./c);}

Experimente online!

Isso pressupõe que o vetor de saída seja zerado antes do uso.

teto
fonte

1

Python 2, 89 bytes

Usa o fato de quee^ipi = -1 .

A fórmula se torna X_k = sum(x_n / ((-1)^(2nk/N))).

lambda a:[sum(a[x]/(-1+0j)**(x*y*2./len(a))for x in range(len(a)))for y in range(len(a))]

Ideone it!

Freira Furada
fonte

Publique isso como uma resposta separada!

Leaky Nun

Tudo bem, se você diz.

Dennis

1

Mathematica, 49 48 47 bytes

Total[I^Array[4(+##-##-1)/n&,{n=Length@#,n}]#]&

Com base na fórmula da solução @Dennis ' .

milhas
fonte

1

Axioma, 81 bytes

g(x)==(#x<2=>x;[reduce(+,[x.j/%i^(4*k*(j-1)/#x)for j in 1..#x])for k in 0..#x-1])

usando a fórmula de alguém postar aqui. Resultados

(6) -> g([1,1,1,1])
   (6)  [4,0,0,0]
                                    Type: List Expression Complex Integer
(7) -> g([1,2,3,4])
   (7)  [10,- 2 + 2%i,- 2,- 2 - 2%i]
                                    Type: List Expression Complex Integer
(8) -> g([1,0,2,0,3,0,4,0])
   (8)  [10,- 2 + 2%i,- 2,- 2 - 2%i,10,- 2 + 2%i,- 2,- 2 - 2%i]
                                    Type: List Expression Complex Integer
(11) -> g([1,2,3,4,5])
   (11)
        5+--+4       5+--+3    5+--+2      5+--+
        \|%i   + 5%i \|%i   - 4\|%i   - 3%i\|%i  + 2
   [15, --------------------------------------------,
                           5+--+4
                           \|%i
    5+--+4       5+--+3    5+--+2      5+--+
    \|%i   + 3%i \|%i   - 5\|%i   - 2%i\|%i  + 4
    --------------------------------------------,
                       5+--+4
                       \|%i
    5+--+4       5+--+3    5+--+2      5+--+
    \|%i   + 4%i \|%i   - 2\|%i   - 5%i\|%i  + 3
    --------------------------------------------,
                       5+--+4
                       \|%i
    5+--+4       5+--+3    5+--+2      5+--+
    \|%i   + 2%i \|%i   - 3\|%i   - 4%i\|%i  + 5
    --------------------------------------------]
                       5+--+4
                       \|%i
                                    Type: List Expression Complex Integer
(12) -> g([1,2,3,4,5.])
   (12)
   [15.0, - 2.5 + 3.4409548011 779338455 %i, - 2.5 + 0.8122992405 822658154 %i,
    - 2.5 - 0.8122992405 822658154 %i, - 2.5 - 3.4409548011 779338455 %i]
                                      Type: List Expression Complex Float

RosLuP
fonte

0

Oitava , 43 39 bytes

@(x)j.^(-4*(t=0:(s=rows(x))-1).*t'/s)*x

Experimente online!

Multiplica o vetor de entrada pela matriz DFT.

teto
fonte

Calcular a transformação discreta de Fourier

Regras

Casos de teste

Socorro

Respostas:

Geléia , 16 15 bytes

Como funciona

Python 3, 77 bytes

J, 30 20 bytes

Uso

MATL , 20 16 bytes

Explicação

Pyth, 30

Pitão, 18 bytes

Julia, 45 bytes

Python 2, 78 bytes

C (gcc) , 86 78 bytes

Python 2, 89 bytes

Mathematica, 49 48 47 bytes

Axioma, 81 bytes

Oitava , 43 39 bytes