View source for Representation of Numbers in the Computer

Questions to [mailto:davrot@uni-bremen.de David Rotermund]

''By Jan Wiersig, modified by Udo Ernst and translated into English by Daniel Harnack. David Rotermund replaced the Matlab code with Python code.''

== Bits and Bytes ==
In digital computers, information is represented by discrete states of circuit elements. The smallest possible unit of information is one bit (binary digit). It can be in two different states, that may be described differently:
{| class="wikitable"
|true
| style="text-align: center;" |<math display="inline">\longleftrightarrow</math>
| style="text-align: center;" |false
|-
|yes
| style="text-align: center;" |<math display="inline">\longleftrightarrow</math>
| style="text-align: center;" |no
|-
|1
| style="text-align: center;" |<math display="inline">\longleftrightarrow</math>
| style="text-align: center;" |0
|-
|
| style="text-align: center;" |<math display="inline">\vdots</math>
| style="text-align: center;" |
|}
A bit is easily realized physically:
{| class="wikitable"
|current flowing
| style="text-align: center;" |<math display="inline">\longleftrightarrow</math>
| style="text-align: center;" |current not flowing
|-
|voltage there
| style="text-align: center;" |<math display="inline">\longleftrightarrow</math>
| style="text-align: center;" |voltage gone
|-
|magnetized
| style="text-align: center;" |<math display="inline">\longleftrightarrow</math>
| style="text-align: center;" |not magnetized
|-
|
| style="text-align: center;" |<math display="inline">\vdots</math>
| style="text-align: center;" |
|}
For example, in the communication between integrated circuits, information is traded via changes in voltage, while the bits on the hard disk are written by magnetization of ferromagnetic materials. Between electronic musical instruments, bits are exchanged through current loops (MIDI-Standard). In the stone age of computers, the fifties, bits were even once realized as air bubbles in a liquid medium.

By combining several bits, complex information like numbers, letters (e.g. 8 bit-ASCII-code), images, color, music, etc, can be represented. Much like in the decimal system, where whole numbers are made up of the digits 0-9, the same numbers can be written in the so called dual system by sequences of 0 and 1:
{| class="wikitable"
!dual system
! style="text-align: center;" |decimal system
|-
|000
| style="text-align: center;" |0
|-
|001
| style="text-align: center;" |1
|-
|010
| style="text-align: center;" |2
|-
|011
| style="text-align: center;" |3
|-
|100
| style="text-align: center;" |4
|-
|101
| style="text-align: center;" |5
|-
|110
| style="text-align: center;" |6
|-
|111
| style="text-align: center;" |7
|-
|<math display="inline">\vdots</math>
| style="text-align: center;" |<math display="inline">\vdots</math>
|}
Two further examples for 8-bit numbers:

01010101 <math display="inline">=1 \star 2^0+0 \star 2^1+1 \star 2^2+0 \star 2^3 +1 \star 2^4+0 \star 2^5+1 \star 2^6+0 \star 2^7 = 85</math>

10101010 <math display="inline">=0 \star 2^0+1 \star 2^1+0 \star 2^2+1 \star 2^3 +0 \star 2^4+1 \star 2^5+0 \star 2^6+1 \star 2^7 = 170</math>

To represent negative numbers, a small trick is necessary: one specific bit codes for the sign of the number. In an <math display="inline">n</math>-bit number, one would for example reserve the <math display="inline">n</math>-th it for the sign, and the remaining <math display="inline">n-1</math> bits code, as usual, a binary number <math display="inline">z</math>: If the <math display="inline">n</math>-th bit is not set, then the result is by default <math display="inline">+z</math>. If the <math display="inline">n</math>-th bit is set, the result is <math display="inline">-(2^{n-1})+z</math>. For illustration, again a small table:
{| class="wikitable"
!dual system
! style="text-align: center;" |decimal system
|-
|01111111
| style="text-align: center;" | +127
|-
|01111110
| style="text-align: center;" | +126
|-
|<math display="inline">\vdots</math>
| style="text-align: center;" |<math display="inline">\vdots</math>
|-
|00000010
| style="text-align: center;" | +2
|-
|00000001
| style="text-align: center;" | +1
|-
|00000000
| style="text-align: center;" | +0
|-
|11111111
| style="text-align: center;" | -1
|-
|11111110
| style="text-align: center;" | -2
|-
|<math display="inline">\vdots</math>
| style="text-align: center;" |<math display="inline">\vdots</math>
|-
|10000010
| style="text-align: center;" | -126
|-
|10000001
| style="text-align: center;" | -127
|-
|10000000
| style="text-align: center;" | -128
|}
Certain bit lengths have names:
{| class="wikitable"
|1 Byte
| style="text-align: center;" |8 Bit
|-
|1 Word
| style="text-align: center;" |16 Bit
|-
|1 Kilobyte
| style="text-align: center;" |1024 Byte
|-
|1 Megabyte
| style="text-align: center;" |1024 Kilobyte
|-
|1 Gigabyte
| style="text-align: center;" |1024 Megabyte
|-
|1 Terabyte
| style="text-align: center;" |1024 Gigabyte
|}

== Representation of Real Numbers and Numerical Errors ==
Real numbers are, by their nature, analogue quantities. Hence we would expect the handling of these numbers on digital computers not to be completely problem-free. Present digital computers usually represent real numbers as floating-point numbers.

floating-point number = mantissa ⋅ basis <sup>exponent</sup>

