calculations.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 18,
      "metadata": {
        "id": "6GA_pwQNBBcR"
      },
      "outputs": [],
      "source": [
        "p = 2\n",
        "m = 4\n",
        "irreducible_poly = [1,1,0,1]"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def generate_field_elements(comb, sol, idx):\n",
        "  if(idx == m):\n",
        "    sol.add(tuple(comb))\n",
        "    return\n",
        "  for i in range(p):\n",
        "    comb.append(i)\n",
        "    generate_field_elements(comb, sol, idx + 1)\n",
        "    comb.pop()\n",
        "  return sol"
      ],
      "metadata": {
        "id": "IZ4hV9QNKMih"
      },
      "execution_count": 19,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "sol = generate_field_elements([], set(), 0)\n",
        "field_elements = list(map(list, sol))\n",
        "\n",
        "for i in range(p ** m):\n",
        "  while(field_elements[i] and field_elements[i][-1] == 0): field_elements[i].pop()\n",
        "  if(field_elements[i] == []): field_elements[i] = [0]"
      ],
      "metadata": {
        "id": "62Jbp_3sLafJ"
      },
      "execution_count": 20,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# list(map(int, '1 3 3 4 2'.split()))[::-1]"
      ],
      "metadata": {
        "id": "7z3OeBH4LLF5"
      },
      "execution_count": 21,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "field_elements"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "l-21I247M5nb",
        "outputId": "8790e9c6-fe1a-4c50-dba3-0f5d3ab238ab"
      },
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[[0, 0, 0, 1],\n",
              " [0, 0, 1],\n",
              " [0, 1, 0, 1],\n",
              " [0, 1, 1, 1],\n",
              " [1, 0, 1, 1],\n",
              " [1, 1],\n",
              " [0, 1],\n",
              " [1, 1, 1],\n",
              " [0, 1, 1],\n",
              " [0],\n",
              " [1, 0, 1],\n",
              " [1, 0, 0, 1],\n",
              " [1, 1, 0, 1],\n",
              " [1],\n",
              " [0, 0, 1, 1],\n",
              " [1, 1, 1, 1]]"
            ]
          },
          "metadata": {},
          "execution_count": 22
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def generate_polynomial(poly):\n",
        "    ans = \"\"\n",
        "    for i in range(len(poly)):\n",
        "        if(poly[i] == 0): continue\n",
        "        else: ans += f\"{poly[i]} x**{i} + \"\n",
        "    if(ans): ans = ans[:-2]\n",
        "    else: return '0'\n",
        "    return ans.strip()\n",
        "\n",
        "field_elements_polynomials = {}\n",
        "for ele in field_elements:\n",
        "  field_elements_polynomials[generate_polynomial(ele)] = ele\n",
        "\n",
        "field_elements_polynomials"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "B-MXw_Vcfp8x",
        "outputId": "4fd26b77-03f7-444f-f5e5-c03ec894d6e0"
      },
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{'1 x**3': [0, 0, 0, 1],\n",
              " '1 x**2': [0, 0, 1],\n",
              " '1 x**1 + 1 x**3': [0, 1, 0, 1],\n",
              " '1 x**1 + 1 x**2 + 1 x**3': [0, 1, 1, 1],\n",
              " '1 x**0 + 1 x**2 + 1 x**3': [1, 0, 1, 1],\n",
              " '1 x**0 + 1 x**1': [1, 1],\n",
              " '1 x**1': [0, 1],\n",
              " '1 x**0 + 1 x**1 + 1 x**2': [1, 1, 1],\n",
              " '1 x**1 + 1 x**2': [0, 1, 1],\n",
              " '0': [0],\n",
              " '1 x**0 + 1 x**2': [1, 0, 1],\n",
              " '1 x**0 + 1 x**3': [1, 0, 0, 1],\n",
              " '1 x**0 + 1 x**1 + 1 x**3': [1, 1, 0, 1],\n",
              " '1 x**0': [1],\n",
              " '1 x**2 + 1 x**3': [0, 0, 1, 1],\n",
              " '1 x**0 + 1 x**1 + 1 x**2 + 1 x**3': [1, 1, 1, 1]}"
            ]
          },
          "metadata": {},
          "execution_count": 23
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def degree(poly):\n",
        "    while poly and poly[-1] == 0:\n",
        "        poly.pop()   # normalize\n",
        "    return len(poly)-1\n",
        "\n",
        "def congruence(n,m):\n",
        "    while ((n % p) % m) != 0:\n",
        "        n = n + p\n",
        "    return n\n",
        "\n",
        "def divide(u, v):\n",
        "    q, r = [0], u\n",
        "    divisorDeg = degree(v)\n",
        "    divisorLC = v[-1]\n",
        "\n",
        "    while degree(r) >= divisorDeg:\n",
        "        monomialExponent = degree(r) - divisorDeg\n",
        "        monomialZeros = [0 for _ in range(monomialExponent)]\n",
        "        if r[-1] % divisorLC != 0:\n",
        "            monomialDivisor = monomialZeros + [congruence(r[-1], divisorLC) // divisorLC]\n",
        "        else:\n",
        "            monomialDivisor = monomialZeros + [r[-1] // divisorLC]\n",
        "\n",
        "        q = add(q, monomialDivisor)\n",
        "        r = subtract(r, multiply(monomialDivisor, v))\n",
        "\n",
        "    return q, r"
      ],
      "metadata": {
        "id": "O1BzWSntIvfE"
      },
      "execution_count": 24,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def rem(u, v):\n",
        "    n, m = degree(u), degree(v)\n",
        "    if m < 0: raise ZeroDivisionError\n",
        "    if n >= m:\n",
        "        while n >= m:\n",
        "            d = [0] * (n - m) + v\n",
        "            if u[-1] % float(v[-1]) != 0:\n",
        "                mult = congruence(u[-1],float(v[-1])) / float(v[-1])\n",
        "            else:\n",
        "                mult = u[-1] / float(d[-1])\n",
        "            d = [(coeff * mult) % p for coeff in d]\n",
        "            u = [(coeffu - coeffd) % p for coeffu, coeffd in zip(u, d)]\n",
        "            n = degree(u)\n",
        "        r = u\n",
        "    else:\n",
        "        r = u\n",
        "    return r"
      ],
      "metadata": {
        "id": "8UZgON5MPItz"
      },
      "execution_count": 25,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def add(u, v):\n",
        "  n, m = len(u), len(v)\n",
        "  m_, ans = max(n, m), []\n",
        "  u = u + [0] * (m_ - n)\n",
        "  v = v + [0] * (m_ - m)\n",
        "  for i in range(m_):\n",
        "    ans.append((u[i] + v[i]) % p)\n",
        "  while(ans and ans[-1] == 0):\n",
        "    ans.pop()\n",
        "  if(not ans): return [0]\n",
        "  r = rem(ans, irreducible_poly)\n",
        "  return r"
      ],
      "metadata": {
        "id": "2z_mwbC1Ipwc"
      },
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#  u(x) - v(x)\n",
        "def subtract(u, v):\n",
        "  n, m = len(u), len(v)\n",
        "  m_, ans = max(n, m), []\n",
        "  u = u + [0] * (m_ - n)\n",
        "  v = v + [0] * (m_ - m)\n",
        "  for i in range(m_):\n",
        "    ans.append((u[i] - v[i]) % p)\n",
        "  while(ans and ans[-1] == 0):\n",
        "    ans.pop()\n",
        "  if(not ans): return [0]\n",
        "  r = rem(ans, irreducible_poly)\n",
        "  return r"
      ],
      "metadata": {
        "id": "3JOBedjtIrp2"
      },
      "execution_count": 27,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def multiply(u, v):\n",
        "  n, m = len(u), len(v)\n",
        "  ans = [0 for _ in range(n + m)]\n",
        "  for i in range(n):\n",
        "    for j in range(m):\n",
        "      ans[i + j] += u[i] * v[j]\n",
        "  for i in range(n + m):\n",
        "    ans[i] %= p\n",
        "  while(ans and ans[-1] == 0):\n",
        "    ans.pop()\n",
        "  if(not ans): return [0]\n",
        "  r = rem(ans, irreducible_poly)\n",
        "  return r"
      ],
      "metadata": {
        "id": "44TyeWhqIuEr"
      },
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def find_inverse():\n",
        "  d = {}\n",
        "  for ele in field_elements:\n",
        "    for ele2 in field_elements:\n",
        "      if(tuple(ele2) in d): continue\n",
        "      if(multiply(ele, ele2) == [1]):\n",
        "        d[tuple(ele)] = tuple(ele2)\n",
        "        d[tuple(ele2)] = tuple(ele)\n",
        "  return d"
      ],
      "metadata": {
        "id": "htOXy63GI25D"
      },
      "execution_count": 29,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "inverse = find_inverse()"
      ],
      "metadata": {
        "id": "UvOy5niIJIpf"
      },
      "execution_count": 30,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "inverse"
      ],
      "metadata": {
        "id": "qZeWYeERLtqH",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "d86d0789-3ab0-4885-f345-e413749af7ec"
      },
      "execution_count": 31,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{(0, 0, 0, 1): (0, 1, 1),\n",
              " (1, 0, 1, 1): (1, 1),\n",
              " (0, 1, 1): (0, 0, 0, 1),\n",
              " (0, 0, 1): (0, 0, 1, 1),\n",
              " (1, 1, 1): (1, 1, 1, 1),\n",
              " (0, 0, 1, 1): (0, 0, 1),\n",
              " (0, 1, 0, 1): (1,),\n",
              " (1,): (0, 1, 0, 1),\n",
              " (0, 1, 1, 1): (1, 0, 0, 1),\n",
              " (0, 1): (1, 0, 1),\n",
              " (1, 0, 0, 1): (0, 1, 1, 1),\n",
              " (1, 1): (1, 0, 1, 1),\n",
              " (1, 0, 1): (0, 1),\n",
              " (1, 1, 1, 1): (1, 1, 1)}"
            ]
          },
          "metadata": {},
          "execution_count": 31
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Parsing"
      ],
      "metadata": {
        "id": "DdmFUN2O44t2"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# f1 + f2 - f3 + (f4 + f5 * f8) / f6 * f7\n",
        "\n",
        "def operandStack(listNumbers: str):\n",
        "    numbers = listNumbers[1:len(listNumbers) - 1].split(',')\n",
        "    return list(map(int, numbers))\n",
        "\n",
        "def splitInputString(input: str) -> list:\n",
        "    input = input.replace(' ', '')\n",
        "    inputStack, inputOperand, index = [], [], 0\n",
        "    # Check for balanced parentheses, otherwise throw error\n",
        "    parenthesesArray = [char for char in input if char in ['(', ')']]\n",
        "    balancedStack = []\n",
        "    for element in parenthesesArray:\n",
        "        if element == '(':\n",
        "            balancedStack.append(element)\n",
        "        else:\n",
        "            if len(balancedStack) == 0:\n",
        "                print(\"Entered expression is incorrect, re-enter the expression.\")\n",
        "                return\n",
        "            else:\n",
        "                balancedStack.pop()\n",
        "    if len(balancedStack) != 0:\n",
        "        print(\"Entered expression is incorrect, re-enter the expression.\")\n",
        "        return\n",
        "\n",
        "    # Checking for balanced polynomial brackets\n",
        "    bracketsArray = [char for char in input if char in ['[', ']']]\n",
        "    balancedStack = []\n",
        "    for element in bracketsArray:\n",
        "        if element == '[':\n",
        "            balancedStack.append(element)\n",
        "            if len(balancedStack) > 1:\n",
        "                print(\"Entered expression is incorrect, re-enter the expression.\")\n",
        "                return\n",
        "        else:\n",
        "            if len(balancedStack) == 0:\n",
        "                print(\"Entered expression is incorrect, re-enter the expression.\")\n",
        "                return\n",
        "            else:\n",
        "                balancedStack.pop()\n",
        "    if len(balancedStack) != 0:\n",
        "        print(\"Entered expression is incorrect, re-enter the expression.\")\n",
        "        return\n",
        "\n",
        "    while index < len(input):\n",
        "        if input[index] in ['+', '-', '*', '/', '(', ')']:\n",
        "            inputStack.append(input[index])\n",
        "            index += 1\n",
        "        else:\n",
        "            if input[index] == '[':\n",
        "                inputOperand = []\n",
        "                closingBracket = index + input[index:].index(']')\n",
        "                inputStack.append(operandStack(input[index:closingBracket + 1]))\n",
        "                index = closingBracket + 1\n",
        "\n",
        "    # Two consecutive operators or two consecutive operands cannot be evaluated together (for example: a * + b, a b * c)\n",
        "    for index in range(0, len(inputStack) - 1, 1):\n",
        "        if inputStack[index] in ['+', '-', '*', '/'] and inputStack[index + 1] in ['+', '-', '*', '/']:\n",
        "            print(\"Entered expression is incorrect, re-enter the expression.\")\n",
        "            return\n",
        "        if isinstance(inputStack[index], list) and isinstance(inputStack[index + 1], list):\n",
        "            print(\"Entered expression is incorrect, re-enter the expression.\")\n",
        "            return\n",
        "    return inputStack"
      ],
      "metadata": {
        "id": "bI4Ztpvl45k6"
      },
      "execution_count": 32,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def parse(inputString: str):\n",
        "    tokenStack = ['('] + splitInputString(inputString) + [')']\n",
        "    positionIndex = 0\n",
        "\n",
        "    def tokenStackElement():\n",
        "        nonlocal positionIndex\n",
        "        return tokenStack[positionIndex]\n",
        "\n",
        "    def moveIndex():\n",
        "        nonlocal positionIndex\n",
        "        positionIndex += 1\n",
        "\n",
        "    def parsePrimaryExpression():\n",
        "        token = tokenStackElement()\n",
        "        # If token type is a polynomial\n",
        "        if isinstance(token, list) and positionIndex < len(tokenStack):\n",
        "            moveIndex()\n",
        "            return token\n",
        "        elif token == '(' and positionIndex < len(tokenStack):\n",
        "            moveIndex()\n",
        "            expression = parseExpression()\n",
        "            moveIndex()\n",
        "            return expression\n",
        "\n",
        "    def parseMulExpression():\n",
        "        expression = parsePrimaryExpression()\n",
        "        token = tokenStackElement()\n",
        "        while (positionIndex < len(tokenStack) and (token == '*' or token == '/')):\n",
        "            moveIndex()\n",
        "            rightHandExpression = parsePrimaryExpression()\n",
        "            expression = (token, expression, rightHandExpression)\n",
        "            token = tokenStackElement()\n",
        "        return expression\n",
        "\n",
        "    def parseExpression():\n",
        "        expression = parseMulExpression()\n",
        "        token = tokenStackElement()\n",
        "        while (positionIndex < len(tokenStack) and (token == '+' or token == '-')):\n",
        "            moveIndex()\n",
        "            rightHandExpression = parseMulExpression()\n",
        "            expression = (token, expression, rightHandExpression)\n",
        "            token = tokenStackElement()\n",
        "        return expression\n",
        "\n",
        "    result = parsePrimaryExpression()\n",
        "\n",
        "    return result"
      ],
      "metadata": {
        "id": "M6Y_79oFMIo2"
      },
      "execution_count": 33,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def evaluateExpr(expressionTuple):\n",
        "    if isinstance(expressionTuple, list):\n",
        "        return expressionTuple\n",
        "    elif isinstance(expressionTuple, tuple):\n",
        "        operator, operator1, operator2 = expressionTuple\n",
        "        if operator == '+':\n",
        "            return add(evaluateExpr(operator1), evaluateExpr(operator2))\n",
        "        elif operator == '-':\n",
        "            return subtract(evaluateExpr(operator1), evaluateExpr(operator2))\n",
        "        elif operator == '*':\n",
        "            return multiply(evaluateExpr(operator1), evaluateExpr(operator2))\n",
        "        elif operator == '/':\n",
        "            return multiply(evaluateExpr(operator1), inverse[tuple(evaluateExpr(operator2))])"
      ],
      "metadata": {
        "id": "I0bI1sf3t7uB"
      },
      "execution_count": 34,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "parse('[1, 2, 3] * [4, 5] + ([6, 7] / [7, 8] + [9, 10])')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-aB1Qygdt-Ss",
        "outputId": "e1a04148-0003-40b1-9952-80fb5dd19a88"
      },
      "execution_count": 35,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "('+', ('*', [1, 2, 3], [4, 5]), ('+', ('/', [6, 7], [7, 8]), [9, 10]))"
            ]
          },
          "metadata": {},
          "execution_count": 35
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "parse('[1, 2, 3] + ([4, 5] * [5, 7] - [8, 9])')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5vdYUj--wFVo",
        "outputId": "0e62825a-eed8-4e3f-873c-1b41fa38abab"
      },
      "execution_count": 36,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "('+', [1, 2, 3], ('-', ('*', [4, 5], [5, 7]), [8, 9]))"
            ]
          },
          "metadata": {},
          "execution_count": 36
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "e = parse('([1, 1, 1] * [1, 1]) + [1, 0, 1] / [0, 1, 1]')"
      ],
      "metadata": {
        "id": "TbzYNAfWf576"
      },
      "execution_count": 37,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "evaluateExpr(e)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XbIrtq2bvoiD",
        "outputId": "c0078f9c-e4ff-4ed3-f167-1c9baadd9119"
      },
      "execution_count": 38,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[0.0, 1.0, 1.0]"
            ]
          },
          "metadata": {},
          "execution_count": 38
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "inverse[tuple([0,1,1])]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lqRbnBRhVTKa",
        "outputId": "1cba1eb3-3960-4929-f756-5783226bfcc6"
      },
      "execution_count": 39,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(0, 0, 0, 1)"
            ]
          },
          "metadata": {},
          "execution_count": 39
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "multiply([1,1,1],[1,1])"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "_h1PskzeROrx",
        "outputId": "ec868d0d-5987-48cd-dac1-848aa54eafec"
      },
      "execution_count": 40,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[0.0, 1.0]"
            ]
          },
          "metadata": {},
          "execution_count": 40
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "JA4Ogdq6V4Jn"
      },
      "execution_count": 40,
      "outputs": []
    }
  ]
}