Insight 5 - Floating Point Representation and their Computational Issues

-
Floating-point representation

In computing, a floating-point representation is an approximation which allows modern computers to support the trade-off between range and precision when handling real numbers. Representing numbers as integers in a fixed number of bits has some notable limitations. It cannot handle numbers that have a fraction and it's not suitable for very large numbers that don't fit into (e.g.) 32 bits.
In general, a number is represented by an approximation to a fixed number of significant digits (the significant) and scaled using an exponent for some fixed base; the base for the scaling is normally two, ten, or sixteen. A number that can be represented exactly has the following form:


where significand, base, and exponent are all integers and the base is greater than or equal to two.
As an example, consider 12345 x 10-4 = 1.2345, or 11111 x 10-1 = 1111.1.
The term floating point refers to the fact that a number's radix point (decimal point or, more commonly in computer science, binary point) can "float"; that is, it can be placed anywhere relative to the significant digits of the number. This position is indicated as the exponent component and consequently the floating-point representation can be thought of as a kind of scientific notation.
One of the greater advantage of using this representation on modern systems is because it allows to represent, using just a fixed number of digits, numbers that have a very different order of magnitude.

Even though the use of the mentioned representation (and arithmetic) is vital for the performance and functioning of modern systems, it may have some issue which are typically known as catastrophic cancellation and rounding error.
A catastrophic cancellation occurs when an operation on two numbers increases the relative error (substantially) more than it increases absolute error. For instance, it occurs when subtracting two nearly equal numbers. On the other hand, a rounding error occurs when some numbers are rounded too early during a computation and/or when this is not done properly. It's the difference between a rounded-off value and the actual value.

- Catastrophic cancellation example

Consider the decimal number 0.1234567891234567890, which on a machine that keeps 10 floating-point digits it would be represented by 0.1234567891, which is fairly close when measuring the error as a percentage of the value but it's very different when measured in order of precision.
Now consider the following subtraction:

0.1234567891234567890 - 0.1234567890000000000

The answer accurate to 20 significant digits is 0.0000000001234567890 but, however, the result on the 10-digits floating-point machine yields

0.1234567891 - 0.1234567890 = 0.0000000001

In both cases the result is accurate to the same order of magnitude as the input but, in the second case, there's a cancellation of several significant digits.






- Rounding error example

As an example of rounding error, consider the speed of light in a vacuum. The official value is 299,792,458 meters per second. In scientific notation (power 10), that quantity is expressed as 2.299792458 x 108and rounding it to three decimal places yields 2.998 x 108. The rounding error is the difference between the actual value and the rounded value, in this case it's equal to 0.00007542 x 108. In scientific notation, the rounding error is 7.542 x 103, which is equals to 7452 in plain decimal notation.


Commenti

Posta un commento

Post popolari in questo blog

Welford Algorithm

-
Immagine
The variance is the expectation of the squared deviation of a random variable form its mean.  Informally, it measures how far a set of (random) numbers are spread out from their average value. The variance is the square of the standard deviation, the second central moment of a distribution and the covariance of the random variable with itself, and it is often represented by Var(X), σ 2 , s 2 . One of the most widely known formula for computing the variance is: where x-bar is the mean of the sample. The definition given above can be converted into an algorithm that computed the variance and the standard deviation in two passes: 1. Compute the mean                            (O(n)) 2. Compute the square differences       (O(n)) Output the variance Even though this algorithm seems working properly, it may become too expensive on some input instances. Just consider a sampling procedu...
Continua a leggere

Research 6 - Derivation of Chebyshev's inequality and its application to prove the (weak) LLN

-
Immagine
Chebyshev's Inequality In probability theory, the Chebyshev's inequality guarantees that, for a wide class of probability distributions, no more than a certain fraction of values can be more distant than a certain value from the mean. In particular, the mentioned inequality states that no more than 1/k 2 of the distribution's values can be more than k standard deviations away from the mean. In other words, this mean that at least (1 - 1/k 2 ) of the distribution's values are within k standard deviations of the mean. The Chebyshev's inequality can be easily derived from the Markov's inequality, where the latter defines an upper bound for the probability that a non-negative random variable is greater than (or equal to) some positive integer constant. Remember the Markov's inequality where   a  > 0 and  X  is a nonnegative random variable The Chebyshev inequality follows by considering the random variable ( X - E ( X )) 2  and the constant a 2...
Continua a leggere

Research 7 -- Central Limit Theorem, LLN, and most common probability distributions

-
Immagine
Law of Large Numbers and CLT Intuitively, everyone can be convinced of the fact that the average of many measurements of the same unknown quantity tends to give a better estimate than a single measurement. The law of the large numbers (LLN) and the central limit theorem (CLT) formalise this general ideas through mathematics and random variables. Suppose X 1 , X 2 , ..., X n are independent random variables with the same underlying distribution. In this case, we say that the X i are independent and identically-distributed (or, i.i.d.). In particular, the X i have all the same mean μ and standard deviation σ. The average of the i.i.d. variables is defined as: The central limit theorem states that when an infinite number of successive random samples are taken from a population, the sampling distribution of the means of those samples will become approximately normally distributed with mean μ and standard deviation σ/ √N as the sample size becomes larger, irrespective of the sh...
Continua a leggere