.. _sphx_glr_api_gallery_special_functions_fourier_transform:

Discrete Fourier transform
----------------------------

Naive DFT vs. hand-rolled radix-2 FFT vs. ``numpy.fft``.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Cross-checks all three methods for correctness, then times them across a range of signal lengths to make the algorithmic speedup visible directly.">

.. only:: html

  .. image:: /api/gallery/special_functions/fourier_transform/images/thumb/sphx_glr_plot_01_naive_vs_radix2_vs_numpy_thumb.png
    :alt:

  :doc:`/api/gallery/special_functions/fourier_transform/plot_01_naive_vs_radix2_vs_numpy`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">O(n^2) vs. O(n log n): naive DFT vs. radix-2 FFT vs. numpy.fft</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/special_functions/fourier_transform/plot_01_naive_vs_radix2_vs_numpy