Fast Fourier Transform (fft)
============================

.. currentmodule:: numpycore.fft

The ``fft`` module provides functions for computing discrete Fourier transforms.

Example
-------

.. code-block:: python

   import numpycore as np

   # Create a signal
   t = np.linspace(0, 1, 1000)
   signal = np.sin(2 * np.pi * 50 * t) + 0.5 * np.sin(2 * np.pi * 120 * t)

   # Compute FFT
   spectrum = np.fft.fft(signal)

   # Compute inverse FFT
   reconstructed = np.fft.ifft(spectrum)

   # Frequency bins
   freqs = np.fft.fftfreq(len(signal), d=t[1] - t[0])

Standard FFTs
-------------

.. list-table::
   :widths: 25 60 15
   :header-rows: 1

   * - Function
     - Description
     - Example
   * - fft(a)
     - 1-D discrete Fourier Transform
     - 
   * - ifft(a)
     - 1-D inverse discrete Fourier Transform
     - 
   * - fft2(a)
     - 2-D discrete Fourier Transform
     - 
   * - ifft2(a)
     - 2-D inverse discrete Fourier Transform
     - 
   * - fftn(a)
     - N-D discrete Fourier Transform
     - 
   * - ifftn(a)
     - N-D inverse discrete Fourier Transform
     - 

Real FFTs
---------

.. list-table::
   :widths: 25 60 15
   :header-rows: 1

   * - Function
     - Description
     - Example
   * - rfft(a)
     - 1-D FFT of real input
     - 
   * - irfft(a)
     - Inverse of rfft
     - 
   * - rfft2(a)
     - 2-D FFT of real input
     - :ref:`View <example-fft-real-rfft2-0>`
   * - irfft2(a)
     - Inverse of rfft2
     - :ref:`View <example-fft-real-irfft2-1>`
   * - rfftn(a)
     - N-D FFT of real input
     - :ref:`View <example-fft-real-rfftn-2>`
   * - irfftn(a)
     - Inverse of rfftn
     - :ref:`View <example-fft-real-irfftn-3>`

Hermitian FFTs
--------------

.. list-table::
   :widths: 25 60 15
   :header-rows: 1

   * - Function
     - Description
     - Example
   * - hfft(a)
     - FFT of Hermitian-symmetric input
     - :ref:`View <example-fft-hermitian-hfft-4>`
   * - ihfft(a)
     - Inverse of hfft
     - :ref:`View <example-fft-hermitian-ihfft-5>`

Helper Functions
----------------

.. list-table::
   :widths: 25 60 15
   :header-rows: 1

   * - Function
     - Description
     - Example
   * - fftfreq(n, d=1.0)
     - Discrete Fourier Transform sample frequencies
     - 
   * - rfftfreq(n, d=1.0)
     - DFT sample frequencies for rfft
     - 
   * - fftshift(x)
     - Shift zero-frequency to center
     - :ref:`View <example-fft-helper-fftshift-6>`
   * - ifftshift(x)
     - Inverse of fftshift
     - :ref:`View <example-fft-helper-ifftshift-7>`

Code Examples
-------------

The following examples are extracted from the test suite.

.. _example-fft-real-rfft2-0:

.. dropdown:: rfft2 (test_phase4_fft.py:23)
   :class-title: example-dropdown

   .. code-block:: python
      :linenos:
      :lineno-start: 13
      :emphasize-lines: 11

              print(f"  NumpyCore result: {nc_result}")
              sys.exit(1)
          print(f"[OK] {test_name}: PASSED")
      
      def test_rfft2():
          """Test 2D real FFT"""
          data_np = test_bind.np.random.randn(8, 8)
          data_nc = test_bind.numpycore.array(data_np.tolist())
      
          result_np = test_bind.np.fft.rfft2(data_np)
          result_nc = test_bind.numpycore.fft.rfft2(data_nc)
      
          assert_arrays_equal(result_np, result_nc, "rfft2")
      
      def test_irfft2():
          """Test inverse 2D real FFT"""
          data_np = test_bind.np.random.randn(8, 8)
          data_nc = test_bind.numpycore.array(data_np.tolist())
      
          fft_np = test_bind.np.fft.rfft2(data_np)
          fft_nc = test_bind.numpycore.fft.rfft2(data_nc)

