LANGUAGE PRIMITE DATA STRUCTURES



LANGUAGE PRIMITIVE DATA STRUCTURES

How well do the integer related data types in modern computer languages represent the mathematical concept of integer?

The mathematical concept of an INTEGER is an aleph null, or countable infinite set[1]. Integers are often represented by the integer number line. The set of integers is closed over addition, subtraction, and multiplication. Integer division can also be defined so that it is closed except, of course, in the case of division by zero. The set of integers also has other well-defined properties such as the existence of additive and multiplicative identities, and an additive inverse. In fact, the set of integers is a Linear Algebra over the operations of + and *, so you can see your Linear Algebra class for more fun along these lines.

In C++, int, long int (or long), short int (or short), and so forth store integers in two’s complement form[2] as a specific number of bits.[3] For example, an int is almost always stored as either 16 bits or 32 bits (2 or 4 bytes). Regardless of language, the range of an integer stored in N bits in two’s complement is always:

-2N-1(+2N-1-1 for 8 bits, this range is -128 to +127

for 16 bits, this range is ≈ ±32K

for 32 bits, this range is ≈ ±2G

Java supports a very similar set of integer data types, and calls them byte, short, int, and long. Many languages also support unsigned integers. In C++, they are called uint, ulong, ushort. The range of integers for an N bit unsigned integer is 0(2N-1. In C++, when you ask for short or long integers, the compiler will decide whether or not you get them. In Java, you will get the size requested, but support for short is spotty, and automatic conversions to int will often cause compilation errors. For example, short a = 3, b = 4; a++; will compile, but a= a+b; will not without converting to a = (short)(a+b); This applies to a number of operations.

As long as no value computed or stored is outside the supported range, the computer representation of integers is a (more or less) perfect mirror to the mathematician’s “integer”. Note: we consider zero to be positive and even, but mathematicians do not. Integer overflow or underflow is the result when such an operation fails.

In C++, limits.h contains predefined constants representing the highest and lowest values for some of these data types. The names of some of these constants are given below. Be advised, however, that it is usually unwise to test against these values as comparisons involve subtraction, and any operation involving one of these numbers can easily produce overflow or underflow.

INT_MIN INT_MAX UINT_MAX

LONG_MIN LONG_MAX ULONG_MAX

SHRT_MIN SHRT_MAX USHRT_MAX

In Java, wrapper classes such as Integer, Long, and Short are predefined for primitive types, and these wrapper classes have predefined static constants such as: Integer.MAX_VALUE, Integer.MIN_VALUE, Long.MAX_VALUE, etc.

How well do the floating point related data types represent the mathematical concept of a real number?

The mathematical concept of a REAL number is an aleph one, uncountable infinite set. The real number line is often used to represent real numbers. Notice the fundamental difference between the set of integers and the set of real numbers. The number of integers between any two numbers on the integer number line is finite. The number of real numbers between any two numbers on the real number line is infinite, and not only infinite but uncountably infinite.

In C++, float, double, and long double are used to represent real numbers. Java supports only float and double. Computer representations of real numbers are stored in a manner similar to scientific notation, except in binary. These representations are called floating-point representations. There are many variations, but the method described here is most common today as it follows the IEEE 754 floating-point representation standard. For 64 bits, a normalized number is stored as a single sign bit, an 11 bit exponent[4] (the base is understood to be 2), 1 understood but not stored bit containing a 1, and a 52 bit fraction/mantissa. There is an understood binary point between the understood 1 and the fraction.

Despite the best efforts of a number of people over the years, 32 bits is simply unable to store floating-point numbers with reasonable accuracy and range. This is why C and C++ ignore float, and use the double representation almost exclusively. For example, none of the functions in math.h[5] expect a float parameter nor do they return a float value. Java is somewhat more orthogonal, as it overloads the mathematical method names for most numeric types for some functions. For example, abs, min, max, and round are defined for double, float, long and int. Even so, sqrt, floor, and ceil are only defined for double.

The exponent provides the range of numbers that can be represented. The 11 bit exponent in double gives a range of ( (21023. In base 10, this is ( (10308.

The fraction/mantissa provides the level of accuracy of the representation (the number of significant digits). Normalization adjusts the binary point until there is a single 1 to the left of the binary point Thus, the mantissa is greater than or equal to 1 and less than 2. This leftmost 1 is normally not stored. The remaining 52 bits of the mantissa is normally stored and is usually called the fraction for obvious reasons. The exponent is adjusted to get mantissa in the desired range. Such numbers are called normalized. Some values such as ZERO cannot be normalized and some other values are de-normalized for other purposes, such as to permit a closer approach to 0.0. These 53 bits (1 not stored) in the mantissa provide 15 to 16 significant digits in decimal.

Thus, all whole numbers requiring no more than 15 or 16 significant digits can be represented exactly in floating-point. Much larger numbers whose binary form has many zeros in the lower bits are also stored exactly. For example:

10101000000000000000000000000000000000000000000000000000000000002

= 1.01012 * 264 (normalized to between 1 and 2)

mantissa = 1.01012 The stored fraction will be = 01010…02

exponent = 64 The stored exponent will be 6410 + 102310 = 108710

As 11 bits in binary, this is will be 100 0011 11112

Furthermore, any fraction that can be stated with the denominators as powers of 2 can be represented exactly. For example:

53/64 = 32/64 + 16/64 + 4/64 + 1/64 = ½ + ¼ + 1/16 + 1/64 = 0.1101012

Many common fractions such as 1/3, 1/5, 2/3, etc cannot be represented exactly as they become repeating binary fractions when converted to binary. For example, 2/5 = 0.410 = 0.011001100110…2. Furthermore, no irrational numbers or transcendental numbers such as (2 or ( or e can be represented exactly.

Even such pedestrian values as those associated with money are usually approximated when stored or computed:

$1.73 cannot be stored exactly as 73/100 cannot be expressed as a sum of fractions with denominators all powers of 2.

Therefore, you should almost never attempt to compare two floating-point values for either equality or inequality. In fact, all compilers should flag such a statement with a warning message. Unfortunately, some do and some do not. The only situation where you can reasonably expect the comparison to work correctly is when the values to be compared were input or constants. (That is, not computed.) Use >= or ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download