Abstract Mathematical Types

The astute reader may have noticed that objects such as integers, real numbers, complex numbers, vectors, matrices, functions, and images (bivariate functions) have not been listed under abstract data types. In some cases, the Sparse Matrix ADT is mentioned as a concept separate from a Matrix ADT and in others, neither is mentioned.

A data structure is a means of storing data; however, integers, vectors, matrices, etc., are all singular mathematical objects even though they may require aggregate data. For example, a matrix is a description of a linear transformation; however, such a transformation requires M × N real or possibly complex numbers.

I will therefore list here a number of mathematical objects together with their representations in computer science:

Boolean Values

The Boolean values true and false have two common representations:

  • A bool type, or
  • Given an integer type, the integer 0 represents false while all other integers represent true.

Characters

Alphabetic characters are ordered, enumerated, and then represented with representation of sufficient size:

  • ASCII codes alphabetic and number characters together with other symbols using seven bits,
  • Extended ASCII allows one further bit to allow an extension to ASCII for 128 other characters,
  • Unicode has many formats (UTF-8, -16, and -32) of which over one million are reserved and over 100 thousand are used.

Integers

Integers are usually implemented using 8, 16, 32, or 64 bits with 2s complement to represent negative integers. On a 32-bit computer, these usually correspond to signed char, short, int, and long, respectively.

Many mathematical libraries will have special objects for storing integers of arbitrary size.

Rational Numbers

Rational numbers are usually represented by a class which contains two integer member variables representing the numerator and denominator. In general, these member variables share no common factors and the denominator is required to be positive.

Real Numbers

Real numbers are most commonly represented by the double-precision floating-point format double. This is specified in IEEE 754. Under very strict well documented situations, it may be possible to use the single-precision floating-point format float; however, the programmer should seriously understand the weaknesses of this 4-byte single-precision format as compared to the 8-byte double-precision format.

Representations include the extended double-precision and quadruple precision floating-point formats as well as others.

Complex Numbers

Complex numbers are usually represented as a class which contains two real number member variables.

N-Dimensional Vectors

An N-dimensional vector is usually represented as a class with an array of N real numbers as the member variable.

Matrices

The most naive representation of an M×N matrix is through an array-of-arrays of MN doubles. This is good for small matrices; however, for most matrices, almost all of the entries are zero and therefore it is usually better to store only those entries which are non-zero. Such a representation is called sparse and there are many variations which are appropriate for different situations.

One pedagogical representation of a sparse matrix representation is shown here.

Images

Given that the human eye has three separate receptors in the eye, it is most common to think of an image as a 3-dimensional vector-valued function of two variables; usually, (red(x, y), green(x, y), blue(x, y))T; however, there are many separate variations on both these characteristics:

  • Raster graphics use an M×N grid of either a single number (for black-and-white images) or triplets of numbers (for colour images) where each point in the grid (a pixel) is an averaging of the shading/colours surrounding it; while
  • Vector graphics use mathematical descriptions of lines, curves, and shading or colours to describe the image.

A film photograph is similar to a raster graphic, but it uses a random distribution of light-sensitive chemicals.

The colour of a colour image is a triplet of values and these usually are recognized as red-green-blue; however, there are numerous other representations possible including:

  • Cyan-magenta-yellow (CMY),
  • Cyan-magenta-yellow-black (CMYK),
  • Luminance-and-chrominance (YIQ and YUV),
  • Hue-saturation-lightness/value (HSL and HSV), and
  • Luminance-and-red/blue-deltas (YPBPR and YCBCR).

Various transformations may be used to approximate an image with the goal of reducing the memory required. These include run-length encoding, discrete Fourier transforms, and discrete wavelet transforms.