Thereby, the precision, with which the real number can be represented, is determined by the number of available bits.”Simple precision” (i.e. float32) requires 4 Bytes, for ''double precision'' (i.e. float64) 8~Bytes are needed. The latter is the default configuration in Python and Matlab. The IEEE format of double precision uses 53-Bits for the mantissa, 11-Bits for the exponent and for the basis the remaining 2. One Bit of the mantissa respectively the exponent are used for the sign of the quantity. Thus, the exponent can vary between<math display="inline">-1024</math> and <math display="inline">+1023</math>. The mantissa always represents a value in the interval <math display="inline">[1, 2[</math> in the IEEE notation. Here, the <math display="inline">52</math> Bits are utilized to add up fractions of exponents of 2. The value of the mantissa yields <math display="inline">mantissa = 1 + \sum_{i=1}^{52} b_i 2^{-i}</math>, with <math display="inline">b_i=1</math> , if the <math display="inline">i</math>-th bit in the mantissa is set.

== Range Error ==
The maximal range of the floating-point numbers is determined by the number of bits used to code for the exponent. A typical number for single precision is

<math display="inline">2^{\pm 127} \approx 10^{\pm 38}</math>

and for double precision

<math>2^{\pm 1023} \approx 10^{\pm 308}</math>

Via application of arithmetic operations on these numbers, the range can be exceeded. The error occurring in that case is named a range error. As an example we consider the Bohr radius in SI units

<math>a_0 = \frac{4\pi\varepsilon_0\hbar^2}{m_ee^2}\approx 5.3\times 10^{-11} \mbox{m}</math>

The quantity <math display="inline">\hbar</math> is Planck’s quantum of action divided by <math display="inline">2\pi</math>. Bohr’s radius is in the range of single precision floating-point numbers. However, the same does not hold for the numerator <math display="inline">4\pi\varepsilon_0\hbar^2 \approx 1.24\cdot 10^{-78}\mbox{KgC}^2\mbox{m}</math> and the denominator <math display="inline">m_ee^2 \approx 2.34\times 10^{-68}\mbox{KgC}^2</math>. I.e. neither the numerator nor the denominator can be represented as a single precision floating-point number. Hence, the calculation of Bohr’s radius by the given formula can be problematic. A simple solution of this problem lies in the use of natural units, such as Bohr’s radius, for distances, etc.

An even bigger problem can be illustrated by the calculation of the factorial. The factorial is defined as

<math>n! = n\cdot(n-1)\cdot(n-2)\cdot\ldots3\cdot 2\cdot 1</math>

In Python or Matlab, it can be easily verified by using the function factorial(n), that the factorial for <math display="inline">n>170</math> can not be represented, even with double precision numbers. A way out is provided by the use of logarithms, since the logarithm of a bigger number still gives moderately small values, e.g. <math display="inline">\log_{10}(10^{100}) = 100</math>. It ensues that

<math>\ln(n!) = \ln(n) + \ln(n-1) + \ldots + \ln(3) + \ln(2) + \ln(1)</math>

For bigger <math display="inline">n</math>, the evaluation of this expression is, however, to laborious. If <math display="inline">n>30</math>, one is advised to use Stirling’s formula

<math>\ln(n!) = n\ln(n)-n+\frac{1}{2}\ln(2\pi n)+\ln\left(1+\frac{1}{12n}+\frac{1}{288n^2}+\ldots\right)</math>

The factorial <math display="inline">n!</math> can than be written as the following

<math>n! = \mbox{mantissa}\times 10^{\mbox{exponent}}</math>

To get the mantissa and the exponent, we form the logarithm to the basis 10 (reminder: <math display="inline">\log_{10}(x) = \ln(x)/\ln(10)</math>)

<math>\log_{10}(n!) = \log_{10}(\mbox{mantissa})+{\mbox{exponent}}</math>

We now associate the integer part of <math display="inline">\log_{10}(n!)</math> with the exponent. The post-decimal places are associated with the mantissa, i.e. mantissa = <math display="inline">10^a</math> with <math display="inline">a = \log_{10}(n!)-\mbox{exponent}</math>. 

From these examples we learn that range errors can usually be circumvented with a little creativity.

== Rounding Error ==
Rounding errors stem from the finite precision of the mantissa. The following program illustrates this fact:<syntaxhighlight lang="python">x: float = 1.0

while 1 + x != 1:
    x = x / 2

x = x * 2
print(x) # -> 2.220446049250313e-16</syntaxhighlight>One might think that this constitutes an infinite loop. To the contrary, the loop will be left in finite time. The result for double precision is <math display="inline">x \approx 2\times 10^{-16}</math> <syntaxhighlight lang="python3">
import sys
print(sys.float_info.epsilon)
</syntaxhighlight>eps is the smallest number with <math display="inline">1+\epsilon > 1</math>  

, and is the . Rounding errors of this order of magnitude occur on a regular basis. For example, Python calculates <math display="inline">\sin{\pi} \approx 1.2246\times 10^{-16}</math> <syntaxhighlight lang="python3">
import math
print(math.sin(math.pi))
</syntaxhighlight>It shall be mentioned hat the machine accuracy for double precision is exactly  <math display="inline">\epsilon= 2^{-52}</math>, since 52 bits (plus one bit for the sign) are used for the mantissa. This rounding error might appear to be small and negligible. However, if further calculations are performed with rounded numbers, the rounding errors can accumulate with each calculation and grow to a significant value.