Number representation

Besides of the concrete names of Julia library functions everything in this chapter is valid for all modern programming languagues and computer systems.

All data in computers are stored as sequences of bits. For concrete number types, the bitstring function returns this information as a sequence of 0 and 1. The sizeof function returns the number of bytes in the binary representation.

Integer numbers

Positive integer numbers are represented by their representation in the binary system. For negative numbers $n$, the binary representation of their "two's complement" $2^N-|n|$ (where $N$ is the number of available bits) is stored.

typemin and typemax return the smallest and largest numbers which can be represented in number type.

Unless the possible range of the representation $(-2^{N-1},2^{N-1})$ is exceeded, addition, multiplication and subtraction of integers are exact. If it is exceeded, operation results wrap around into the opposite sign region.

Floating point numbers

How does this work for floating point numbers ?

But this should be 0.3. What is happening ???

Real number representation

• Let us think about representation real numbers. Usually we write them as decimal fractions and cut the representation off if the number of digits is infinite.

• Any real number $x\in \mathbb{R}$ can be expressed via the representation formula: $x=\pm \sum _{i=0}^{\mathrm{\infty }}{d}_i{\beta }^{-i}{\beta }^e$ with base $\beta \in \mathbb{N},\beta \ge 2$, significand (or mantissa) digits $d_i\in \mathbb{N},0\le d_i<\beta$ and exponent $e\in \mathbb{Z}$

• The representation is infinite for periodic decimal numbers and irrational numbers.

Scientific notation

The scientific notation of real numbers is derived from this representation in the case of $\beta =10$. Let e.g. $x=6.022\cdot {10}^{23}$=6.022e23. Then

• $\beta =10$

• $d=(6,0,2,2,0\dots )$

• $e=23$

This representation is not unique, e.g. $x_1=0.6022\cdot {10}^{24}$=0.6022e24$=x$ with

• $\beta =10$

• $d=(0,6,0,2,2,0\dots )$

• $e=24$

IEEE754 standard

This is the actual standard format for storing floating point numbers. It was developed in the 1980ies.

• $\beta =2$, therefore $d_i\in \{0,1\}$

• Truncation to fixed finite size: $x=\pm \sum _{i=0}^{t-1}{d}_i{\beta }^{-i}{\beta }^e$

• $t$ : significand (mantissa) length

• Normalization: assume $d_0=1\Rightarrow$ save one bit for the storage of the significand. This requires a normalization step after operations which adjusts significand and exponent of the result.

• $k$: exponent size. Define $L,K$: $-{\beta }^k+1=L\le e\le U={\beta }^k-1$

• Extra bit for sign

• $\Rightarrow$ storage size: $(t-1)+k+1$

• Standardized for most modern languages

• Hardware support usually for 64bit and 32bit

precision	Julia	C/C++	k	t	bits
quadruple	n/a	long double	16	113	128
double	Float64	double	11	53	64
single	Float32	float	8	24	32
half	Float16	n/a	5	11	16

• See also the Julia Documentation on floating point numbers, 0.30000000000000004.com, wikipedia and the links therein.

The storage sequence is: Sign bit, exponent, mantissa.

Storage layout for a normalized Float32 number ($d_0=1$):

• bit 1: sign, $0\to +,1\to -$

• bit $2\dots 9$: $k=8$ exponent bits

  • the value $e+2^{k-1}-1=e+127$ is stored $\Rightarrow$ no need for sign bit in exponent

• bit $10\dots 32$: $23=t-1$ mantissa bits $d_1\dots d_{23}$

• $d_0=1$ not stored $\equiv$ "hidden bit"

Julia allows to obtain the signifcand and the exponent of a floating point number

• We can calculate the length of the exponent $k$ from the maximum representable floating point number by taking the base-2 logarithm of its exponent:

• The size of the significand $t$ is calculated from the overall size of the representation minus the size of the exponent and the size of the sign bit + 1 for the "hidden bit".

This allows to define a more readable variant of the bitstring repredentatio for floats.

• The sign bit is the first bit in the representation:

• Next comes the exponent:

• And finally, the significand:

• Put them together:

Julia floating point types

Type Float16:

• size of exponent: 5

• size of significand: 11

• Binary representation: 0_01011_1001100110

• Exponent e=-4

• Stored: e+15= 11

• $d_0=1$ assumed implicitely.

• Numbers which are exactly represented in decimal system may not be exactly represented in binary system!

• Such numbers are always rounded to a finite approximate

Floating point limits

• Finite size of representation $\Rightarrow$ there are minimal and maximal possible numbers which can be represented

• symmetry wrt. 0 because of sign bit

• smallest positive denormalized number: $d_i=0,i=0\dots t-2,d_{t-1}=1$ $\Rightarrow$ $x_{min}=2^{1-t}{2}^L$

• smallest positive normalized number: $d_0=1,d_i=0,i=1\dots t-1$ $\Rightarrow$ $x_{min}=2^L$

• largest positive normalized number: $d_i=1,0\dots t-1$ $\Rightarrow$ $x_{max}=2(1-2^{1-t})2^U$

• Largest representable number:

Machine precision

• There cannot be more than $2^{t+k}$ floating point numbers $\Rightarrow$ almost all real numbers have to be approximated

• Let $x$ be an exact value and $\tilde{x}$ be its approximation. Then $|\frac{\tilde{x}-x}{x}|<ϵ$ is the best accuracy estimate we can get, where

  • $ϵ=2^{1-t}$ (truncation)

  • $ϵ=\frac{1}{2}{2}^{1-t}$ (rounding)

• Also: $ϵ$ is the smallest representable number such that $1+ϵ>1$.

• Relative errors show up in particular when

  • subtracting two close numbers

  • adding smaller numbers to larger ones

How do operations work?

E.g. Addition

• Adjust exponent of number to be added:

  • Until both exponents are equal, add 1 to exponent, shift mantissa to right bit by bit

• Add both numbers

• Normalize result

The smallest number one can add to 1 can have at most $t$ bit shifts of normalized mantissa until mantissa becomes 0, so its value must be $2^{-t}$.

Machine epsilon

• Smallest floating point number $ϵ$ such that $1+ϵ>1$ in floating point arithmetic

• In exact math it is true that from $1+\epsilon =1$ it follows that $0+\epsilon =0$ and vice versa. In floating point computations this is not true

Density of floating point numbers

How dense are floating point numbers on the real axis?