10-Divide _ Conquer.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "6a749398",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "7fb2cb10",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[4 2 3]\n",
      " [2 4 8]\n",
      " [0 9 0]\n",
      " [5 1 2]\n",
      " [7 2 3]]\n"
     ]
    }
   ],
   "source": [
    "N = 15\n",
    "L = 5\n",
    "M = 3\n",
    "x = np.array([4,2,0,5,7,2,4,9,1,2,3,8,0,2,3])\n",
    "np.shape(x)\n",
    "y = x.reshape(L,M,order='F')\n",
    "print(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "222ce56e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# DFT\n",
    "def DFT(x,N):\n",
    "    X = np.zeros(N,dtype = 'complex_')\n",
    "    for k in range(N):\n",
    "        for n in range(N):\n",
    "            X[k] = X[k] + x[n]*np.exp(-1j*2*np.pi*k*n/N)\n",
    "    return X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "fb11ddff",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(5, 3)\n",
      "[9. +0.j        1.5+0.8660254j 1.5-0.8660254j]\n",
      "[14.+0.j         -4.+3.46410162j -4.-3.46410162j]\n",
      "[ 9. +0.j         -4.5-7.79422863j -4.5+7.79422863j]\n",
      "[8. +0.j        3.5+0.8660254j 3.5-0.8660254j]\n",
      "[12. +0.j         4.5+0.8660254j  4.5-0.8660254j]\n"
     ]
    }
   ],
   "source": [
    "F = np.zeros((L,M), dtype= 'complex_')\n",
    "print(np.shape(F))\n",
    "\n",
    "for l in range(L):\n",
    "    F[l] = DFT(y[l,:],M) # for Row\n",
    "    # np.shape(F)\n",
    "    print(F[l])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "37f26696",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 9.        +0.j          1.5       +0.8660254j   1.5       -0.8660254j ]\n",
      " [14.        +0.j         -2.24520477+4.79156087j -5.25085162+0.65464289j]\n",
      " [ 9.        +0.j         -8.80332841-1.87120522j  8.22190912+3.66062979j]\n",
      " [ 8.        +0.j          1.90519858-3.06108124j -3.34059644-1.35661911j]\n",
      " [12.        +0.j          0.39090314-4.56587283j -4.2216074 +1.78270328j]]\n"
     ]
    }
   ],
   "source": [
    "G = np.zeros((L,M),dtype = 'complex_')\n",
    "for l in range(L):\n",
    "    for q in range(M):\n",
    "        G[l,q] = F[l,q] * np.exp(-1j*2*np.pi*l*q/N)\n",
    "print(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "971059df",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[52.          8.20656829  4.95715437  4.11892682 21.16279549  8.54400375\n",
      "  6.7848686  10.82658508 10.82658508  6.7848686   8.54400375 21.16279549\n",
      "  4.11892682  4.95715437  8.20656829]\n"
     ]
    }
   ],
   "source": [
    "X = np.zeros((L,M),dtype = 'complex_')\n",
    "for m in range(M):\n",
    "    X[:,m] = DFT(G[:,m],L) #column\n",
    "#print(abs(X))\n",
    "Y = X.reshape(N,)\n",
    "print(abs(Y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "b563a847",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[52.          8.20656829  4.95715437  4.11892682 21.16279549  8.54400375\n",
      "  6.7848686  10.82658508 10.82658508  6.7848686   8.54400375 21.16279549\n",
      "  4.11892682  4.95715437  8.20656829]\n"
     ]
    }
   ],
   "source": [
    "print(abs(np.fft.fft(x,N)))"
   ]
  }
 ],
 "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.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}