{
"metadata": {
"name": ""
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"ESE - Numerical Methods I: Basics of Computer Arithmetic - Examples"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Integers"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"1. Express the number `140` as a binary (base 2) sequence (manually)! How many bits do you need?\n",
"2. Express the number `16` as a binary (base 2) sequence (use `'{0:b}'.format(16)`)! How many bits do you need?\n",
"3. Add `140` and `16` in binary (manually)!\n",
"4. Using 8 bits (no sign bit) to represent `140`, what would be the largest number you can add without causing overflow?\n",
"4. Subtract `16` from `120` in binary!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Express the number `140` as a binary (base 2) sequence! How many bits do you need?**\n",
"\n",
"as a reminder (8 bit):\n",
"\n",
"\n",
"\n",
"| $2^7$ | \n",
"$2^6$ | \n",
"$2^5$ | \n",
"$2^4$ | \n",
"$2^3$ | \n",
"$2^2$ | \n",
"$2^1$ | \n",
"$2^0$ | \n",
"
\n",
"\n",
"| $0$ | \n",
"$0$ | \n",
"$0$ | \n",
"$0$ | \n",
"$0$ | \n",
"$0$ | \n",
"$0$ | \n",
"$0$ | \n",
"
\n",
"
\n",
"\n",
"Let's see if 8 bit (largest factor = $2^7$) is enough:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print 140/2**8"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
}
],
"prompt_number": 17
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"so we know that an 8 bit representation suffices. Now let's split `140` in base two components:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print 140/2**7\n",
"print 140%2**7"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n",
"12\n"
]
}
],
"prompt_number": 18
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print 12/2**6\n",
"print 12%2**6"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n",
"12\n"
]
}
],
"prompt_number": 19
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print 12/2**5\n",
"print 12%2**5"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n",
"12\n"
]
}
],
"prompt_number": 20
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print 12/2**4\n",
"print 12%2**4"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n",
"12\n"
]
}
],
"prompt_number": 21
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print 12/2**3\n",
"print 12%2**3"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n",
"4\n"
]
}
],
"prompt_number": 22
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print 4/2**2\n",
"print 4%2**2"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n",
"0\n"
]
}
],
"prompt_number": 23
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"so that our result is:\n",
"\n",
"\n",
"\n",
"| $2^7$ | \n",
"$2^6$ | \n",
"$2^5$ | \n",
"$2^4$ | \n",
"$2^3$ | \n",
"$2^2$ | \n",
"$2^1$ | \n",
"$2^0$ | \n",
"
\n",
"\n",
"| $1$ | \n",
"$0$ | \n",
"$0$ | \n",
"$0$ | \n",
"$1$ | \n",
"$1$ | \n",
"$0$ | \n",
"$0$ | \n",
"
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Express the number `16` as a binary (base 2) sequence! How many bits do you need?**\n",
"\n",
"Python has a built-in formatter for this purpose:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# meaning: take the 0th value from within the parenthesis and format it as 'b', which stands for binary\n",
"'{0:b}'.format(16)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 24,
"text": [
"'10000'"
]
}
],
"prompt_number": 24
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Add `140` and `16` in binary!**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"| $1$ | \n",
"$0$ | \n",
"$0$ | \n",
"$0$ | \n",
"$1$ | \n",
"$1$ | \n",
"$0$ | \n",
"$0$ | \n",
"
\n",
"\n",
"| $0$ | \n",
"$0$ | \n",
"$0$ | \n",
"$1$ | \n",
"$0$ | \n",
"$0$ | \n",
"$0$ | \n",
"$0$ | \n",
"
\n",
"\n",
"| $1$ | \n",
"$0$ | \n",
"$0$ | \n",
"$1$ | \n",
"$1$ | \n",
"$1$ | \n",
"$0$ | \n",
"$0$ | \n",
"
\n",
"
\n",
"\n",
"so that"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print 1*2**7 + 0*2**6 + 0*2**5 + 1*2**4 + 1*2**3 + 1*2**2 + 0*2**1 + 0*2**0\n",
"# and to check\n",
"\"{0:b}\".format(156)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"156\n"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 25,
"text": [
"'10011100'"
]
}
],
"prompt_number": 25
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Using 8 bits (no sign bit) to represent `140`, what would be the largest number you can add without causing overflow?**\n",
"\n",
"we can check that manually"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print 1*2**7 + 1*2**6 + 1*2**5 + 1*2**4 + 1*2**3 + 1*2**2 + 1*2**1 + 1*2**0"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"255\n"
]
}
],
"prompt_number": 26
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"or here under `uint8`, for unsigned integers. The largest number we can add is therefore `155` to yield:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"\"{0:b}\".format(255)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 27,
"text": [
"'11111111'"
]
}
],
"prompt_number": 27
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Subtract 16 from 120 in binary!**\n",
"\n",
"We know that"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"'{0:b}'.format(120)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 28,
"text": [
"'1111000'"
]
}
],
"prompt_number": 28
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"and"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"'{0:b}'.format(16)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 29,
"text": [
"'10000'"
]
}
],
"prompt_number": 29
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Subtraction is implemented as assition of the negative number; to get the negativ representation of an integer we invert all bits and add `1`:\n",
"\n",
"```\n",
"16 = 00010000\n",
"\n",
"-16 = 11101111 + 00000001 = 11110000\n",
"```\n",
"\n",
"\n",
"\n",
"| $0$ | \n",
"$1$ | \n",
"$1$ | \n",
"$1$ | \n",
"$1$ | \n",
"$0$ | \n",
"$0$ | \n",
"$0$ | \n",
"
\n",
"\n",
"| $1$ | \n",
"$1$ | \n",
"$1$ | \n",
"$1$ | \n",
"$0$ | \n",
"$0$ | \n",
"$0$ | \n",
"$0$ | \n",
"
\n",
"\n",
"| $0$ | \n",
"$1$ | \n",
"$1$ | \n",
"$0$ | \n",
"$1$ | \n",
"$0$ | \n",
"$0$ | \n",
"$0$ | \n",
"
\n",
"
\n",
"\n",
"\n",
"which we can check (since we now have a sign bit the maximum power reduces from 7 to 6):"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print 1*2**6 + 1*2**5 + 0*2**4 + 1*2**3 + 0*2**2 + 0*2**1 + 0*2**0"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"104\n"
]
}
],
"prompt_number": 30
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Floating Points"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![](\"files/img/float_to_binary.png\")
\n",
"\n",
"1. Convert the number `75.75` to binary (single-precision)!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The integer part is straightforward:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"'{0:b}'.format(75)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 1,
"text": [
"'1001011'"
]
}
],
"prompt_number": 1
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The fraction is a sum of $2^{-1} + 2^{-2} + 2^{-3} + 2^{-4} + 2^{-5} $ so for `0.75` we find `11` so that $2^{-1} + 2^{-2} = 0.75 = 0.5 + 0.25$\n",
"\n",
"so that our number in binary becomes\n",
"\n",
"`1001011.11`\n",
"\n",
"we move the floating point up **six** places.\n",
"\n",
"`1.00101111`\n",
"\n",
"So we find our exponent as"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"'{0:b}'.format(6+127)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 2,
"text": [
"'10000101'"
]
}
],
"prompt_number": 2
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"and our fraction as (only the part after the leading `1`): \n",
"\n",
"`00101111`\n",
"\n",
"to yield, with `0` as sign bit for a positive number\n",
"\n",
"`0 10000101 00101111000000000000000`"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}