.. _example-fft-real-irfft2-1:

.. dropdown:: irfft2 (test_phase4_fft.py:36)
   :class-title: example-dropdown

   .. code-block:: python
      :linenos:
      :lineno-start: 26
      :emphasize-lines: 11

      
      def test_irfft2():
          """Test inverse 2D real FFT"""
          data_np = test_bind.np.random.randn(8, 8)
          data_nc = test_bind.numpycore.array(data_np.tolist())
      
          fft_np = test_bind.np.fft.rfft2(data_np)
          fft_nc = test_bind.numpycore.fft.rfft2(data_nc)
      
          result_np = test_bind.np.fft.irfft2(fft_np)
          result_nc = test_bind.numpycore.fft.irfft2(fft_nc)
      
          assert_arrays_equal(result_np, result_nc, "irfft2")
      
      def test_rfftn():
          """Test N-D real FFT"""
          data_np = test_bind.np.random.randn(4, 4, 4)
          data_nc = test_bind.numpycore.array(data_np.tolist())
      
          result_np = test_bind.np.fft.rfftn(data_np)
          result_nc = test_bind.numpycore.fft.rfftn(data_nc)

.. _example-fft-real-rfftn-2:

.. dropdown:: rfftn (test_phase4_fft.py:46)
   :class-title: example-dropdown

   .. code-block:: python
      :linenos:
      :lineno-start: 36
      :emphasize-lines: 11

          result_nc = test_bind.numpycore.fft.irfft2(fft_nc)
      
          assert_arrays_equal(result_np, result_nc, "irfft2")
      
      def test_rfftn():
          """Test N-D real FFT"""
          data_np = test_bind.np.random.randn(4, 4, 4)
          data_nc = test_bind.numpycore.array(data_np.tolist())
      
          result_np = test_bind.np.fft.rfftn(data_np)
          result_nc = test_bind.numpycore.fft.rfftn(data_nc)
      
          assert_arrays_equal(result_np, result_nc, "rfftn")
      
      def test_irfftn():
          """Test inverse N-D real FFT"""
          data_np = test_bind.np.random.randn(4, 4, 4)
          data_nc = test_bind.numpycore.array(data_np.tolist())
      
          fft_np = test_bind.np.fft.rfftn(data_np)
          fft_nc = test_bind.numpycore.fft.rfftn(data_nc)

.. _example-fft-real-irfftn-3:

.. dropdown:: irfftn (test_phase4_fft.py:59)
   :class-title: example-dropdown

   .. code-block:: python
      :linenos:
      :lineno-start: 49
      :emphasize-lines: 11

      
      def test_irfftn():
          """Test inverse N-D real FFT"""
          data_np = test_bind.np.random.randn(4, 4, 4)
          data_nc = test_bind.numpycore.array(data_np.tolist())
      
          fft_np = test_bind.np.fft.rfftn(data_np)
          fft_nc = test_bind.numpycore.fft.rfftn(data_nc)
      
          result_np = test_bind.np.fft.irfftn(fft_np)
          result_nc = test_bind.numpycore.fft.irfftn(fft_nc)
      
          assert_arrays_equal(result_np, result_nc, "irfftn")
      
      def test_hfft():
          """Test Hermitian FFT"""
          # Create a Hermitian symmetric array
          # For a real signal, rfft produces Hermitian symmetric output
          signal_np = test_bind.np.random.randn(16)
          hermitian_np = test_bind.np.fft.rfft(signal_np)
          hermitian_nc = test_bind.numpycore.array(hermitian_np.tolist())

.. _example-fft-hermitian-hfft-4:

.. dropdown:: hfft (test_phase4_fft.py:72)
   :class-title: example-dropdown

   .. code-block:: python
      :linenos:
      :lineno-start: 62
      :emphasize-lines: 11

      
      def test_hfft():
          """Test Hermitian FFT"""
          # Create a Hermitian symmetric array
          # For a real signal, rfft produces Hermitian symmetric output
          signal_np = test_bind.np.random.randn(16)
          hermitian_np = test_bind.np.fft.rfft(signal_np)
          hermitian_nc = test_bind.numpycore.array(hermitian_np.tolist())
      
          result_np = test_bind.np.fft.hfft(hermitian_np)
          result_nc = test_bind.numpycore.fft.hfft(hermitian_nc)
      
          assert_arrays_equal(result_np, result_nc, "hfft")
      
      def test_ihfft():
          """Test inverse Hermitian FFT"""
          data_np = test_bind.np.random.randn(16)
          data_nc = test_bind.numpycore.array(data_np.tolist())
      
          result_np = test_bind.np.fft.ihfft(data_np)
          result_nc = test_bind.numpycore.fft.ihfft(data_nc)

