Integer number formats cannot store fractional values. We can get around this using a fixed point format, but this severely limits both the range and the number of fractional digits. A 64-bit fixed point system with 32 whole number digits and 32 fractional digits has a maximum range of 2³² - 1 even when we don't need the fractional bits. A system that utilizes all the bits where they are needed would generally be a better option for approximating real numbers.

Floating point gets around the limitations of fixed point by using a format similar to scientific notation.

3.52 * 10³ = 3520

A scientific notation number consists of a mantissa (3.52 in the example above) a radix (always 10), and an exponent (3 in the example above). Hence, the general format of a scientific notation value is:

mantissa * radix^exponent

The normalized form always has a mantissa greater than or equal to 1.0, and strictly less than 10.0. Written mathematically, the mantissa is in the set [1.0,10.0). As you may recall from algebra, [] encloses a set including the extreme values and () encloses a set excluding them. We can denormalize the value and express it in many other ways, such as 35.2 * 10², or 0.00325 x 10⁶. For each position we shift the digits of the mantissa relative to the decimal point, we are multiplying or dividing the mantissa by a factor of 10. To compensate for this, we simply increase or decrease the exponent. Adding 1 to the exponent multiplies 10^exponent by 10, for example. this compensates for shifting the mantissa digits one position to the right, which divides the mantissa by 10.

Denormalizing is necessary when adding scientific notation values with different exponents:

    3.52 * 10^3
+   1.97 * 10^5
-----------------------------------------

      1
    0.0352 * 10^5
+   1.97 * 10^5
-----------------------------------------
    2.0052 * 10^5
            

Adjusting the mantissa and exponent is also sometimes necessary to normalize results. For example, if we had chosen to denormalize the other value above, we would see the following:

    3.52 * 10^3
+   1.97 * 10^5
-----------------------------------------

      1
      3.52 * 10^3
+   197.0 * 10^3 
-----------------------------------------
    200.52 * 10^3   Not normalized
    2.0052 * 10^5   Normalized
            

For this reason, it's best to denormalize the number with the smaller exponent. This way, the result of the addition is likely to be already normalized.

A binary floating system is basically the same, but stores a signed binary mantissa and a signed binary exponent, and usually uses a radix of 2. Using a radix of 2 (or any power of 2) allows us to normalize and denormalize by simply shifting the binary digits in the mantissa and adding or subtracting from the exponent, just as we do with scientific notation. Shifting binary digits in the mantissa n bits to the left or right multiplies or divides the mantissa by 2ⁿ, just as shifting decimal digits multiplies or divides by 10.

00010₂ * 2³ = 01000₂ * 2¹.

Standard floating point formats are defined by the IEEE society. The IEEE formats are slightly more complex than necessary to understand floating point in general, so we will start with a simpler example here.

Many people get confused about floating point because of their inability to abstract it into a hierarchy of simple components. If we solve one piece of the puzzle at a time and then put them together, it's no more difficult than fixed point or integers. It just requires a simple extra step such as computing mantissa * radix ^ exponent. Don't think about the floating point format overall or the exponent while converting the mantissa. Just understand the mantissa and deal with it separately. This is a classic example of divide and conquer, which is the whole point of abstraction.

Suppose a 32-bit floating point format has a 24-bit two's complement mantissa, an 8-bit two's complement exponent, and a radix of 2. The general structure is:

mantissa * 2^exponent

The binary format is as follows, labeling bits starting with 0 on the right as we would with an unsigned integer:

 31                  8 7        0
+--------------------------------+
|       mantissa      | exponent |
+--------------------------------+
            

We do not need to store the radix, since it never changes and can just be assumed by the hardware design.

Overflow occurs when the result of a floating point operation is larger than the largest positive value, or smaller than the smallest negative value. In other words, the magnitude is too large to represent.

Underflow occurs when the result of a floating point operation is between the smallest possible positive value and the largest possible negative value. In other words, the magnitude is too small to represent.

The example 32-bit format above cannot represent values larger than 1.42 * 10⁴⁵ or smaller than 2.93873587706 * 10^-39.

One technique to avoid overflow and underflow is to alternate operations that increase and decrease intermediate results. Rather than do all the multiplications (by values greater than 1) first, which could cause overflow, or all the divisions first, which could cause underflow, we could alternate multiplications and divisions to moderate the results along the way. Techniques like these must often be used in scientific calculations.

Using 4-bit unsigned integers as a simpler example of the concept, if we try to compute 4 * 4 / 2, we will encounter an overflow because 4 * 4 is larger than the maximum value of 15 that we can represent in 4-bits. If, on the other hand, we compute it as 4 / 2 * 4, we get the correct result. The same principle applies to all systems with limited range.

