Hefty Number Principles.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p align=\"center\">\n",
    "  <img src=\"hn_logo.png\">\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## About Hefty Number\n",
    "Hefty Number is a python library built upon Numpy for doing arithmetic in arbitrary bases with arbitrary precision."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "import sympy as sp\n",
    "\n",
    "sp.init_printing(order='rev-lex',use_latex='mathjax')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Numbers\n",
    "Our modern positional number system can be described as a polynomial. \n",
    "\n",
    "$$\n",
    "\\large{\\begin{align}\n",
    "a_{n-1}b^{n-1} + a_{n-2}b^{n-2} \\ldots a_{1}b^{1} + a_{0}b^{0} \\tag{1}\n",
    "\\end{align}}\n",
    "$$\n",
    "\n",
    "Where:\n",
    "* $a$ is a vector of coeficients representing the digits of a number and \n",
    "* $b$ is the base of the number in base 10. \n",
    "* $n$ is the legth of the number.\n",
    "\n",
    "We can introduce the notion of a base vector to achieve an easier to work with linear form. If $a_n$ is our vector of coeficients and b is the base of the number then:\n",
    "\n",
    "$$ \n",
    "\\large\n",
    "\\dot{a} = [b^{n-1},b^{n-2},\\ldots,b^{1},b^{0}] \\tag{2}\n",
    "$$\n",
    "\n",
    "Given this notation we get the equivalent forms: "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\large{\\begin{align}\n",
    "a_{n-1}b^{n-1} + a_{n-2}b^{n-2} \\ldots a_{1}b^{1} + a_{0}b^{0} =  \\\\\n",
    "a_{n-1}\\dot{a}_{n-1} + a_{n-2}\\dot{a}_{n-2} \\ldots a_{1}\\dot{a}_{1} + a_{0}\\dot{a}_{0} = \\sum_{i=0}^{n-1}{a_i}{\\dot{a}_i} = \\\\\n",
    "a\\cdot\\dot{a}^\\intercal\n",
    "\\end{align}}\n",
    "$$\n",
    "\n",
    "Where:\n",
    "* $a$ is a vector of coeficients representing the digits of a number and \n",
    "* $b$ is the base of the number. \n",
    "* $\\dot{a}$ is the base vector\n",
    "\n",
    "Converting from base is a simple matter of multiplying the coeficients of the number by its base vector transposed. $a\\cdot\\dot{a}^\\intercal$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Arithmetic\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Multiplication "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Multiplication is built upon the primitive addition operation. Any multiplication algorithm converts its opperands to a series of additions. Consider the multiplication of $425 * 323$. The naive approach is to add one of the opperands as many times as the other one. We could list $425$ to the count of $323$ and then add the list. This is inneficient in terms of the number of operations performed. The more efficient approach, long multiplication, is taught in grade school. \n",
    "\n",
    "Let's think about what's going on when perform $425 * 323$ in respect to how these numbers are composed in the positional number system. We define a function that allows us to convert base 10 numbers into a vector representing the decomposition of the numbers: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [],
   "source": [
    "def b10ToUnitVect(b10Num):\n",
    "    rollingSum = 0 \n",
    "    ls = []\n",
    "    for i in range(1,len(str(b10Num))+1):\n",
    "        res = b10Num % 10**i\n",
    "        m   = res - rollingSum\n",
    "        ls = [m] + ls\n",
    "        rollingSum += m\n",
    "        \n",
    "    return np.matrix(ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[400  20   5]]\n",
      "[[300  20   3]]\n"
     ]
    }
   ],
   "source": [
    "a = b10ToUnitVect(425)\n",
    "b = b10ToUnitVect(323)\n",
    "\n",
    "print(a)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Multiplying the two numbers corresponds to multipying each element in one vector with every element of the other. This always produces a square matrix of numbers to be added. We can perform this enumeration by performing row vector by column vector dot product. As follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1200000,   80000,   12000],\n",
       "        [  60000,    4000,     600],\n",
       "        [  15000,    1000,     150],\n",
       "        [    900,      60,       9]])"
      ]
     },
     "execution_count": 150,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.T*b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[120000,   8000,   1200,   6000,    400,     60,   1500,    100,\n",
       "             15]])"
      ]
     },
     "execution_count": 131,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(a.T*b).flatten()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "print(425*323 == int((a.T*b).flatten().sum()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1200000000000,   80000000000,   12000000000],\n",
       "        [  90000000000,    6000000000,     900000000],\n",
       "        [   6000000000,     400000000,      60000000],\n",
       "        [   2700000000,     180000000,      27000000],\n",
       "        [    120000000,       8000000,       1200000],\n",
       "        [            0,             0,             0],\n",
       "        [       600000,         40000,          6000],\n",
       "        [        30000,          2000,           300],\n",
       "        [            0,             0,             0],\n",
       "        [         1500,           100,            15]], dtype=int64)"
      ]
     },
     "execution_count": 143,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = b10ToUnitVect(4329402105)\n",
    "a.T*b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1200000,   80000,   12000],\n",
       "        [  60000,    4000,     600],\n",
       "        [  15000,    1000,     150],\n",
       "        [    900,      60,       9]])"
      ]
     },
     "execution_count": 147,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = b10ToUnitVect(4253)\n",
    "b = b10ToUnitVect(323)\n",
    "\n",
    "a.T*b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$3.0$$"
      ],
      "text/plain": [
       "3.0"
      ]
     },
     "execution_count": 161,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.log10(1000)/np.log10(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "137275"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "5*3+5*20+5*300+20*3+20*20+20*300+400*3+400*20+400*300"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 235,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 235,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k = np.divide(np.log(1000),np.log(10))\n",
    "# k is numpy.float64 with the value\"3.0\" \n",
    "\n",
    "z = k\n",
    "k == \"3.0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$12.8$$"
      ],
      "text/plain": [
       "12.8"
      ]
     },
     "execution_count": 221,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$60$$"
      ],
      "text/plain": [
       "60"
      ]
     },
     "execution_count": 222,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "12*5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$1.4375$$"
      ],
      "text/plain": [
       "1.4375"
      ]
     },
     "execution_count": 226,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "23/16"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Where a >= 1 and arg min is an non-negative integer. \n",
    "\n",
    "$$\\large{\\begin{align}\n",
    "\\underset{a \\ b \\ c}{\\operatorname{arg \\ min}}\\ 23-4^2a-4^1b-4^0c\\\\\n",
    "\\underset{a}{\\operatorname{arg \\ min}}\\ 23-4^2a = a \\\\\n",
    "\\underset{b}{\\operatorname{arg \\ min}}\\ 23-4^2a-4^1b = b \\\\\n",
    "\\underset{c}{\\operatorname{arg \\ min}}\\ 23-4^2b-4^1b-4^0c = c \\\\\n",
    "\\end{align}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Non-vector case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 2  3 10  7 16  1  0 18  5  8 11 19 13  0  8  0  3 16  4  5  3  0 19 19 11\n",
      "  3  9 14 16  9 13  2 14  8  3  1  7 18 13 15 16  7 13  2 13  0 12 16  4  7\n",
      " 16  5 19 15 17  8 10  3 16 19 10 12 17 18  2  1 13 19 13 16 13  3  4 10  0\n",
      "  5  1  3  0  3 15 15 16  1 13  8  2  5 11 13 10 10  3 11 19  0 12  3 17 14\n",
      "  5 11  1 17  9 11 12 13  4 13  0 11 10 17  7  2  8  6 16  3 18 14  5 10  2\n",
      " 12 10 16  4  7 17 12  4 16 14  3 13  2  5 19 10 11  3  0  3  2 11 16  8 19\n",
      "  5  5  6 14 12 18  5 18 13  9 19 18 10  8 17 17 11  3 11  7  1  3  2 12 19\n",
      " 13 17 14 14 12 17  8  6 14 16 19 18  3 16 14  2 19  3 13  2  1  5  4  2 10\n",
      " 13 14  2 16  9  1 11  4 13  5 19  5  2 12 11  9 19  8 11  5 11  0 17 13 17\n",
      "  9  9  8  7 19  4 13 15  3  9 18 10  7 14  0  2  5 15 11 16 11  2  6 16 12\n",
      "  7 17]\n",
      "[[ 787377278800261375797310609626570169255923439036910297102455296922779142265402741036829965897731387072437550921294373519676860926877849046796053515656186390238191719866517824579364401567959339626467440107729622759612596819782635071948294923475127692380421387128460609278029340193136528647715203699828982676533576148782791492957]]\n"
     ]
    }
   ],
   "source": [
    "def argmin_s(x,base,power) -> \"[min,arg_min]\": \n",
    "    \n",
    "    minVal,lastMinVal = 1,1\n",
    "    fundamental       = base**power\n",
    "    \n",
    "    for i in range(0,base):\n",
    "        minVal = x - fundamental * i\n",
    "    \n",
    "        if(minVal < 0):\n",
    "            return [lastMinVal,i-1]\n",
    "        if(minVal == 0):\n",
    "            return [minVal,i]\n",
    "        \n",
    "        lastMinVal = minVal\n",
    "        \n",
    "    return [minVal,i]\n",
    "\n",
    "\n",
    "def b10bn(b10Num,base)->\"ndarry\":\n",
    "    if(base == 1):\n",
    "        return np.ones(b10Num)\n",
    "    \n",
    "    logNum = math.log(b10Num,base)\n",
    "    num    = []\n",
    "    \n",
    "    if logNum == 1:\n",
    "        nDigits=2\n",
    "    else:\n",
    "        nDigits = math.ceil(logNum)\n",
    "        \n",
    "    for i in range(nDigits-1,0,-1):\n",
    "        b10Num,idx = argmin_s(b10Num,base,i)\n",
    "        num.append(idx)\n",
    "        \n",
    "    num.append(b10Num)\n",
    "    \n",
    "    return np.array(num)\n",
    "\n",
    "def powerVect(base,n):\n",
    "    num = [1]\n",
    "    \n",
    "    if n == 1:\n",
    "        return np.array(num)\n",
    "    else:   \n",
    "        r = 1\n",
    "        for i in range(n):\n",
    "            r = base*r\n",
    "            num = [r] + num\n",
    "            \n",
    "        return np.matrix(num)\n",
    "    \n",
    "def vectToB10(vect,base):\n",
    "    rVect = powerVect(base,vect.shape[0]-1)\n",
    "    return vect*rVect.T\n",
    "    \n",
    "a = 9234094032940239493043829839823238928382938329823982389328923898238329832983239823982389232989838938928393893**3\n",
    "b = b10bn(a,20)\n",
    "print(b)\n",
    "print(vectToB10(b,20))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "752.7062776521827"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "math.log(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    ""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3.0
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}