{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e48e1280-aa2f-401b-b4a1-338569c8c48e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9508808b-720c-49d5-888d-4c96358cb385",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(6.123233995736766e-17-1j)\n"
     ]
    }
   ],
   "source": [
    "N = 4\n",
    "W = np.exp(-1j * (2 * np.pi) / N)\n",
    "print(W)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c81b826e-0d66-406a-87f9-6f68ee9db081",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 100, 200, 300]\n"
     ]
    }
   ],
   "source": [
    "# let us try to grasp this idea for a small example\n",
    "N = 4\n",
    "f = [0, 100, 200, 300]\n",
    "print(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "8db1c4a4-0c12-46d2-8b3c-6f314484aebe",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 200]\n",
      "[100, 300]\n"
     ]
    }
   ],
   "source": [
    "# splitting the array into even and odd indices\n",
    "f_even = f[0::2]\n",
    "f_odd = f[1::2]\n",
    "print(f_even)\n",
    "print(f_odd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "d96489e5-a977-4b3b-b1b4-33fd00e98081",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0]\n",
      "[200]\n"
     ]
    }
   ],
   "source": [
    "# recursively, we split the resulting arrays, first the even, into even and odd\n",
    "f_even_even = f_even[0::2]\n",
    "f_even_odd = f_even[1::2]\n",
    "print(f_even_even)\n",
    "print(f_even_odd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "c27a2ace-0fbc-4024-a15a-a6bc3236bdf5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[np.complex128(200+0j), np.complex128(-200+0j)]\n"
     ]
    }
   ],
   "source": [
    "reseven0 = f_even_even[0] + np.exp(-2j * np.pi * 0 / N) * f_even_odd[0]\n",
    "reseven1 = f_even_even[0] - np.exp(-2j * np.pi * 0 / N) * f_even_odd[0]\n",
    "reseven = [reseven0, reseven1]\n",
    "print(reseven)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "1898cdd1-b3ae-40cc-999b-47f9e8992f29",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[100]\n",
      "[300]\n"
     ]
    }
   ],
   "source": [
    "# separate the odd indices, into even and odd indices\n",
    "f_odd_even = f_odd[0::2]\n",
    "f_odd_odd = f_odd[1::2]\n",
    "print(f_odd_even)\n",
    "print(f_odd_odd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "ff3a56eb-1eef-4c26-89f7-654572a58141",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[np.complex128(400+0j), np.complex128(-200+0j)]\n"
     ]
    }
   ],
   "source": [
    "resodd0 = f_odd_even[0] + np.exp(-2j * np.pi * 0 / N) * f_odd_odd[0]\n",
    "resodd1 = f_odd_even[0] - np.exp(-2j * np.pi * 0 / N) * f_odd_odd[0]\n",
    "resodd = [resodd0, resodd1]\n",
    "print(resodd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0d344814-5d68-4870-868f-18a8aa24f2ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "# from the symmetric property, I can use the result 0 to also\n",
    "# obtain the value for 0+N/2 = N/4 = 2, changing the signal\n",
    "res0 = reseven[0] + np.exp(-2j * np.pi * 0 / N) * resodd[0]\n",
    "res2 = reseven[0] - np.exp(-2j * np.pi * 0 / N) * resodd[0]\n",
    "\n",
    "# similarly the result 1 is used to obtain the result of 1+N/2 = 3\n",
    "res1 = reseven[1] + np.exp(-2j * np.pi * 1 / N) * resodd[1]\n",
    "res3 = reseven[1] - np.exp(-2j * np.pi * 1 / N) * resodd[1]\n",
    "\n",
    "# putting everything together\n",
    "F_manual = np.array([res0, res1, res2, res3]).astype(np.complex64)\n",
    "print(F_manual)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "93bce2d8-7aea-4798-a34f-2bb4861351ac",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eaa1179d-bece-4dc5-b746-4e883713d4f9",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}