Everything has a cost. The increased range and the ability to represent non-whole numbers is no exception.

Performance

Arithmetic on floating point is several times slower than on integers. This is an inherent property of the more complex format.

Consider the process of adding two scientific notation values:

1. Equalize the exponents
2. Add the mantissas
3. Normalize the result

Each of these operations take roughly the same amount of time in a computer as a single integer addition. Since floating point is stored like scientific notation, it uses a similar process and we can expect floating point addition to take about three times as long as integer addition. In reality, a typical PC takes about 2.5 times as long to run a loop doing mostly floating point arithmetic as it does to do the same loop with integers.

Note that this applies only to operations that can be carried out using either a single integer instruction or a single floating point instruction. For example, suppose a program is running on a 32-bit computer, and the data may be outside the range of a 32-bit integer. In this case, multiple integer instructions will be necessary to process integer values of more than 64 bits, and much of the speed advantage of integers is lost.

If hardware has floating point support built-in, then common operations like floating point addition, subtraction, etc. can each be handled by a single instruction. If hardware doesn't have a floating point unit (common in microcontrollers), floating point operations must be handled by software routines. Hence, adding two floating point values will require dozens of integer instructions to complete instead of just one floating point instruction.

Most algorithms can be implemented using integers instead of floating point with a little thought. Use of floating point is often the result of sheer laziness. Don't use floating point just because it's intuitive. Think about whether it is really necessary. The answer is usually no.

Example 14.8. Improving Speed with Integers

The value of PI can be estimated using a Monte Carlo simulation by generating uniform random coordinates across a square "dart board" with an inscribed circle. Since the darts are distributed in a uniform random fashion, the probability of one landing in the circle is the area of the circle divided by the area of the square. This ratio is PI/4.

Figure 14.1. Monte Carlo Dart Board

After generating many random points, we simply divide the number within the circle by the total to get an estimate of PI/4. The intuitive approach is a use a 1 x 1 square and generate random x and y values between 0 and 1. However, this approach requires the use of floating point. if we instead make the dimensions of the square our maximum integer size (e.g. 2³²-1) and generate integer x and y values instead, we can eliminate all floating point calculations from the program.

In fact, the integer implementation of this program is more than twice as fast as the floating point implementation. Full details can be found in the Research Computing User's Guide.

#include <stdio.h>
#include <sysexits.h>

int     main(int argc,char *argv[])

{
    double  x;

    for (x = 0.0; x != 1.0; x += 0.1)
        printf("%0.16f\n", x);

    return EX_OK;
}
                

0.0000000000000000
0.1000000000000000
0.2000000000000000
0.3000000000000000
0.4000000000000000
0.5000000000000000
0.6000000000000000
0.7000000000000000
0.7999999999999999
0.8999999999999999
0.9999999999999999
1.0999999999999999
1.2000000000000000
1.3000000000000000
1.4000000000000001
1.5000000000000002
...
                

The example floating point systems above are only for general understanding and context and not used in real systems. Use of integer mantissa formats suffers from problems such as multiple representations of the same value, e.g. 1 * 2² = 2 * 2¹.

The IEEE floating point formats have become standard on most CPUs. They are highly optimized and contain special features, like representations for infinity and not-a-number (NaN).

S is the sign bit. Like integer formats, 1 indicates a negative number and 0 indicates positive.

F is the fractional part of the mantissa. The non-fractional part is not stored, and always 1, so the actual mantissa is 1.F₂. This method provides an extra bit of precision that need not be stored, so we have a 24-bit fixed point mantissa in reality, even though we only store 23 bits. It also ensures that there is only 1 way to represent a given value, unlike the example formats above with integer mantissas.

The 8-bit exponent is stored in bias-127 notation, hence E is an unsigned integer with the value exponent + 127.

The absolute value of the number is 1.F x 2^E-127, except for some special cases:

The floating-point hardware uses more than 23 bits for computation to avoid round-off error. This is particularly important when adding values with different exponents, since the mantissas must be offset by up to 128 bits before addition, thus producing a sum with up to 24 + 128 = 152 bits. The result is trimmed back to 24 bits after normalizing the result.

The 64-bit format is similar to the 32-bit format, but uses an 11-bit bias-1023 exponent, and a 53-bit fixed-point mantissa in the form 1.x, where only the fractional portion (52 bits) is stored.

The range of the 64-bit format is +/- (2.2250 * 10^-308 to 1.7976 * 10³⁰⁸)