Implementieren Sie die diskrete Fourier-Transformation (DFT) für eine Sequenz beliebiger Länge. Dies kann entweder als Funktion oder als Programm implementiert werden, und die Sequenz kann entweder als Argument oder unter Verwendung einer Standardeingabe angegeben werden.

Der Algorithmus berechnet ein Ergebnis basierend auf der Standard-DFT in Vorwärtsrichtung. Die Eingabesequenz hat Länge Nund besteht aus [x(0), x(1), ..., x(N-1)]. Die Ausgabesequenz hat die gleiche Länge und besteht darin, [X(0), X(1), ..., X(N-1)]wo jede X(k)durch die folgende Beziehung definiert ist.

Regeln

Dies ist Code-Golf, also gewinnt die kürzeste Lösung.
Builtins, die die DFT in Vorwärts- oder Rückwärtsrichtung (auch als inverse Richtung bezeichnet) berechnen, sind nicht zulässig.
Gleitkomma-Ungenauigkeiten werden nicht gegen Sie angerechnet.

Testfälle

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]

Hilfe

Es gab zuvor eine Herausforderung , die DFT mithilfe eines FFT-Algorithmus für Sequenzen mit Längen gleich einer Potenz von 2 zu finden. Dort finden Sie möglicherweise einige Tricks, die Ihnen hier helfen könnten. Denken Sie daran, dass diese Herausforderung Sie nicht auf Komplexität beschränkt und dass Ihre Lösung auch für Sequenzen beliebiger Länge geeignet ist.

code-golf math Meilen
quelle

2

Gelee , 16 15 Bytes

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

Probieren Sie es online aus!

Wie es funktioniert

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
quelle

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)]

Testen Sie es auf Ideone .

Der Code verwendet die entsprechende Formel

Formel

Dennis
quelle

Wow, riesige Figuren. Es ist schön, die entsprechenden Formeln zu sehen, die kürzeren Code ermöglichen können.

Meilen

4

J, 30 bis 20 Bytes

3 Bytes dank @miles .

Verwendet die Tatsache, dass e^ipi = -1.

Die Formel wird X_k = sum(x_n / ((-1)^(2nk/N))).

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

Verwendungszweck

>> 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

wo >>ist STDIN und <<ist STDOUT.

"Gleitkomma-Ungenauigkeiten werden nicht gegen Sie angerechnet."

Undichte Nonne
quelle

3

MATL , 20 16 Bytes

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

Die Eingabe ist ein Spaltenvektor, dh Sie ersetzen Kommas durch Semikolons:

[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]

Dies verwendet die Formel in der Antwort von Leaky Nun , basierend auf den Tatsachen, dass exp ( iπ ) = −1 ist und dass die Potenzoperation von MATL mit einem nicht ganzzahligen Exponenten (wie in den meisten Programmiersprachen) das Hauptverzweigungsergebnis erzeugt .

Probieren Sie es online aus!

Aufgrund des seltsamen Abstands von Octave mit komplexen Zahlen sind der Real- und der Imaginärteil durch ein Leerzeichen getrennt, ebenso wie die verschiedenen Einträge des resultierenden Vektors. Wenn das zu hässlich aussieht, fügen Sie !am Ende ein ( 17 Byte ) hinzu, damit jeder Eintrag der Ausgabe in einer anderen Zeile steht.

Erläuterung

-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
quelle

2

Pyth, 30

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

Testsuite

Sehr naiver Ansatz, nur eine Umsetzung der Formel. Stößt auf verschiedene kleinere Gleitkommaprobleme mit Werten, die additiv umgekehrt werden sollten, um Werte zu erhalten, die leicht von Null abweichen.

Seltsamerweise .jscheint es ohne Argumente nicht zu funktionieren, aber ich bin mir nicht sicher, ob ich es richtig verwende.

FryAmTheEggman
quelle

1

Herzlichen Glückwunsch zu 10k !!

Luis Mendo

2

Pyth, 18 Bytes

Verwendet die Tatsache, dass e^ipi = -1.

Die Formel wird X_k = sum(x_n / ((-1)^(2nk/N))).

ms.ecb^_1*cyklQdQU

Testsuite.

Undichte Nonne
quelle

2

Julia, 45 Bytes

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

Probieren Sie es online aus!

Der Code verwendet die entsprechende Formel

Formel

Dennis
quelle

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))

Das Polynom wird für jede Potenz pvon ausgewertet 1j**(4./len(l)).

Der Ausdruck reduce(lambda a,b:a*p+b,l)wertet das Polynom aus, das durch lden Wert püber die Horner-Methode gegeben ist:

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

Außer, dass unsere Eingabeliste umgekehrt ist, mit einem konstanten Term am Ende. Wir könnten es umkehren, aber weil p**len(l)==1wir für Fourier-Koeffizienten einen Hack des Invertierens pund Multiplizierens des gesamten Ergebnisses mit verwenden können p.

Einige Versuche gleicher Länge:

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)

Als Funktion für 1 Byte mehr (79):

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

Ein Rekursionsversuch (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)

Iterativ simulieren 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
quelle

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);}

Probieren Sie es online aus!

Dies setzt voraus, dass der Ausgabevektor vor der Verwendung auf Null gesetzt wird.

Deckenkatze
quelle

1

Python 2, 89 Bytes

Verwendet die Tatsache, dass e^ipi = -1.

Die Formel wird 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 es!

Undichte Nonne
quelle

Poste das als separate Antwort!

Undichte Nonne

Okay, wenn du es sagst.

Dennis

1

Mathematica, 49 48 47 Bytes

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

Basierend auf der Formel aus der @ Tennis- Lösung .

Meilen
quelle

1

Axiom, 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])

mit der Formel jemand hier posten. Ergebnisse

(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
quelle

0

Oktave , 43 39 Bytes

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

Probieren Sie es online aus!

Multipliziert den Eingabevektor mit der DFT-Matrix.

Deckenkatze
quelle

Berechnen Sie die diskrete Fourier-Transformation

Regeln

Testfälle

Hilfe

Antworten:

Gelee , 16 15 Bytes

Wie es funktioniert

Python 3, 77 Bytes

J, 30 bis 20 Bytes

Verwendungszweck

MATL , 20 16 Bytes

Erläuterung

Pyth, 30

Pyth, 18 Bytes

Julia, 45 Bytes

Python 2, 78 Bytes

C (gcc) , 86 78 Bytes

Python 2, 89 Bytes

Mathematica, 49 48 47 Bytes

Axiom, 81 Bytes

Oktave , 43 39 Bytes