.. _example-fft-hermitian-ihfft-5:

.. dropdown:: ihfft (test_phase4_fft.py:82)
   :class-title: example-dropdown

   .. code-block:: python
      :linenos:
      :lineno-start: 72
      :emphasize-lines: 11

          result_nc = test_bind.numpycore.fft.hfft(hermitian_nc)
      
          assert_arrays_equal(result_np, result_nc, "hfft")
      
      def test_ihfft():
          """Test inverse Hermitian FFT"""
          data_np = test_bind.np.random.randn(16)
          data_nc = test_bind.numpycore.array(data_np.tolist())
      
          result_np = test_bind.np.fft.ihfft(data_np)
          result_nc = test_bind.numpycore.fft.ihfft(data_nc)
      
          assert_arrays_equal(result_np, result_nc, "ihfft")
      
      def test_round_trip_rfft2():
          """Test rfft2 -> irfft2 round trip"""
          data_np = test_bind.np.random.randn(6, 8)
          data_nc = test_bind.numpycore.array(data_np.tolist())
      
          # Forward transform
          fft_np = test_bind.np.fft.rfft2(data_np)

.. _example-fft-helper-fftshift-6:

.. dropdown:: fftshift (test_fft_and_bitwise.py:185)
   :class-title: example-dropdown

   .. code-block:: python
      :linenos:
      :lineno-start: 175
      :emphasize-lines: 11

          assert_arrays_equal(np_result, nc_result, "rfftfreq")
      
      
      def test_fftshift():
          """Test np.fft.fftshift() to shift zero-frequency to center"""
          np_arr = test_bind.np.array([0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0])
      
          nc_arr = test_bind.numpycore.arange(0.0, 8.0, 1.0)
      
          np_result = test_bind.np.fft.fftshift(np_arr)
          nc_result = test_bind.numpycore.fft.fftshift(nc_arr)  # Use numpycore implementation
      
          assert_arrays_equal(np_result, nc_result, "fftshift")
      
      
      def test_ifftshift():
          """Test np.fft.ifftshift() to undo fftshift"""
          np_arr = test_bind.np.array([4.0, 5.0, 6.0, 7.0, 0.0, 1.0, 2.0, 3.0])
      
          nc_arr = test_bind.numpycore.zeros([8])
          for i, val in enumerate([4.0, 5.0, 6.0, 7.0, 0.0, 1.0, 2.0, 3.0]):

.. _example-fft-helper-ifftshift-7:

.. dropdown:: ifftshift (test_fft_and_bitwise.py:199)
   :class-title: example-dropdown

   .. code-block:: python
      :linenos:
      :lineno-start: 189
      :emphasize-lines: 11

      
      def test_ifftshift():
          """Test np.fft.ifftshift() to undo fftshift"""
          np_arr = test_bind.np.array([4.0, 5.0, 6.0, 7.0, 0.0, 1.0, 2.0, 3.0])
      
          nc_arr = test_bind.numpycore.zeros([8])
          for i, val in enumerate([4.0, 5.0, 6.0, 7.0, 0.0, 1.0, 2.0, 3.0]):
              nc_arr.itemset(i, val)
      
          np_result = test_bind.np.fft.ifftshift(np_arr)
          nc_result = test_bind.numpycore.fft.ifftshift(nc_arr)  # Use numpycore implementation
      
          assert_arrays_equal(np_result, nc_result, "ifftshift")
      
      
      def test_fftn_1d():
          """Test np.fft.fftn() for 1D FFT"""
          np_signal = test_bind.np.array([1.0, 2.0, 3.0, 4.0])
          nc_signal = test_bind.numpycore.arange(1.0, 5.0, 1.0)
      
          np_result = test_bind.np.fft.fftn(np_signal)