commons-math-transform/src/test/java/org/apache/commons/math4/transform/FastFourierTransformerTest.java - commons-math - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
  * this work for additional information regarding copyright ownership.
  * The ASF licenses this file to You under the Apache License, Version 2.0
  * (the "License"); you may not use this file except in compliance with
  * the License.  You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 package org.apache.commons.math4.transform;

 import java.util.function.DoubleUnaryOperator;

 import org.junit.Assert;
 import org.junit.Test;

 import org.apache.commons.rng.UniformRandomProvider;
 import org.apache.commons.rng.simple.RandomSource;
 import org.apache.commons.numbers.complex.Complex;

 import org.apache.commons.math3.analysis.UnivariateFunction;
 import org.apache.commons.math3.analysis.function.Sin;
 import org.apache.commons.math3.analysis.function.Sinc;

 /**
  * Test case for {@link FastFourierTransform}.
  * <p>
  * FFT algorithm is exact, the small tolerance number is used only
  * to account for round-off errors.
  */
 public final class FastFourierTransformerTest {
     private static final Sin SIN_FUNCTION = new Sin();
     private static final DoubleUnaryOperator SIN = x -> SIN_FUNCTION.value(x);

     /** RNG. */
     private static final UniformRandomProvider RNG = RandomSource.MWC_256.create();

     // Precondition checks.

     @Test
     public void testTransformComplexSizeNotAPowerOfTwo() {
         final int n = 127;
         final Complex[] x = createComplexData(n);
         final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
         for (int i = 0; i < norm.length; i++) {
             for (boolean type : new boolean[] {true, false}) {
                 final FastFourierTransform fft = new FastFourierTransform(norm[i], type);
                 try {
                     fft.apply(x);
                     Assert.fail(norm[i] + ", " + type +
                         ": IllegalArgumentException was expected");
                 } catch (IllegalArgumentException e) {
                     // Expected behaviour
                 }
             }
         }
     }

     @Test
     public void testTransformRealSizeNotAPowerOfTwo() {
         final int n = 127;
         final double[] x = createRealData(n);
         final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
         for (int i = 0; i < norm.length; i++) {
             for (boolean type : new boolean[] {true, false}) {
                 final FastFourierTransform fft = new FastFourierTransform(norm[i], type);
                 try {
                     fft.apply(x);
                     Assert.fail(norm[i] + ", " + type +
                         ": IllegalArgumentException was expected");
                 } catch (IllegalArgumentException e) {
                     // Expected behaviour
                 }
             }
         }
     }

     @Test
     public void testTransformFunctionSizeNotAPowerOfTwo() {
         final int n = 127;
         final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
         for (int i = 0; i < norm.length; i++) {
             for (boolean type : new boolean[] {true, false}) {
                 final FastFourierTransform fft = new FastFourierTransform(norm[i], type);
                 try {
                     fft.apply(SIN, 0.0, Math.PI, n);
                     Assert.fail(norm[i] + ", " + type +
                         ": IllegalArgumentException was expected");
                 } catch (IllegalArgumentException e) {
                     // Expected behaviour
                 }
             }
         }
     }

     @Test
     public void testTransformFunctionNotStrictlyPositiveNumberOfSamples() {
         final int n = -128;
         final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
         for (int i = 0; i < norm.length; i++) {
             for (boolean type : new boolean[] {true, false}) {
                 final FastFourierTransform fft = new FastFourierTransform(norm[i], type);
                 try {
                     fft.apply(SIN, 0.0, Math.PI, n);
                     fft.apply(SIN, 0.0, Math.PI, n);
                     Assert.fail(norm[i] + ", " + type +
                         ": IllegalArgumentException was expected");
                 } catch (IllegalArgumentException e) {
                     // Expected behaviour
                 }
             }
         }
     }

     @Test
     public void testTransformFunctionInvalidBounds() {
         final int n = 128;
         final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
         for (int i = 0; i < norm.length; i++) {
             for (boolean type : new boolean[] {true, false}) {
                 final FastFourierTransform fft = new FastFourierTransform(norm[i], type);
                 try {
                     fft.apply(SIN, Math.PI, 0.0, n);
                     Assert.fail(norm[i] + ", " + type +
                         ": IllegalArgumentException was expected");
                 } catch (IllegalArgumentException e) {
                     // Expected behaviour
                 }
             }
         }
     }

     // Utility methods for checking (successful) transforms.

     private static Complex[] createComplexData(final int n) {
         final Complex[] data = new Complex[n];
         for (int i = 0; i < n; i++) {
             final double re = 2 * RNG.nextDouble() - 1;
             final double im = 2 * RNG.nextDouble() - 1;
             data[i] = Complex.ofCartesian(re, im);
         }
         return data;
     }

     private static double[] createRealData(final int n) {
         final double[] data = new double[n];
         for (int i = 0; i < n; i++) {
             data[i] = 2 * RNG.nextDouble() - 1;
         }
         return data;
     }

     /** Naive implementation of DFT, for reference. */
     private static Complex[] dft(final Complex[] x, final int sgn) {
         final int n = x.length;
         final double[] cos = new double[n];
         final double[] sin = new double[n];
         final Complex[] y = new Complex[n];
         for (int i = 0; i < n; i++) {
             final double arg = 2.0 * Math.PI * i / n;
             cos[i] = Math.cos(arg);
             sin[i] = Math.sin(arg);
         }
         for (int i = 0; i < n; i++) {
             double yr = 0.0;
             double yi = 0.0;
             for (int j = 0; j < n; j++) {
                 final int index = (i * j) % n;
                 final double c = cos[index];
                 final double s = sin[index];
                 final double xr = x[j].getReal();
                 final double xi = x[j].getImaginary();
                 yr += c * xr - sgn * s * xi;
                 yi += sgn * s * xr + c * xi;
             }
             y[i] = Complex.ofCartesian(yr, yi);
         }
         return y;
     }

     private static void doTestTransformComplex(final int n,
                                                final double tol,
                                                final FastFourierTransform.Norm normalization,
                                                boolean inverse) {
         final FastFourierTransform fft = new FastFourierTransform(normalization, inverse);
         final Complex[] x = createComplexData(n);
         final Complex[] expected;
         final double s;
         if (!inverse) {
             expected = dft(x, -1);
             if (normalization == FastFourierTransform.Norm.STD) {
                 s = 1.0;
             } else {
                 s = 1.0 / Math.sqrt(n);
             }
         } else {
             expected = dft(x, 1);
             if (normalization == FastFourierTransform.Norm.STD) {
                 s = 1.0 / n;
             } else {
                 s = 1.0 / Math.sqrt(n);
             }
         }
         final Complex[] actual = fft.apply(x);
         for (int i = 0; i < n; i++) {
             final String msg;
             msg = String.format("%s, %s, %d, %d", normalization, inverse, n, i);
             final double re = s * expected[i].getReal();
             Assert.assertEquals(msg, re, actual[i].getReal(),
                                 tol * Math.abs(re));
             final double im = s * expected[i].getImaginary();
             Assert.assertEquals(msg, im, actual[i].getImaginary(),
                                 tol * Math.abs(re));
         }
     }

     private static void doTestTransformReal(final int n,
                                             final double tol,
                                             final FastFourierTransform.Norm normalization,
                                             final boolean inverse) {
         final FastFourierTransform fft = new FastFourierTransform(normalization, inverse);
         final double[] x = createRealData(n);
         final Complex[] xc = new Complex[n];
         for (int i = 0; i < n; i++) {
             xc[i] = Complex.ofCartesian(x[i], 0.0);
         }
         final Complex[] expected;
         final double s;
         if (!inverse) {
             expected = dft(xc, -1);
             if (normalization == FastFourierTransform.Norm.STD) {
                 s = 1.0;
             } else {
                 s = 1.0 / Math.sqrt(n);
             }
         } else {
             expected = dft(xc, 1);
             if (normalization == FastFourierTransform.Norm.STD) {
                 s = 1.0 / n;
             } else {
                 s = 1.0 / Math.sqrt(n);
             }
         }
         final Complex[] actual = fft.apply(x);
         for (int i = 0; i < n; i++) {
             final String msg;
             msg = String.format("%s, %s, %d, %d", normalization, inverse, n, i);
             final double re = s * expected[i].getReal();
             Assert.assertEquals(msg, re, actual[i].getReal(),
                                 tol * Math.abs(re));
             final double im = s * expected[i].getImaginary();
             Assert.assertEquals(msg, im, actual[i].getImaginary(),
                                 tol * Math.abs(re));
         }
     }

     private static void doTestTransformFunction(final DoubleUnaryOperator f,
                                                 final double min,
                                                 final double max,
                                                 int n,
                                                 final double tol,
                                                 final FastFourierTransform.Norm normalization,
                                                 final boolean inverse) {
         final FastFourierTransform fft = new FastFourierTransform(normalization, inverse);
         final Complex[] x = new Complex[n];
         for (int i = 0; i < n; i++) {
             final double t = min + i * (max - min) / n;
             x[i] = Complex.ofCartesian(f.applyAsDouble(t), 0);
         }
         final Complex[] expected;
         final double s;
         if (!inverse) {
             expected = dft(x, -1);
             if (normalization == FastFourierTransform.Norm.STD) {
                 s = 1.0;
             } else {
                 s = 1.0 / Math.sqrt(n);
             }
         } else {
             expected = dft(x, 1);
             if (normalization == FastFourierTransform.Norm.STD) {
                 s = 1.0 / n;
             } else {
                 s = 1.0 / Math.sqrt(n);
             }
         }
         final Complex[] actual = fft.apply(f, min, max, n);
         for (int i = 0; i < n; i++) {
             final String msg = String.format("%d, %d", n, i);
             final double re = s * expected[i].getReal();
             Assert.assertEquals(msg, re, actual[i].getReal(),
                                 tol * Math.abs(re));
             final double im = s * expected[i].getImaginary();
             Assert.assertEquals(msg, im, actual[i].getImaginary(),
                                 tol * Math.abs(re));
         }
     }

     // Tests of standard transform (when data is valid).

     @Test
     public void testTransformComplex() {
         final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
         for (int i = 0; i < norm.length; i++) {
             for (boolean type : new boolean[] {true, false}) {
                 doTestTransformComplex(2, 1e-15, norm[i], type);
                 doTestTransformComplex(4, 1e-14, norm[i], type);
                 doTestTransformComplex(8, 1e-13, norm[i], type);
                 doTestTransformComplex(16, 1e-13, norm[i], type);
                 doTestTransformComplex(32, 1e-12, norm[i], type);
                 doTestTransformComplex(64, 1e-11, norm[i], type);
                 doTestTransformComplex(128, 1e-11, norm[i], type);
             }
         }
     }

     @Test
     public void testStandardTransformReal() {
         final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
         for (int i = 0; i < norm.length; i++) {
             for (boolean type : new boolean[] {true, false}) {
                 doTestTransformReal(2, 1e-15, norm[i], type);
                 doTestTransformReal(4, 1e-14, norm[i], type);
                 doTestTransformReal(8, 1e-13, norm[i], type);
                 doTestTransformReal(16, 1e-13, norm[i], type);
                 doTestTransformReal(32, 1e-12, norm[i], type);
                 doTestTransformReal(64, 1e-12, norm[i], type);
                 doTestTransformReal(128, 1e-11, norm[i], type);
             }
         }
     }

     @Test
     public void testStandardTransformFunction() {
         final UnivariateFunction sinc = new Sinc();
         final DoubleUnaryOperator f = x -> sinc.value(x);

         final double min = -Math.PI;
         final double max = Math.PI;
         final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();

         for (int i = 0; i < norm.length; i++) {
             for (boolean type : new boolean[] {true, false}) {
                 doTestTransformFunction(f, min, max, 2, 1e-15, norm[i], type);
                 doTestTransformFunction(f, min, max, 4, 1e-14, norm[i], type);
                 doTestTransformFunction(f, min, max, 8, 1e-14, norm[i], type);
                 doTestTransformFunction(f, min, max, 16, 1e-13, norm[i], type);
                 doTestTransformFunction(f, min, max, 32, 1e-13, norm[i], type);
                 doTestTransformFunction(f, min, max, 64, 1e-12, norm[i], type);
                 doTestTransformFunction(f, min, max, 128, 1e-11, norm[i], type);
             }
         }
     }

     // Additional tests for 1D data.

     /**
      * Test of transformer for the ad hoc data taken from Mathematica.
      */
     @Test
     public void testAdHocData() {
         FastFourierTransform transformer;
         Complex[] result;
         double tolerance = 1e-12;

         final double[] x = {1.3, 2.4, 1.7, 4.1, 2.9, 1.7, 5.1, 2.7};
         final Complex[] y = {
             Complex.ofCartesian(21.9, 0.0),
             Complex.ofCartesian(-2.09497474683058, 1.91507575950825),
             Complex.ofCartesian(-2.6, 2.7),
             Complex.ofCartesian(-1.10502525316942, -4.88492424049175),
             Complex.ofCartesian(0.1, 0.0),
             Complex.ofCartesian(-1.10502525316942, 4.88492424049175),
             Complex.ofCartesian(-2.6, -2.7),
             Complex.ofCartesian(-2.09497474683058, -1.91507575950825)};

         transformer = new FastFourierTransform(FastFourierTransform.Norm.STD);
         result = transformer.apply(x);
         for (int i = 0; i < result.length; i++) {
             Assert.assertEquals(y[i].getReal(), result[i].getReal(), tolerance);
             Assert.assertEquals(y[i].getImaginary(), result[i].getImaginary(), tolerance);
         }

         transformer = new FastFourierTransform(FastFourierTransform.Norm.STD, true);
         result = transformer.apply(y);
         for (int i = 0; i < result.length; i++) {
             Assert.assertEquals(x[i], result[i].getReal(), tolerance);
             Assert.assertEquals(0.0, result[i].getImaginary(), tolerance);
         }

         double[] x2 = {10.4, 21.6, 40.8, 13.6, 23.2, 32.8, 13.6, 19.2};
         TransformUtils.scaleInPlace(x2, 1.0 / Math.sqrt(x2.length));
         Complex[] y2 = y;

         transformer = new FastFourierTransform(FastFourierTransform.Norm.UNIT);
         result = transformer.apply(y2);
         for (int i = 0; i < result.length; i++) {
             Assert.assertEquals(x2[i], result[i].getReal(), tolerance);
             Assert.assertEquals(0.0, result[i].getImaginary(), tolerance);
         }

         transformer = new FastFourierTransform(FastFourierTransform.Norm.UNIT, true);
         result = transformer.apply(x2);
         for (int i = 0; i < result.length; i++) {
             Assert.assertEquals(y2[i].getReal(), result[i].getReal(), tolerance);
             Assert.assertEquals(y2[i].getImaginary(), result[i].getImaginary(), tolerance);
         }
     }

     /**
      * Test of transformer for the sine function.
      */
     @Test
     public void testSinFunction() {
         FastFourierTransform transformer;
         Complex[] result;
         int size = 1 << 8;
         double tolerance = 1e-12;

         double min = 0.0;
         double max = 2 * Math.PI;
         transformer = new FastFourierTransform(FastFourierTransform.Norm.STD);
         result = transformer.apply(SIN, min, max, size);
         Assert.assertEquals(0.0, result[1].getReal(), tolerance);
         Assert.assertEquals(-(size >> 1), result[1].getImaginary(), tolerance);
         Assert.assertEquals(0.0, result[size - 1].getReal(), tolerance);
         Assert.assertEquals(size >> 1, result[size - 1].getImaginary(), tolerance);
         for (int i = 0; i < size - 1; i += i == 0 ? 2 : 1) {
             Assert.assertEquals(0.0, result[i].getReal(), tolerance);
             Assert.assertEquals(0.0, result[i].getImaginary(), tolerance);
         }

         min = -Math.PI;
         max = Math.PI;
         transformer = new FastFourierTransform(FastFourierTransform.Norm.STD, true);
         result = transformer.apply(SIN, min, max, size);
         Assert.assertEquals(0.0, result[1].getReal(), tolerance);
         Assert.assertEquals(-0.5, result[1].getImaginary(), tolerance);
         Assert.assertEquals(0.0, result[size - 1].getReal(), tolerance);
         Assert.assertEquals(0.5, result[size - 1].getImaginary(), tolerance);
         for (int i = 0; i < size - 1; i += i == 0 ? 2 : 1) {
             Assert.assertEquals(0.0, result[i].getReal(), tolerance);
             Assert.assertEquals(0.0, result[i].getImaginary(), tolerance);
         }
     }
 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one or more
	* contributor license agreements. See the NOTICE file distributed with
	* this work for additional information regarding copyright ownership.
	* The ASF licenses this file to You under the Apache License, Version 2.0
	* (the "License"); you may not use this file except in compliance with
	* the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	package org.apache.commons.math4.transform;

	import java.util.function.DoubleUnaryOperator;

	import org.junit.Assert;
	import org.junit.Test;

	import org.apache.commons.rng.UniformRandomProvider;
	import org.apache.commons.rng.simple.RandomSource;
	import org.apache.commons.numbers.complex.Complex;

	import org.apache.commons.math3.analysis.UnivariateFunction;
	import org.apache.commons.math3.analysis.function.Sin;
	import org.apache.commons.math3.analysis.function.Sinc;

	/**
	* Test case for {@link FastFourierTransform}.
	* <p>
	* FFT algorithm is exact, the small tolerance number is used only
	* to account for round-off errors.
	*/
	public final class FastFourierTransformerTest {
	private static final Sin SIN_FUNCTION = new Sin();
	private static final DoubleUnaryOperator SIN = x -> SIN_FUNCTION.value(x);

	/** RNG. */
	private static final UniformRandomProvider RNG = RandomSource.MWC_256.create();

	// Precondition checks.

	@Test
	public void testTransformComplexSizeNotAPowerOfTwo() {
	final int n = 127;
	final Complex[] x = createComplexData(n);
	final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
	for (int i = 0; i < norm.length; i++) {
	for (boolean type : new boolean[] {true, false}) {
	final FastFourierTransform fft = new FastFourierTransform(norm[i], type);
	try {
	fft.apply(x);
	Assert.fail(norm[i] + ", " + type +
	": IllegalArgumentException was expected");
	} catch (IllegalArgumentException e) {
	// Expected behaviour
	}
	}
	}
	}

	@Test
	public void testTransformRealSizeNotAPowerOfTwo() {
	final int n = 127;
	final double[] x = createRealData(n);
	final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
	for (int i = 0; i < norm.length; i++) {
	for (boolean type : new boolean[] {true, false}) {
	final FastFourierTransform fft = new FastFourierTransform(norm[i], type);
	try {
	fft.apply(x);
	Assert.fail(norm[i] + ", " + type +
	": IllegalArgumentException was expected");
	} catch (IllegalArgumentException e) {
	// Expected behaviour
	}
	}
	}
	}

	@Test
	public void testTransformFunctionSizeNotAPowerOfTwo() {
	final int n = 127;
	final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
	for (int i = 0; i < norm.length; i++) {
	for (boolean type : new boolean[] {true, false}) {
	final FastFourierTransform fft = new FastFourierTransform(norm[i], type);
	try {
	fft.apply(SIN, 0.0, Math.PI, n);
	Assert.fail(norm[i] + ", " + type +
	": IllegalArgumentException was expected");
	} catch (IllegalArgumentException e) {
	// Expected behaviour
	}
	}
	}
	}

	@Test
	public void testTransformFunctionNotStrictlyPositiveNumberOfSamples() {
	final int n = -128;
	final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
	for (int i = 0; i < norm.length; i++) {
	for (boolean type : new boolean[] {true, false}) {
	final FastFourierTransform fft = new FastFourierTransform(norm[i], type);
	try {
	fft.apply(SIN, 0.0, Math.PI, n);
	fft.apply(SIN, 0.0, Math.PI, n);
	Assert.fail(norm[i] + ", " + type +
	": IllegalArgumentException was expected");
	} catch (IllegalArgumentException e) {
	// Expected behaviour
	}
	}
	}
	}

	@Test
	public void testTransformFunctionInvalidBounds() {
	final int n = 128;
	final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
	for (int i = 0; i < norm.length; i++) {
	for (boolean type : new boolean[] {true, false}) {
	final FastFourierTransform fft = new FastFourierTransform(norm[i], type);
	try {
	fft.apply(SIN, Math.PI, 0.0, n);
	Assert.fail(norm[i] + ", " + type +
	": IllegalArgumentException was expected");
	} catch (IllegalArgumentException e) {
	// Expected behaviour
	}
	}
	}
	}

	// Utility methods for checking (successful) transforms.

	private static Complex[] createComplexData(final int n) {
	final Complex[] data = new Complex[n];
	for (int i = 0; i < n; i++) {
	final double re = 2 * RNG.nextDouble() - 1;
	final double im = 2 * RNG.nextDouble() - 1;
	data[i] = Complex.ofCartesian(re, im);
	}
	return data;
	}

	private static double[] createRealData(final int n) {
	final double[] data = new double[n];
	for (int i = 0; i < n; i++) {
	data[i] = 2 * RNG.nextDouble() - 1;
	}
	return data;
	}

	/** Naive implementation of DFT, for reference. */
	private static Complex[] dft(final Complex[] x, final int sgn) {
	final int n = x.length;
	final double[] cos = new double[n];
	final double[] sin = new double[n];
	final Complex[] y = new Complex[n];
	for (int i = 0; i < n; i++) {
	final double arg = 2.0 * Math.PI * i / n;
	cos[i] = Math.cos(arg);
	sin[i] = Math.sin(arg);
	}
	for (int i = 0; i < n; i++) {
	double yr = 0.0;
	double yi = 0.0;
	for (int j = 0; j < n; j++) {
	final int index = (i * j) % n;
	final double c = cos[index];
	final double s = sin[index];
	final double xr = x[j].getReal();
	final double xi = x[j].getImaginary();
	yr += c * xr - sgn * s * xi;
	yi += sgn * s * xr + c * xi;
	}
	y[i] = Complex.ofCartesian(yr, yi);
	}
	return y;
	}

	private static void doTestTransformComplex(final int n,
	final double tol,
	final FastFourierTransform.Norm normalization,
	boolean inverse) {
	final FastFourierTransform fft = new FastFourierTransform(normalization, inverse);
	final Complex[] x = createComplexData(n);
	final Complex[] expected;
	final double s;
	if (!inverse) {
	expected = dft(x, -1);
	if (normalization == FastFourierTransform.Norm.STD) {
	s = 1.0;
	} else {
	s = 1.0 / Math.sqrt(n);
	}
	} else {
	expected = dft(x, 1);
	if (normalization == FastFourierTransform.Norm.STD) {
	s = 1.0 / n;
	} else {
	s = 1.0 / Math.sqrt(n);
	}
	}
	final Complex[] actual = fft.apply(x);
	for (int i = 0; i < n; i++) {
	final String msg;
	msg = String.format("%s, %s, %d, %d", normalization, inverse, n, i);
	final double re = s * expected[i].getReal();
	Assert.assertEquals(msg, re, actual[i].getReal(),
	tol * Math.abs(re));
	final double im = s * expected[i].getImaginary();
	Assert.assertEquals(msg, im, actual[i].getImaginary(),
	tol * Math.abs(re));
	}
	}

	private static void doTestTransformReal(final int n,
	final double tol,
	final FastFourierTransform.Norm normalization,
	final boolean inverse) {
	final FastFourierTransform fft = new FastFourierTransform(normalization, inverse);
	final double[] x = createRealData(n);
	final Complex[] xc = new Complex[n];
	for (int i = 0; i < n; i++) {
	xc[i] = Complex.ofCartesian(x[i], 0.0);
	}
	final Complex[] expected;
	final double s;
	if (!inverse) {
	expected = dft(xc, -1);
	if (normalization == FastFourierTransform.Norm.STD) {
	s = 1.0;
	} else {
	s = 1.0 / Math.sqrt(n);
	}
	} else {
	expected = dft(xc, 1);
	if (normalization == FastFourierTransform.Norm.STD) {
	s = 1.0 / n;
	} else {
	s = 1.0 / Math.sqrt(n);
	}
	}
	final Complex[] actual = fft.apply(x);
	for (int i = 0; i < n; i++) {
	final String msg;
	msg = String.format("%s, %s, %d, %d", normalization, inverse, n, i);
	final double re = s * expected[i].getReal();
	Assert.assertEquals(msg, re, actual[i].getReal(),
	tol * Math.abs(re));
	final double im = s * expected[i].getImaginary();
	Assert.assertEquals(msg, im, actual[i].getImaginary(),
	tol * Math.abs(re));
	}
	}

	private static void doTestTransformFunction(final DoubleUnaryOperator f,
	final double min,
	final double max,
	int n,
	final double tol,
	final FastFourierTransform.Norm normalization,
	final boolean inverse) {
	final FastFourierTransform fft = new FastFourierTransform(normalization, inverse);
	final Complex[] x = new Complex[n];
	for (int i = 0; i < n; i++) {
	final double t = min + i * (max - min) / n;
	x[i] = Complex.ofCartesian(f.applyAsDouble(t), 0);
	}
	final Complex[] expected;
	final double s;
	if (!inverse) {
	expected = dft(x, -1);
	if (normalization == FastFourierTransform.Norm.STD) {
	s = 1.0;
	} else {
	s = 1.0 / Math.sqrt(n);
	}
	} else {
	expected = dft(x, 1);
	if (normalization == FastFourierTransform.Norm.STD) {
	s = 1.0 / n;
	} else {
	s = 1.0 / Math.sqrt(n);
	}
	}
	final Complex[] actual = fft.apply(f, min, max, n);
	for (int i = 0; i < n; i++) {
	final String msg = String.format("%d, %d", n, i);
	final double re = s * expected[i].getReal();
	Assert.assertEquals(msg, re, actual[i].getReal(),
	tol * Math.abs(re));
	final double im = s * expected[i].getImaginary();
	Assert.assertEquals(msg, im, actual[i].getImaginary(),
	tol * Math.abs(re));
	}
	}

	// Tests of standard transform (when data is valid).

	@Test
	public void testTransformComplex() {
	final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
	for (int i = 0; i < norm.length; i++) {
	for (boolean type : new boolean[] {true, false}) {
	doTestTransformComplex(2, 1e-15, norm[i], type);
	doTestTransformComplex(4, 1e-14, norm[i], type);
	doTestTransformComplex(8, 1e-13, norm[i], type);
	doTestTransformComplex(16, 1e-13, norm[i], type);
	doTestTransformComplex(32, 1e-12, norm[i], type);
	doTestTransformComplex(64, 1e-11, norm[i], type);
	doTestTransformComplex(128, 1e-11, norm[i], type);
	}
	}
	}

	@Test
	public void testStandardTransformReal() {
	final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();
	for (int i = 0; i < norm.length; i++) {
	for (boolean type : new boolean[] {true, false}) {
	doTestTransformReal(2, 1e-15, norm[i], type);
	doTestTransformReal(4, 1e-14, norm[i], type);
	doTestTransformReal(8, 1e-13, norm[i], type);
	doTestTransformReal(16, 1e-13, norm[i], type);
	doTestTransformReal(32, 1e-12, norm[i], type);
	doTestTransformReal(64, 1e-12, norm[i], type);
	doTestTransformReal(128, 1e-11, norm[i], type);
	}
	}
	}

	@Test
	public void testStandardTransformFunction() {
	final UnivariateFunction sinc = new Sinc();
	final DoubleUnaryOperator f = x -> sinc.value(x);

	final double min = -Math.PI;
	final double max = Math.PI;
	final FastFourierTransform.Norm[] norm = FastFourierTransform.Norm.values();

	for (int i = 0; i < norm.length; i++) {
	for (boolean type : new boolean[] {true, false}) {
	doTestTransformFunction(f, min, max, 2, 1e-15, norm[i], type);
	doTestTransformFunction(f, min, max, 4, 1e-14, norm[i], type);
	doTestTransformFunction(f, min, max, 8, 1e-14, norm[i], type);
	doTestTransformFunction(f, min, max, 16, 1e-13, norm[i], type);
	doTestTransformFunction(f, min, max, 32, 1e-13, norm[i], type);
	doTestTransformFunction(f, min, max, 64, 1e-12, norm[i], type);
	doTestTransformFunction(f, min, max, 128, 1e-11, norm[i], type);
	}
	}
	}

	// Additional tests for 1D data.

	/**
	* Test of transformer for the ad hoc data taken from Mathematica.
	*/
	@Test
	public void testAdHocData() {
	FastFourierTransform transformer;
	Complex[] result;
	double tolerance = 1e-12;

	final double[] x = {1.3, 2.4, 1.7, 4.1, 2.9, 1.7, 5.1, 2.7};
	final Complex[] y = {
	Complex.ofCartesian(21.9, 0.0),
	Complex.ofCartesian(-2.09497474683058, 1.91507575950825),
	Complex.ofCartesian(-2.6, 2.7),
	Complex.ofCartesian(-1.10502525316942, -4.88492424049175),
	Complex.ofCartesian(0.1, 0.0),
	Complex.ofCartesian(-1.10502525316942, 4.88492424049175),
	Complex.ofCartesian(-2.6, -2.7),
	Complex.ofCartesian(-2.09497474683058, -1.91507575950825)};

	transformer = new FastFourierTransform(FastFourierTransform.Norm.STD);
	result = transformer.apply(x);
	for (int i = 0; i < result.length; i++) {
	Assert.assertEquals(y[i].getReal(), result[i].getReal(), tolerance);
	Assert.assertEquals(y[i].getImaginary(), result[i].getImaginary(), tolerance);
	}

	transformer = new FastFourierTransform(FastFourierTransform.Norm.STD, true);
	result = transformer.apply(y);
	for (int i = 0; i < result.length; i++) {
	Assert.assertEquals(x[i], result[i].getReal(), tolerance);
	Assert.assertEquals(0.0, result[i].getImaginary(), tolerance);
	}

	double[] x2 = {10.4, 21.6, 40.8, 13.6, 23.2, 32.8, 13.6, 19.2};
	TransformUtils.scaleInPlace(x2, 1.0 / Math.sqrt(x2.length));
	Complex[] y2 = y;

	transformer = new FastFourierTransform(FastFourierTransform.Norm.UNIT);
	result = transformer.apply(y2);
	for (int i = 0; i < result.length; i++) {
	Assert.assertEquals(x2[i], result[i].getReal(), tolerance);
	Assert.assertEquals(0.0, result[i].getImaginary(), tolerance);
	}

	transformer = new FastFourierTransform(FastFourierTransform.Norm.UNIT, true);
	result = transformer.apply(x2);
	for (int i = 0; i < result.length; i++) {
	Assert.assertEquals(y2[i].getReal(), result[i].getReal(), tolerance);
	Assert.assertEquals(y2[i].getImaginary(), result[i].getImaginary(), tolerance);
	}
	}

	/**
	* Test of transformer for the sine function.
	*/
	@Test
	public void testSinFunction() {
	FastFourierTransform transformer;
	Complex[] result;
	int size = 1 << 8;
	double tolerance = 1e-12;

	double min = 0.0;
	double max = 2 * Math.PI;
	transformer = new FastFourierTransform(FastFourierTransform.Norm.STD);
	result = transformer.apply(SIN, min, max, size);
	Assert.assertEquals(0.0, result[1].getReal(), tolerance);
	Assert.assertEquals(-(size >> 1), result[1].getImaginary(), tolerance);
	Assert.assertEquals(0.0, result[size - 1].getReal(), tolerance);
	Assert.assertEquals(size >> 1, result[size - 1].getImaginary(), tolerance);
	for (int i = 0; i < size - 1; i += i == 0 ? 2 : 1) {
	Assert.assertEquals(0.0, result[i].getReal(), tolerance);
	Assert.assertEquals(0.0, result[i].getImaginary(), tolerance);
	}

	min = -Math.PI;
	max = Math.PI;
	transformer = new FastFourierTransform(FastFourierTransform.Norm.STD, true);
	result = transformer.apply(SIN, min, max, size);
	Assert.assertEquals(0.0, result[1].getReal(), tolerance);
	Assert.assertEquals(-0.5, result[1].getImaginary(), tolerance);
	Assert.assertEquals(0.0, result[size - 1].getReal(), tolerance);
	Assert.assertEquals(0.5, result[size - 1].getImaginary(), tolerance);
	for (int i = 0; i < size - 1; i += i == 0 ? 2 : 1) {
	Assert.assertEquals(0.0, result[i].getReal(), tolerance);
	Assert.assertEquals(0.0, result[i].getImaginary(), tolerance);
	}
	}
	}