{
    "nbformat": 4,
    "nbformat_minor": 5,
    "metadata": {
        "kernelspec": {
            "display_name": "Python",
            "language": "python",
            "name": "python"
        },
        "language_info": {
            "name": "python"
        }
    },
    "cells": [
        {
            "id": "8c049747",
            "cell_type": "markdown",
            "source": "<div class='alert alert-warning'>\n\nSciPy's interactive examples with Jupyterlite are experimental and may not always work as expected. Execution of cells containing imports may result in large downloads (up to 60MB of content for the first import from SciPy). Load times when importing from SciPy may take roughly 10-20 seconds. If you notice any problems, feel free to open an [issue](https://github.com/scipy/scipy/issues/new/choose).\n\n</div>",
            "metadata": {}
        },
        {
            "id": "01c90b40",
            "cell_type": "markdown",
            "source": "On a particular machine, an FFT of prime length takes 11.4 ms:\n",
            "metadata": {}
        },
        {
            "id": "9c8360ff",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "from scipy import fft\nimport numpy as np\nrng = np.random.default_rng()\nmin_len = 93059  # prime length is worst case for speed\na = rng.standard_normal(min_len)\nb = fft.fft(a)",
            "outputs": []
        },
        {
            "id": "7ae257a1",
            "cell_type": "markdown",
            "source": "Zero-padding to the next regular length reduces computation time to\n1.6 ms, a speedup of 7.3 times:\n",
            "metadata": {}
        },
        {
            "id": "68a65493",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "fft.next_fast_len(min_len, real=True)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "93312"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "ce66e8d7",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "b = fft.fft(a, 93312)",
            "outputs": []
        },
        {
            "id": "22bc4cdf",
            "cell_type": "markdown",
            "source": "Rounding up to the next power of 2 is not optimal, taking 3.0 ms to\ncompute; 1.9 times longer than the size given by ``next_fast_len``:\n",
            "metadata": {}
        },
        {
            "id": "6bab4360",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "b = fft.fft(a, 131072)",
            "outputs": []
        }
    ]
}