04 - types

The type bool

This type represents a mathematical truth value (AKA logical value). It can hold exactly 1 of 2 possible values: false and true.

bool can be thought as a single bit (0 or 1).

bool will be most often used with if and other control flow statements.

Integer types

Most numbers will require multiple memory cells. A single byte consisting of 8 bits can only represent 256 (2^8) distinct values - such small range is too low for most situations. Most code will use 32-bit and 64-bit integer types.

Integers have 2 independent properties:

• length - amount of memory cells they occupy. The more memory they occupy, the wider range of numbers they can represent.

• signedness - if number is signed, its first bit does not contribute to its magnitude but is used as +/- sign instead.

Signed numbers can represent negative values. Unsigned can not, but the extra bit allows twice as many representable magnitudes.

Why signed integers have 1 more possible negative value? Shouldn't this be e.g. -127 - 127?

It actually could be that way if hardware used sign and magnitude notation to represent negative numbers. Basically, all bits except one would mean the number magnitude (written similarly as humans do, but in base 2 instead of base 10) and the last bit meaning + or - sign. However, there is one huge problem with this notation - it allows 2 representations for zero: +0 and -0. Having 2 different possible representations for the same value is very undesirable - it would significantly complicate electrical circuits to support comparison and other mathematical operations.

Here is a table comparing different interpretations of the same 4-bit pattern:

Why ones' and two's complement?

The apostrophe placement is related to english grammar rules and the fact that the first of the terms refers in plural form while the second in singular. See https://english.stackexchange.com/a/145101 and https://english.stackexchange.com/a/520902 for more information.

Computer hardware is using two's complement to represent signed numbers. It has multiple advantages:

• it avoids problems caused by 2 representations for zero

• it has very simple convertion to/from unsigned representation

• multiple math operations have the same implementation for unsigned and two's complement representation, so the same circuit can perform math on numbers in both forms, example:

  • unsigned: addition of 127 (0111 1111) and 128 (1000 0000) is 255 (1111 1111)

  • two's complement: addition of 127 (0111 1111) and -128 (1000 0000) is -1 (1111 1111)

Do I need to remmeber all of this?

No. Bit-level knowledge is suplementary and is not required except in bitwise operations, which are rarely used. I present this knowledge because the fact that numbers in computers have many limitations (especially floating-point types) was very surprising for me.

Special values

Floating-point types support special values. These are mostly intended for mathematical functions which can not output a valid answer (e.g. because the argument is out of domain).

• infinity - all exponent bits set to 1 and all mantissa bits set to 0. Instead of treating this as "zero to a very huge power" it is treated as infinitely large number. The existence of infinity helps to detect possible calculation errors. Infinity can also be negative.

• NaN (not a number) - all exponent bits set to 1 and any non-zero mantissa. The purpose of NaNs is to indicate logic errors - for example, a logarithm can not take negative number as an argument, hence log(-1) = NaN.

1
2
3
4
5
6
7
8
9
10

#include <iostream>
#include <cmath>

int main()
{
	// 1000^1000 is too large to represent - hence infinity
	std::cout << std::pow(1000, 1000) << "\n";
	// logarithms can not accept negative numbers, hence NaN
	std::cout << std::log(-1) << "\n";
}

Operations on special values will generally propagate them further, e.g. infinity +/- any proper value will be infinity, NaN +/- any proper value will be NaN. This is desirable, because if at any point there is a logical mistake it's much better to get clearly meaningless result than to be fooled by something looking valid that came from wrongly written code.

Floating-point limitations

Floating-point limits are not so straightforward as for integers due to their complex notation.

Both mantissa and exponent have their own limits, so there is both maximum/minimum magnitude and maximum/minimum power it can be raised to. In other words, we can speak about:

• largest representable positive and negative value (+/- sign, max m, max p)

• smallest representable positive and negative value, different than 0 (+/- sign, min m, min p)

• granularity: what is the smallest possible difference between 2 consecutive numbers; granularity is not constant

Floating-points store real numbers with limited accurary. Just like in decimal system 1/3 can be approximated as 0.333 or 333 * 10^(-3), the same problem exists in floating-point notation - the only difference is that base 2 is used instead of base 10 for the exponent. There are infinitely many values which can not be precisely represented - instead, the closest approximations are used.

Shortly speaking, granurality increases (more values can be represented in the given subrange) the closer they are to 0. The highest precision is in range -0.1 to 0.1. Analogy: 100 and 101 can be exactly represented. But in case of 1000000001, it might be approximated as 1 * 10^9 when mantisa does not have enough bits to support 1000000001 * 10^1. As numbers grow, more focus is placed into the exponent which causes magnitude to be more rounded towards specific power. Past some point, all odd values are approximated to closest even value.

If floating-point math has limited accuracy, how do calculators work then? How are various fractional values safely computed?

In places such as finance where accuracy is paramount integers are used for calculations. Monetary amounts like 1.5 (in any currency that has denomination of 100) are stored as 150. The same method is commonly found in games - various fractional statistics are multiplied by 100 or 1000 so that all math can happen on whole numbers. Math on integer types is also faster.

Calculators with unlimited precision don't use floating-point arithmetic. They store integers as arrays which can have arbitrarily large size (each cell does not necessarily represent each digit - it's more complicated). They store fractions as 2 integers (numerator and denominator), they don't immediately evaluate every function, they don't simplify formula if it would lose accuracy and so on. Basically, they store information using complex data structures and perform operations using methods very similar to humans. This allows to support arbitrarily complex expressions without losing precision, but the logic that handles them is enormously complicated.

I'm concerned with limited accuracy. How safe is using floating-point representation?

Very safe. In vast majority of applications:

• Error margin is multiple orders of magnitude higher than floating-point inaccuracy (e.g. physical data was measured with 0.01% error, computations had 0.000001% error).

• Accuracy isn't actually important - especially in computer graphics, projects are much more concerned about performance than perfectly positioned pixels (and since computer screens have only few thousand pixels in row/column, their accuracy is somewhere between 1/1000 and 1/10000 - still much bigger error than floating-point).

• Accurate values would be insignificant - in audio processing applications, very small values would represent a signal too quiet to be in the human hearing range.

As a rule of thumb:

• 32-bit (single precision) floating-point has accuracy of 7 decimal places

• 64-bit (double precision) floating-point has accuracy of 15 decimal places

More to come

If you feel a bit overwhelmed by the complexity of floating-point types, don't worry - further lessons will feature example code showcasing many of their peculiarities.