Skip to content

Commit 49a4a83

Browse files
leren1leren1
authored
Refactor and add tests (fixes TheAlgorithms#2963) (TheAlgorithms#2964)
1 parent f0b5202 commit 49a4a83

File tree

3 files changed

+180
-21
lines changed

3 files changed

+180
-21
lines changed

‎src/main/java/com/thealgorithms/maths/FFT.java

Lines changed: 32 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -175,31 +175,17 @@ public Complex divide(double n) {
175175
* https://www.geeksforgeeks.org/iterative-fast-fourier-transformation-polynomial-multiplication/
176176
* https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
177177
* https://cp-algorithms.com/algebra/fft.html
178-
*
179-
* @param x The discrete signal which is then converted to the FFT or the
178+
* @param x The discrete signal which is then converted to the FFT or the
180179
* IFFT of signal x.
181180
* @param inverse True if you want to find the inverse FFT.
181+
* @return
182182
*/
183-
public static void fft(ArrayList<Complex> x, boolean inverse) {
183+
public static ArrayList<Complex> fft(ArrayList<Complex> x, boolean inverse) {
184184
/* Pad the signal with zeros if necessary */
185185
paddingPowerOfTwo(x);
186186
int N = x.size();
187-
188-
/* Find the log2(N) */
189-
int log2N = 0;
190-
while ((1 << log2N) < N) {
191-
log2N++;
192-
}
193-
194-
/* Swap the values of the signal with bit-reversal method */
195-
int reverse;
196-
for (int i = 0; i < N; i++) {
197-
reverse = reverseBits(i, log2N);
198-
if (i < reverse) {
199-
Collections.swap(x, i, reverse);
200-
}
201-
}
202-
187+
int log2N = findLog2(N);
188+
x = fftBitReversal(N,log2N,x);
203189
int direction = inverse ? -1 : 1;
204190

205191
/* Main loop of the algorithm */
@@ -217,14 +203,40 @@ public static void fft(ArrayList<Complex> x, boolean inverse) {
217203
}
218204
}
219205
}
206+
x = inverseFFT(N,inverse,x);
207+
return x;
208+
}
209+
210+
/* Find the log2(N) */
211+
public static int findLog2(int N){
212+
int log2N = 0;
213+
while ((1 << log2N) < N) {
214+
log2N++;
215+
}
216+
return log2N;
217+
}
218+
219+
/* Swap the values of the signal with bit-reversal method */
220+
public static ArrayList<Complex> fftBitReversal(int N, int log2N, ArrayList<Complex> x){
221+
int reverse;
222+
for (int i = 0; i < N; i++) {
223+
reverse = reverseBits(i, log2N);
224+
if (i < reverse) {
225+
Collections.swap(x, i, reverse);
226+
}
227+
}
228+
return x;
229+
}
220230

221-
/* Divide by N if we want the inverse FFT */
231+
/* Divide by N if we want the inverse FFT */
232+
public static ArrayList<Complex> inverseFFT(int N, boolean inverse, ArrayList<Complex> x ){
222233
if (inverse) {
223234
for (int i = 0; i < x.size(); i++) {
224235
Complex z = x.get(i);
225236
x.set(i, z.divide(N));
226237
}
227238
}
239+
return x;
228240
}
229241

230242
/**

‎src/main/java/com/thealgorithms/maths/Gaussian.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -38,7 +38,7 @@ public static double[][] gaussianElimination(int mat_size, int i, double[][] mat
3838
return mat;
3939
}
4040

41-
// calcilate the x_1, x_2,... values of the gaussian and save it in an arraylist.
41+
// calculate the x_1, x_2,... values of the gaussian and save it in an arraylist.
4242
public static ArrayList<Double> valueOfGaussian(int mat_size, double[][] x, double[][] mat) {
4343
ArrayList<Double> answerArray = new ArrayList<Double>();
4444
int i, j;

‎src/test/java/com/thealgorithms/maths/FFTTest.java

Lines changed: 147 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,147 @@
1+
package com.thealgorithms.maths;
2+
import org.junit.jupiter.api.Test;
3+
import java.util.ArrayList;
4+
import static org.junit.jupiter.api.Assertions.*;
5+
6+
class FFTTest {
7+
8+
// Testing the simple function getReal
9+
@Test
10+
void getRealtest()
11+
{
12+
FFT.Complex complex = new FFT.Complex(1.0,1.0);
13+
assertEquals(1.0,complex.getReal());
14+
}
15+
16+
// Testing the simple function getImaginary
17+
@Test
18+
void getImaginaryTest()
19+
{
20+
FFT.Complex complex = new FFT.Complex();
21+
assertEquals(0.0,complex.getImaginary());
22+
}
23+
24+
// Testing the function add, assertEqual test
25+
@Test
26+
void addTest()
27+
{
28+
FFT.Complex complex1 = new FFT.Complex(1.0,1.0);
29+
FFT.Complex complex2 = new FFT.Complex(2.0,2.0);
30+
double add = complex1.add(complex2).getReal();
31+
assertEquals(3.0,add);
32+
}
33+
34+
// Testing the function add, assertNotEqual test
35+
@Test
36+
void addFalseTest()
37+
{
38+
FFT.Complex complex1 = new FFT.Complex(1.0,1.0);
39+
FFT.Complex complex2 = new FFT.Complex(2.0,2.0);
40+
double add = complex1.add(complex2).getReal();
41+
assertNotEquals(2.0,add);
42+
}
43+
44+
// Testing the function substract, assertEqual test
45+
@Test
46+
void subtractTest()
47+
{
48+
FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
49+
FFT.Complex complex2 = new FFT.Complex(1.0,1.0);
50+
double sub = complex1.subtract(complex2).getReal();
51+
assertEquals(1.0,sub);
52+
}
53+
54+
// Testing the function multiply complex, assertEqual test
55+
@Test
56+
void multiplyWithComplexTest()
57+
{
58+
FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
59+
FFT.Complex complex2 = new FFT.Complex(1.0,1.0);
60+
double multiReal = complex1.multiply(complex2).getReal();
61+
double multiImg = complex1.multiply(complex2).getImaginary();
62+
assertEquals(0.0,multiReal);
63+
assertEquals(4.0,multiImg);
64+
}
65+
66+
// Testing the function multiply scalar, assertEqual test
67+
@Test
68+
void multiplyWithScalarTest()
69+
{
70+
FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
71+
72+
double multiReal = complex1.multiply(2).getReal();
73+
double multiImg = complex1.multiply(3).getImaginary();
74+
assertEquals(4.0,multiReal);
75+
assertEquals(6.0,multiImg);
76+
}
77+
78+
// Testing the function conjugate, assertEqual test
79+
@Test
80+
void conjugateTest()
81+
{
82+
FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
83+
double conReal = complex1.conjugate().getReal();
84+
double conImg = complex1.conjugate().getImaginary();
85+
assertEquals(2.0,conReal);
86+
assertEquals(-2.0,conImg);
87+
}
88+
89+
// Testing the function abs, assertEqual test
90+
@Test
91+
void abs()
92+
{
93+
FFT.Complex complex1 = new FFT.Complex(2.0,3.0);
94+
double abs = complex1.abs();
95+
assertEquals(Math.sqrt(13),abs);
96+
}
97+
98+
// Testing the function divide complex, assertEqual test.
99+
@Test
100+
void divideWithComplexTest()
101+
{
102+
FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
103+
FFT.Complex complex2 = new FFT.Complex(1.0,2.0);
104+
double divReal = complex1.divide(complex2).getReal();
105+
double divImg = complex1.divide(complex2).getImaginary();
106+
assertEquals(1.2,divReal);
107+
assertEquals(-0.4,divImg);
108+
}
109+
110+
// Testing the function divide scalar, assertEqual test.
111+
@Test
112+
void divideWithScalarTest()
113+
{
114+
FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
115+
double divReal = complex1.divide(2).getReal();
116+
double divImg = complex1.divide(2).getImaginary();
117+
assertEquals(1,divReal);
118+
assertEquals(1,divImg);
119+
}
120+
121+
// Testing the function fft, assertEqual test.
122+
// https://scistatcalc.blogspot.com/2013/12/fft-calculator.html used this link to
123+
// ensure the result
124+
@Test
125+
void fft()
126+
{
127+
ArrayList<FFT.Complex> arr = new ArrayList<FFT.Complex>();
128+
FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
129+
FFT.Complex complex2 = new FFT.Complex(1.0,3.0);
130+
FFT.Complex complex3 = new FFT.Complex(3.0,1.0);
131+
FFT.Complex complex4 = new FFT.Complex(2.0,2.0);
132+
133+
arr.add(complex1);
134+
arr.add(complex2);
135+
arr.add(complex3);
136+
arr.add(complex4);
137+
arr = FFT.fft(arr,false);
138+
double realV1= arr.get(0).getReal();
139+
double realV2= arr.get(2).getReal();
140+
double imgV1 = arr.get(0).getImaginary();
141+
double imgV2 = arr.get(2).getImaginary();
142+
assertEquals(8.0,realV1);
143+
assertEquals(2.0,realV2);
144+
assertEquals(8.0, imgV1);
145+
assertEquals(-2.0,imgV2);
146+
}
147+
}

0 commit comments

Comments
 (0)