回答編集履歴

2

append answer

2023/03/22 08:19

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -112,3 +112,50 @@
112
112
  FFT: (4.000000 + 0.000000i) (0.000000 + 0.000000i) (0.000000 + 0.000000i) (0.000000 + 0.000000i) (4.000000 + 0.000000i) (0.000000 + 0.000000i) (0.000000 + 0.000000i) (0.000000 + 0.000000i)
113
113
  IFFT: (1.000000 + 0.000000i) (0.000000 + 0.000000i) (1.000000 + 0.000000i) (0.000000 + 0.000000i) (1.000000 + 0.000000i) (0.000000 + 0.000000i) (1.000000 + 0.000000i) (0.000000 + 0.000000i)
114
114
  ```
115
+
116
+ ```C:短く書く方
117
+ void _fft(double complex* x, int n, int inv) {
118
+
119
+ if (n == 1) {
120
+
121
+ return;
122
+ }
123
+
124
+ double complex* xe = malloc(n / 2 * sizeof(double complex));
125
+ double complex* xo = malloc(n / 2 * sizeof(double complex));
126
+
127
+ for (int i = 0; i < n / 2; i++) {
128
+
129
+ xe[i] = x[2 * i];
130
+ xo[i] = x[2 * i + 1];
131
+ }
132
+
133
+ _fft(xe, n / 2, inv);
134
+ _fft(xo, n / 2, inv);
135
+
136
+ for (int i = 0; i < n / 2; i++) {
137
+
138
+ double complex w = cexp((inv ? 1 : -1) * 2 * M_PI * I * i / n);
139
+ double complex t = w * xo[i];
140
+
141
+ x[i] = xe[i] + t;
142
+ x[i + n / 2] = xe[i] - t;
143
+ }
144
+
145
+ free(xe);
146
+ free(xo);
147
+
148
+ return;
149
+ }
150
+
151
+ void fft(double complex* x, int n) {
152
+ _fft(x, n, 0);
153
+ return ;
154
+ }
155
+
156
+ void ifft(double complex* x, int n) {
157
+ _fft(x, n, 1);
158
+ for (int i = 0; i < n; i++) x[i] /= n;
159
+ return ;
160
+ }
161
+ ```

1

fix answer

2023/03/22 08:14

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -42,8 +42,7 @@
42
42
  return;
43
43
  }
44
44
 
45
- void ifft(double complex* x, int n) {
45
+ void _ifft(double complex* x, int n) {
46
-
47
46
  if (n == 1) {
48
47
 
49
48
  return;
@@ -58,8 +57,8 @@
58
57
  xo[i] = x[2 * i + 1];
59
58
  }
60
59
 
61
- fft(xe, n / 2);
60
+ _ifft(xe, n / 2);
62
- fft(xo, n / 2);
61
+ _ifft(xo, n / 2);
63
62
 
64
63
  for (int i = 0; i < n / 2; i++) {
65
64
 
@@ -70,12 +69,16 @@
70
69
  x[i + n / 2] = xe[i] - t;
71
70
  }
72
71
 
73
- for (int i = 0; i < n; i++) x[i] /= n;
74
-
75
72
  free(xe);
76
73
  free(xo);
77
74
 
78
75
  return;
76
+ }
77
+
78
+ void ifft(double complex* x, int n) {
79
+ _ifft(x, n);
80
+ for (int i = 0; i < n; i++) x[i] /= n;
81
+ return ;
79
82
  }
80
83
 
81
84
  int main() {