{"id":2107,"date":"2024-07-11T01:01:21","date_gmt":"2024-07-11T01:01:21","guid":{"rendered":"https:\/\/www.w3computing.com\/articles\/?p=2107"},"modified":"2024-07-11T01:01:25","modified_gmt":"2024-07-11T01:01:25","slug":"how-to-implement-a-fast-fourier-transform-fft-in-cpp","status":"publish","type":"post","link":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\/","title":{"rendered":"How to Implement a Fast Fourier Transform (FFT) in C++"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Introduction<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">The Fast Fourier Transform (FFT) is a highly efficient algorithm for computing the Discrete Fourier Transform (DFT) and its inverse. FFT is widely used in signal processing, image analysis, and many other fields. Understanding and implementing FFT in C++ can significantly enhance the performance of your applications that require frequency analysis.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">This tutorial aims to provide a comprehensive guide on how to implement the FFT in C++. While it is targeted at non-beginners, it assumes you have a basic understanding of complex numbers, C++ syntax, and fundamental algorithms. We&#8217;ll start with a brief overview of the FFT and its mathematical foundation before diving into the implementation details.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">1. Overview of Fourier Transform<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">The Fourier Transform is a mathematical operation that transforms a function of time (or space) into a function of frequency. The Discrete Fourier Transform (DFT) is a specific type of Fourier Transform applied to discrete data sets. The DFT is defined as:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=X%28k%29+%3D+%5Csum_%7Bn%3D0%7D%5E%7BN-1%7D+x%28n%29+%5Ccdot+e%5E%7B-i2%5Cpi+kn%2FN%7D&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"X(k) = &#92;sum_{n=0}^{N-1} x(n) &#92;cdot e^{-i2&#92;pi kn\/N}\" class=\"latex\" \/><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Where:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=X%28k%29&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"X(k)\" class=\"latex\" \/> is the DFT of the input sequence <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=x%28n%29&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"x(n)\" class=\"latex\" \/>.<\/li>\n\n\n\n<li><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=N&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"N\" class=\"latex\" \/> is the number of points in the input sequence.<\/li>\n\n\n\n<li><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=k&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"k\" class=\"latex\" \/> is the frequency index.<\/li>\n\n\n\n<li><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=i&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"i\" class=\"latex\" \/> is the imaginary unit.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">The Fast Fourier Transform (FFT) is an algorithm that efficiently computes the DFT, reducing the computational complexity from <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=O%28N%5E2%29&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"O(N^2)\" class=\"latex\" \/> to <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=O%28N+%5Clog+N%29&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"O(N &#92;log N)\" class=\"latex\" \/>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">2. Mathematical Foundation of FFT<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">The FFT algorithm leverages the symmetry and periodicity properties of the DFT. The most common FFT algorithm is the Cooley-Tukey algorithm, which recursively breaks down a DFT of any composite size <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=N&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"N\" class=\"latex\" \/> into many smaller DFTs.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Cooley-Tukey Algorithm<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">The Cooley-Tukey algorithm splits the DFT into smaller parts by separating the even and odd indexed elements of the input sequence. This divide-and-conquer approach reduces the overall complexity.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">For an input sequence <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=x&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"x\" class=\"latex\" \/> of length <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=N&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"N\" class=\"latex\" \/>:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=X%28k%29+%3D+%5Csum_%7Bn%3D0%7D%5E%7BN%2F2-1%7D+x%282n%29+%5Ccdot+e%5E%7B-i2%5Cpi+kn%2F%28N%2F2%29%7D+%2B+%5Csum_%7Bn%3D0%7D%5E%7BN%2F2-1%7D+x%282n%2B1%29+%5Ccdot+e%5E%7B-i2%5Cpi+k%282n%2B1%29%2FN%7D&#038;bg=ffffff&#038;fg=000&#038;s=3&#038;c=20201002\" alt=\"X(k) = &#92;sum_{n=0}^{N\/2-1} x(2n) &#92;cdot e^{-i2&#92;pi kn\/(N\/2)} + &#92;sum_{n=0}^{N\/2-1} x(2n+1) &#92;cdot e^{-i2&#92;pi k(2n+1)\/N}\" class=\"latex\" \/><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">This can be rewritten as:<\/p>\n\n\n<p><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=X%28k%29+%3D+%5Ctext%7BDFT%7D_%7BN%2F2%7D%28x_%7B%5Ctext%7Beven%7D%7D%29+%2B+e%5E%7B-i2%5Cpi+k%2FN%7D+%5Ccdot+%5Ctext%7BDFT%7D_%7BN%2F2%7D%28x_%7B%5Ctext%7Bodd%7D%7D%29&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"X(k) = &#92;text{DFT}_{N\/2}(x_{&#92;text{even}}) + e^{-i2&#92;pi k\/N} &#92;cdot &#92;text{DFT}_{N\/2}(x_{&#92;text{odd}})\" class=\"latex\" \/><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Where:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=x_%7B%5Ctext%7Beven%7D%7D&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"x_{&#92;text{even}}\" class=\"latex\" \/> is the sequence of even-indexed elements.<\/li>\n\n\n\n<li><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=x_%7B%5Ctext%7Bodd%7D%7D&#038;bg=ffffff&#038;fg=000&#038;s=2&#038;c=20201002\" alt=\"x_{&#92;text{odd}}\" class=\"latex\" \/> is the sequence of odd-indexed elements.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">This decomposition continues recursively until the base case of the DFT of length 1 is reached.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">3. Recursive Implementation of FFT<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Let&#8217;s implement the FFT using a recursive approach in C++.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Step-by-Step Implementation<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Include necessary headers:<\/strong><\/li>\n<\/ol>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-1\" data-shcb-language-name=\"C++\" data-shcb-language-slug=\"cpp\"><span><code class=\"hljs language-cpp\"><span class=\"hljs-meta\">#<span class=\"hljs-meta-keyword\">include<\/span> <span class=\"hljs-meta-string\">&lt;iostream&gt;<\/span><\/span>\n<span class=\"hljs-meta\">#<span class=\"hljs-meta-keyword\">include<\/span> <span class=\"hljs-meta-string\">&lt;vector&gt;<\/span><\/span>\n<span class=\"hljs-meta\">#<span class=\"hljs-meta-keyword\">include<\/span> <span class=\"hljs-meta-string\">&lt;complex&gt;<\/span><\/span>\n<span class=\"hljs-meta\">#<span class=\"hljs-meta-keyword\">include<\/span> <span class=\"hljs-meta-string\">&lt;cmath&gt;<\/span><\/span><\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-1\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">C++<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">cpp<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<ol class=\"wp-block-list\" start=\"2\">\n<li><strong>Define the FFT function:<\/strong><\/li>\n<\/ol>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"C++\" data-shcb-language-slug=\"cpp\"><span><code class=\"hljs language-cpp\"><span class=\"hljs-keyword\">using<\/span> <span class=\"hljs-keyword\">namespace<\/span> <span class=\"hljs-built_in\">std<\/span>;\n<span class=\"hljs-keyword\">using<\/span> Complex = <span class=\"hljs-built_in\">complex<\/span>&lt;<span class=\"hljs-keyword\">double<\/span>&gt;;\n<span class=\"hljs-keyword\">using<\/span> CArray = <span class=\"hljs-built_in\">vector<\/span>&lt;Complex&gt;;\n\n<span class=\"hljs-keyword\">const<\/span> <span class=\"hljs-keyword\">double<\/span> PI = <span class=\"hljs-built_in\">acos<\/span>(<span class=\"hljs-number\">-1<\/span>);\n\n<span class=\"hljs-function\"><span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">fft<\/span><span class=\"hljs-params\">(CArray &amp;x)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">const<\/span> <span class=\"hljs-keyword\">size_t<\/span> N = x.size();\n    <span class=\"hljs-keyword\">if<\/span> (N &lt;= <span class=\"hljs-number\">1<\/span>) <span class=\"hljs-keyword\">return<\/span>;\n\n    <span class=\"hljs-comment\">\/\/ Divide<\/span>\n    <span class=\"hljs-function\">CArray <span class=\"hljs-title\">even<\/span><span class=\"hljs-params\">(N \/ <span class=\"hljs-number\">2<\/span>)<\/span><\/span>;\n    <span class=\"hljs-function\">CArray <span class=\"hljs-title\">odd<\/span><span class=\"hljs-params\">(N \/ <span class=\"hljs-number\">2<\/span>)<\/span><\/span>;\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">size_t<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; N \/ <span class=\"hljs-number\">2<\/span>; ++i) {\n        even&#91;i] = x&#91;i * <span class=\"hljs-number\">2<\/span>];\n        odd&#91;i] = x&#91;i * <span class=\"hljs-number\">2<\/span> + <span class=\"hljs-number\">1<\/span>];\n    }\n\n    <span class=\"hljs-comment\">\/\/ Conquer<\/span>\n    fft(even);\n    fft(odd);\n\n    <span class=\"hljs-comment\">\/\/ Combine<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">size_t<\/span> k = <span class=\"hljs-number\">0<\/span>; k &lt; N \/ <span class=\"hljs-number\">2<\/span>; ++k) {\n        Complex t = polar(<span class=\"hljs-number\">1.0<\/span>, <span class=\"hljs-number\">-2<\/span> * PI * k \/ N) * odd&#91;k];\n        x&#91;k] = even&#91;k] + t;\n        x&#91;k + N \/ <span class=\"hljs-number\">2<\/span>] = even&#91;k] - t;\n    }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">C++<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">cpp<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<ol class=\"wp-block-list\" start=\"3\">\n<li><strong>Implement the main function to test FFT:<\/strong><\/li>\n<\/ol>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"C++\" data-shcb-language-slug=\"cpp\"><span><code class=\"hljs language-cpp\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">main<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">const<\/span> <span class=\"hljs-keyword\">size_t<\/span> N = <span class=\"hljs-number\">8<\/span>;\n    <span class=\"hljs-function\">CArray <span class=\"hljs-title\">data<\/span><span class=\"hljs-params\">(N)<\/span><\/span>;\n\n    <span class=\"hljs-comment\">\/\/ Sample data<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">size_t<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; N; ++i) {\n        data&#91;i] = Complex(i, <span class=\"hljs-number\">0<\/span>);\n    }\n\n    <span class=\"hljs-comment\">\/\/ Perform FFT<\/span>\n    fft(data);\n\n    <span class=\"hljs-comment\">\/\/ Output the results<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">size_t<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; N; ++i) {\n        <span class=\"hljs-built_in\">cout<\/span> &lt;&lt; data&#91;i] &lt;&lt; <span class=\"hljs-built_in\">endl<\/span>;\n    }\n\n    <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-number\">0<\/span>;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">C++<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">cpp<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\">Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Divide:<\/strong> Split the input sequence into even and odd indexed elements.<\/li>\n\n\n\n<li><strong>Conquer:<\/strong> Recursively apply the FFT to the smaller sequences.<\/li>\n\n\n\n<li><strong>Combine:<\/strong> Combine the results of the smaller sequences to form the final result.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">4. Iterative Implementation of FFT<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">The recursive approach can be memory-intensive and may lead to stack overflow for large inputs. An iterative implementation of FFT can address these issues.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Step-by-Step Implementation<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Include necessary headers:<\/strong><\/li>\n<\/ol>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"C++\" data-shcb-language-slug=\"cpp\"><span><code class=\"hljs language-cpp\"><span class=\"hljs-meta\">#<span class=\"hljs-meta-keyword\">include<\/span> <span class=\"hljs-meta-string\">&lt;iostream&gt;<\/span><\/span>\n<span class=\"hljs-meta\">#<span class=\"hljs-meta-keyword\">include<\/span> <span class=\"hljs-meta-string\">&lt;vector&gt;<\/span><\/span>\n<span class=\"hljs-meta\">#<span class=\"hljs-meta-keyword\">include<\/span> <span class=\"hljs-meta-string\">&lt;complex&gt;<\/span><\/span>\n<span class=\"hljs-meta\">#<span class=\"hljs-meta-keyword\">include<\/span> <span class=\"hljs-meta-string\">&lt;cmath&gt;<\/span><\/span><\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">C++<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">cpp<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<ol class=\"wp-block-list\" start=\"2\">\n<li><strong>Define the FFT function:<\/strong><\/li>\n<\/ol>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-5\" data-shcb-language-name=\"C++\" data-shcb-language-slug=\"cpp\"><span><code class=\"hljs language-cpp\"><span class=\"hljs-keyword\">using<\/span> <span class=\"hljs-keyword\">namespace<\/span> <span class=\"hljs-built_in\">std<\/span>;\n<span class=\"hljs-keyword\">using<\/span> Complex = <span class=\"hljs-built_in\">complex<\/span>&lt;<span class=\"hljs-keyword\">double<\/span>&gt;;\n<span class=\"hljs-keyword\">using<\/span> CArray = <span class=\"hljs-built_in\">vector<\/span>&lt;Complex&gt;;\n\n<span class=\"hljs-keyword\">const<\/span> <span class=\"hljs-keyword\">double<\/span> PI = <span class=\"hljs-built_in\">acos<\/span>(<span class=\"hljs-number\">-1<\/span>);\n\n<span class=\"hljs-function\"><span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">fft<\/span><span class=\"hljs-params\">(CArray &amp;x)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">const<\/span> <span class=\"hljs-keyword\">size_t<\/span> N = x.size();\n    <span class=\"hljs-keyword\">if<\/span> (N &lt;= <span class=\"hljs-number\">1<\/span>) <span class=\"hljs-keyword\">return<\/span>;\n\n    <span class=\"hljs-comment\">\/\/ Bit-reversed addressing permutation<\/span>\n    <span class=\"hljs-keyword\">size_t<\/span> j = <span class=\"hljs-number\">0<\/span>;\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">size_t<\/span> i = <span class=\"hljs-number\">1<\/span>; i &lt; N; ++i) {\n        <span class=\"hljs-keyword\">size_t<\/span> bit = N &gt;&gt; <span class=\"hljs-number\">1<\/span>;\n        <span class=\"hljs-keyword\">while<\/span> (j &amp; bit) {\n            j ^= bit;\n            bit &gt;&gt;= <span class=\"hljs-number\">1<\/span>;\n        }\n        j ^= bit;\n\n        <span class=\"hljs-keyword\">if<\/span> (i &lt; j) {\n            swap(x&#91;i], x&#91;j]);\n        }\n    }\n\n    <span class=\"hljs-comment\">\/\/ Iterative FFT<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">size_t<\/span> len = <span class=\"hljs-number\">2<\/span>; len &lt;= N; len &lt;&lt;= <span class=\"hljs-number\">1<\/span>) {\n        <span class=\"hljs-keyword\">double<\/span> angle = <span class=\"hljs-number\">-2<\/span> * PI \/ len;\n        <span class=\"hljs-function\">Complex <span class=\"hljs-title\">wlen<\/span><span class=\"hljs-params\">(<span class=\"hljs-built_in\">cos<\/span>(angle), <span class=\"hljs-built_in\">sin<\/span>(angle))<\/span><\/span>;\n        <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">size_t<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; N; i += len) {\n            <span class=\"hljs-function\">Complex <span class=\"hljs-title\">w<\/span><span class=\"hljs-params\">(<span class=\"hljs-number\">1<\/span>)<\/span><\/span>;\n            <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">size_t<\/span> j = <span class=\"hljs-number\">0<\/span>; j &lt; len \/ <span class=\"hljs-number\">2<\/span>; ++j) {\n                Complex u = x&#91;i + j];\n                Complex v = x&#91;i + j + len \/ <span class=\"hljs-number\">2<\/span>] * w;\n                x&#91;i + j] = u + v;\n                x&#91;i + j + len \/ <span class=\"hljs-number\">2<\/span>] = u - v;\n                w *= wlen;\n            }\n        }\n    }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-5\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">C++<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">cpp<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<ol class=\"wp-block-list\" start=\"3\">\n<li><strong>Implement the main function to test FFT:<\/strong><\/li>\n<\/ol>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-6\" data-shcb-language-name=\"C++\" data-shcb-language-slug=\"cpp\"><span><code class=\"hljs language-cpp\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">main<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">const<\/span> <span class=\"hljs-keyword\">size_t<\/span> N = <span class=\"hljs-number\">8<\/span>;\n    <span class=\"hljs-function\">CArray <span class=\"hljs-title\">data<\/span><span class=\"hljs-params\">(N)<\/span><\/span>;\n\n    <span class=\"hljs-comment\">\/\/ Sample data<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">size_t<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; N; ++i) {\n        data&#91;i] = Complex(i, <span class=\"hljs-number\">0<\/span>);\n    }\n\n    <span class=\"hljs-comment\">\/\/ Perform FFT<\/span>\n    fft(data);\n\n    <span class=\"hljs-comment\">\/\/ Output the results<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">size_t<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; N; ++i) {\n        <span class=\"hljs-built_in\">cout<\/span> &lt;&lt; data&#91;i] &lt;&lt; <span class=\"hljs-built_in\">endl<\/span>;\n    }\n\n    <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-number\">0<\/span>;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-6\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">C++<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">cpp<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\">Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Bit-reversed addressing permutation:<\/strong> This step reorders the input sequence to ensure the FFT computation follows the correct order.<\/li>\n\n\n\n<li><strong>Iterative FFT:<\/strong> This loop iteratively applies the FFT algorithm, reducing the complexity by computing the results in place.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">5. Optimization Techniques<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">To further optimize the FFT implementation, consider the following techniques:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>In-Place Computation<\/strong> &#8211; Perform the FFT computation in place to reduce memory usage. The iterative implementation already achieves this by modifying the input sequence directly.<\/li>\n\n\n\n<li><strong>Loop Unrolling<\/strong> &#8211; Unroll loops to reduce the overhead of loop control and increase performance. However, this may increase the code size and complexity.<\/li>\n\n\n\n<li><strong>SIMD Instructions<\/strong> &#8211; Utilize Single Instruction, Multiple Data (SIMD) instructions to parallelize operations. Libraries like Intel&#8217;s Math Kernel Library (MKL) can provide highly optimized FFT implementations.<\/li>\n\n\n\n<li><strong>Cache Optimization<\/strong> &#8211; Optimize data access patterns to reduce cache misses. Ensure the data is accessed sequentially to take advantage of cache locality.<\/li>\n\n\n\n<li><strong>Multithreading<\/strong> &#8211; Parallelize the computation using multithreading. This can be achieved using libraries like OpenMP or C++&#8217;s <code>&lt;thread><\/code> library.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">6. Example Application<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Let&#8217;s apply our FFT implementation to a real-world example: analyzing the frequency components of a signal.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Step-by-Step Implementation<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Generate a sample signal:<\/strong><\/li>\n<\/ol>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-7\" data-shcb-language-name=\"PHP\" data-shcb-language-slug=\"php\"><span><code class=\"hljs language-php\"><span class=\"hljs-comment\">#include &lt;iostream&gt;<\/span>\n<span class=\"hljs-comment\">#include &lt;vector&gt;<\/span>\n<span class=\"hljs-comment\">#include &lt;complex&gt;<\/span>\n<span class=\"hljs-comment\">#include &lt;cmath&gt;<\/span>\n\nusing <span class=\"hljs-keyword\">namespace<\/span> <span class=\"hljs-title\">std<\/span>;\nusing Complex = complex&lt;double&gt;;\nusing CArray = vector&lt;Complex&gt;;\n\n<span class=\"hljs-keyword\">const<\/span> double PI = acos(<span class=\"hljs-number\">-1<\/span>);\n\nvoid fft(CArray &amp;x) {\n    <span class=\"hljs-keyword\">const<\/span> size_t N = x.size();\n    <span class=\"hljs-keyword\">if<\/span> (N &lt;= <span class=\"hljs-number\">1<\/span>) <span class=\"hljs-keyword\">return<\/span>;\n\n    <span class=\"hljs-comment\">\/\/ Bit<\/span>\n\n-reversed addressing permutation\n    size_t j = <span class=\"hljs-number\">0<\/span>;\n    <span class=\"hljs-keyword\">for<\/span> (size_t i = <span class=\"hljs-number\">1<\/span>; i &lt; N; ++i) {\n        size_t bit = N &gt;&gt; <span class=\"hljs-number\">1<\/span>;\n        <span class=\"hljs-keyword\">while<\/span> (j &amp; bit) {\n            j ^= bit;\n            bit &gt;&gt;= <span class=\"hljs-number\">1<\/span>;\n        }\n        j ^= bit;\n\n        <span class=\"hljs-keyword\">if<\/span> (i &lt; j) {\n            swap(x&#91;i], x&#91;j]);\n        }\n    }\n\n    <span class=\"hljs-comment\">\/\/ Iterative FFT<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (size_t len = <span class=\"hljs-number\">2<\/span>; len &lt;= N; len &lt;&lt;= <span class=\"hljs-number\">1<\/span>) {\n        double angle = <span class=\"hljs-number\">-2<\/span> * PI \/ len;\n        Complex wlen(cos(angle), sin(angle));\n        <span class=\"hljs-keyword\">for<\/span> (size_t i = <span class=\"hljs-number\">0<\/span>; i &lt; N; i += len) {\n            Complex w(<span class=\"hljs-number\">1<\/span>);\n            <span class=\"hljs-keyword\">for<\/span> (size_t j = <span class=\"hljs-number\">0<\/span>; j &lt; len \/ <span class=\"hljs-number\">2<\/span>; ++j) {\n                Complex u = x&#91;i + j];\n                Complex v = x&#91;i + j + len \/ <span class=\"hljs-number\">2<\/span>] * w;\n                x&#91;i + j] = u + v;\n                x&#91;i + j + len \/ <span class=\"hljs-number\">2<\/span>] = u - v;\n                w *= wlen;\n            }\n        }\n    }\n}\n\nint main() {\n    <span class=\"hljs-keyword\">const<\/span> size_t N = <span class=\"hljs-number\">1024<\/span>;\n    CArray signal(N);\n\n    <span class=\"hljs-comment\">\/\/ Generate a sample signal: a sum of two sine waves<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (size_t i = <span class=\"hljs-number\">0<\/span>; i &lt; N; ++i) {\n        signal&#91;i] = Complex(sin(<span class=\"hljs-number\">2<\/span> * PI * <span class=\"hljs-number\">50<\/span> * i \/ N) + <span class=\"hljs-number\">0.5<\/span> * sin(<span class=\"hljs-number\">2<\/span> * PI * <span class=\"hljs-number\">120<\/span> * i \/ N), <span class=\"hljs-number\">0<\/span>);\n    }\n\n    <span class=\"hljs-comment\">\/\/ Perform FFT<\/span>\n    fft(signal);\n\n    <span class=\"hljs-comment\">\/\/ Output the results (magnitude)<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (size_t i = <span class=\"hljs-number\">0<\/span>; i &lt; N; ++i) {\n        cout &lt;&lt; abs(signal&#91;i]) &lt;&lt; endl;\n    }\n\n    <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-number\">0<\/span>;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-7\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">PHP<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">php<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\">Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Generate a sample signal:<\/strong> Create a signal that is the sum of two sine waves with different frequencies.<\/li>\n\n\n\n<li><strong>Perform FFT:<\/strong> Apply the FFT to the signal.<\/li>\n\n\n\n<li><strong>Output the results:<\/strong> Print the magnitude of the FFT results to analyze the frequency components.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">7. Conclusion<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">In this tutorial, we covered the implementation of the Fast Fourier Transform (FFT) in C++. We started with the mathematical foundation of the FFT, followed by recursive and iterative implementations. We also discussed optimization techniques to enhance the performance of the FFT.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Implementing the FFT in C++ provides a deep understanding of the algorithm and its performance characteristics. This knowledge is essential for optimizing applications that require frequency analysis.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">By applying these techniques, you can efficiently analyze and process signals, images, and other data in your applications.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Further Reading<\/h2>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Numerical Recipes: The Art of Scientific Computing<\/strong> by William H. Press et al. &#8211; This book provides an in-depth look at numerical algorithms, including the FFT.<\/li>\n\n\n\n<li><strong>The Scientist and Engineer&#8217;s Guide to Digital Signal Processing<\/strong> by Steven W. Smith &#8211; This book offers a comprehensive introduction to digital signal processing and the FFT.<\/li>\n\n\n\n<li><strong>Intel Math Kernel Library (MKL)<\/strong> &#8211; A highly optimized library for mathematical computations, including the FFT.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Introduction The Fast Fourier Transform (FFT) is a highly efficient algorithm for computing the Discrete Fourier Transform (DFT) and its inverse. FFT is widely used in signal processing, image analysis, and many other fields. Understanding and implementing FFT in C++ can significantly enhance the performance of your applications that require frequency analysis. This tutorial aims [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_genesis_hide_title":false,"_genesis_hide_breadcrumbs":false,"_genesis_hide_singular_image":false,"_genesis_hide_footer_widgets":false,"_genesis_custom_body_class":"","_genesis_custom_post_class":"","_genesis_layout":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false},"categories":[9,4],"tags":[],"class_list":["post-2107","post","type-post","status-publish","format-standard","category-cplusplus","category-programming-languages","entry"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.9 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>How to Implement a Fast Fourier Transform (FFT) in C++<\/title>\n<meta name=\"description\" content=\"The Fast Fourier Transform (FFT) is a highly efficient algorithm for computing the Discrete Fourier Transform (DFT) and its inverse.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"How to Implement a Fast Fourier Transform (FFT) in C++\" \/>\n<meta property=\"og:description\" content=\"The Fast Fourier Transform (FFT) is a highly efficient algorithm for computing the Discrete Fourier Transform (DFT) and its inverse.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\/\" \/>\n<meta property=\"article:published_time\" content=\"2024-07-11T01:01:21+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-07-11T01:01:25+00:00\" \/>\n<meta name=\"author\" content=\"w3compadmin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"w3compadmin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"TechArticle\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\\\/\"},\"author\":{\"name\":\"w3compadmin\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#\\\/schema\\\/person\\\/a550b3e20d78bb4f79b7c6b7b53f0561\"},\"headline\":\"How to Implement a Fast Fourier Transform (FFT) in C++\",\"datePublished\":\"2024-07-11T01:01:21+00:00\",\"dateModified\":\"2024-07-11T01:01:25+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\\\/\"},\"wordCount\":946,\"articleSection\":[\"C++\",\"Programming Languages\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\\\/\",\"url\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\\\/\",\"name\":\"How to Implement a Fast Fourier Transform (FFT) in C++\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#website\"},\"datePublished\":\"2024-07-11T01:01:21+00:00\",\"dateModified\":\"2024-07-11T01:01:25+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#\\\/schema\\\/person\\\/a550b3e20d78bb4f79b7c6b7b53f0561\"},\"description\":\"The Fast Fourier Transform (FFT) is a highly efficient algorithm for computing the Discrete Fourier Transform (DFT) and its inverse.\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Articles Home\",\"item\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Programming Languages\",\"item\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/programming-languages\\\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"How to Implement a Fast Fourier Transform (FFT) in C++\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#website\",\"url\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/\",\"name\":\"Developer Articles Hub\",\"description\":\"\",\"alternateName\":\"Developer Articles\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#\\\/schema\\\/person\\\/a550b3e20d78bb4f79b7c6b7b53f0561\",\"name\":\"w3compadmin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/wp-content\\\/litespeed\\\/avatar\\\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1783167470\",\"url\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/wp-content\\\/litespeed\\\/avatar\\\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1783167470\",\"contentUrl\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/wp-content\\\/litespeed\\\/avatar\\\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1783167470\",\"caption\":\"w3compadmin\"},\"sameAs\":[\"http:\\\/\\\/w3computing.com\\\/articles\"]}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"How to Implement a Fast Fourier Transform (FFT) in C++","description":"The Fast Fourier Transform (FFT) is a highly efficient algorithm for computing the Discrete Fourier Transform (DFT) and its inverse.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\/","og_locale":"en_US","og_type":"article","og_title":"How to Implement a Fast Fourier Transform (FFT) in C++","og_description":"The Fast Fourier Transform (FFT) is a highly efficient algorithm for computing the Discrete Fourier Transform (DFT) and its inverse.","og_url":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\/","article_published_time":"2024-07-11T01:01:21+00:00","article_modified_time":"2024-07-11T01:01:25+00:00","author":"w3compadmin","twitter_card":"summary_large_image","twitter_misc":{"Written by":"w3compadmin","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"TechArticle","@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\/#article","isPartOf":{"@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\/"},"author":{"name":"w3compadmin","@id":"https:\/\/www.w3computing.com\/articles\/#\/schema\/person\/a550b3e20d78bb4f79b7c6b7b53f0561"},"headline":"How to Implement a Fast Fourier Transform (FFT) in C++","datePublished":"2024-07-11T01:01:21+00:00","dateModified":"2024-07-11T01:01:25+00:00","mainEntityOfPage":{"@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\/"},"wordCount":946,"articleSection":["C++","Programming Languages"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\/","url":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\/","name":"How to Implement a Fast Fourier Transform (FFT) in C++","isPartOf":{"@id":"https:\/\/www.w3computing.com\/articles\/#website"},"datePublished":"2024-07-11T01:01:21+00:00","dateModified":"2024-07-11T01:01:25+00:00","author":{"@id":"https:\/\/www.w3computing.com\/articles\/#\/schema\/person\/a550b3e20d78bb4f79b7c6b7b53f0561"},"description":"The Fast Fourier Transform (FFT) is a highly efficient algorithm for computing the Discrete Fourier Transform (DFT) and its inverse.","breadcrumb":{"@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.w3computing.com\/articles\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-fast-fourier-transform-fft-in-cpp\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Articles Home","item":"https:\/\/www.w3computing.com\/articles\/"},{"@type":"ListItem","position":2,"name":"Programming Languages","item":"https:\/\/www.w3computing.com\/articles\/programming-languages\/"},{"@type":"ListItem","position":3,"name":"How to Implement a Fast Fourier Transform (FFT) in C++"}]},{"@type":"WebSite","@id":"https:\/\/www.w3computing.com\/articles\/#website","url":"https:\/\/www.w3computing.com\/articles\/","name":"Developer Articles Hub","description":"","alternateName":"Developer Articles","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.w3computing.com\/articles\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/www.w3computing.com\/articles\/#\/schema\/person\/a550b3e20d78bb4f79b7c6b7b53f0561","name":"w3compadmin","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.w3computing.com\/articles\/wp-content\/litespeed\/avatar\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1783167470","url":"https:\/\/www.w3computing.com\/articles\/wp-content\/litespeed\/avatar\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1783167470","contentUrl":"https:\/\/www.w3computing.com\/articles\/wp-content\/litespeed\/avatar\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1783167470","caption":"w3compadmin"},"sameAs":["http:\/\/w3computing.com\/articles"]}]}},"featured_image_src":null,"featured_image_src_square":null,"author_info":{"display_name":"w3compadmin","author_link":"https:\/\/www.w3computing.com\/articles\/author\/w3compadmin\/"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/posts\/2107","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/comments?post=2107"}],"version-history":[{"count":13,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/posts\/2107\/revisions"}],"predecessor-version":[{"id":2120,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/posts\/2107\/revisions\/2120"}],"wp:attachment":[{"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/media?parent=2107"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/categories?post=2107"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/tags?post=2107"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}