Index notation is used in mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 and computer programming

Computer programming

Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...

 to specify the elements of matrices

Matrix (mathematics)

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

 or the components of a vector. The formalism of how indices are used varies according to the discipline. In particular, there are different methods for referring to the elements of a list, a vector, or a matrix, depending on whether one is writing a formal mathematical paper for publication, or when one is writing a computer program

Computer program

A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...

.

Index notation in mathematics

It is quite common in mathematical writing to refer to the elements of an array using subscripts. The subscripts can be integers or variables. The following line states in effect that the each of the elements of a vector c are equal to the sum of the corresponding elements of vectors a and b

so
and so on.

More than one index is used to describe arrays or number with two or more dimensions, such as the elements of a matrix. The (i, j)^th entry of a matrix A is most commonly written as a_i,j , where the first subscript is the row number and the second is the column number. For example, if

then a_2,3 = 7.

Superscripts are used instead of subscripts to distinguish covariant from contravariant entities, see Covariance and contravariance of vectors, particularly in the theory of general relativity

General relativity

General relativity or the general theory of relativity is the geometric theory of gravitation published by Albert Einstein in 1916. It is the current description of gravitation in modern physics...

 and the classical treatment of tensors. The terms "index notation", or "indicial notation" are sometimes used to refer to Einstein notation

Einstein notation

In mathematics, especially in applications of linear algebra to physics, the Einstein notation or Einstein summation convention is a notational convention useful when dealing with coordinate formulae...

.

Index notation in computing

In several programming languages, index notation is a way of addressing elements of an array. This method is used since it is closest to how it is implemented in assembly language

Assembly language

An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...

 whereby the address of the first element is used as a base, and a multiple (the index) of the element size is used to address inside the array.

For example, if an array of integers is stored in a region of the computer's memory starting at the memory cell with address 3000 (the base address

Base address

In computing, a base address is an address serving as a reference point for other addresses.In computers using relative addressing scheme, to obtain an absolute address, the relevant base address is taken and offset is added to it....

), and each integer occupies four cells (bytes), then the elements of this array are at memory locations 3000, 3004, 3008, ..., 0x3000 + 4(n-1). In general, the address of the ith element of an array with base address

Base address

In computing, a base address is an address serving as a reference point for other addresses.In computers using relative addressing scheme, to obtain an absolute address, the relevant base address is taken and offset is added to it....

 b and element size s is b+is. Its also used to divide a regular number to a basic stage of prime.

C implementation details

In the C programming language

C (programming language)

C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

, we can write the above as *(base + i) (pointer form) or base[i] (array indexing form), which is exactly equivalent because the C standard defines the array indexing form as a transformation to pointer form. Coincidentally, since pointer addition is commutative, this allows for obscure expressions such as 3[base] which is equivalent to base[3].

Multidimensional arrays

Things become more interesting when we consider arrays with more than one index, for example, a two-dimensional table. We have three possibilities:

• make the two-dimensional array one-dimensional by computing a single index from the two
• consider a one-dimensional array where each element is another one-dimensional array, i.e. an array of arrays
• use additional storage to hold the array of addresses of each row of the original array, and store the rows of the original array as separate one-dimensional arrays

In C, all three methods can be used. When the first method is used, the programmer decides how the elements of the array are laid out in the computer's memory, and provides the formulas to compute the location of each element. The second method is used when the number of elements in each row is the same and known at the time the program is written. The programmer declares the array to have, say, three columns by writing e.g. elementtype tablename[][3];. One then refers to a particular element of the array by writing tablename[first index][second index]. The compiler computes the total number of memory cells occupied by each row, uses the first index to find the address of the desired row, and then uses the second index to find the address of the desired element in the row. When the third method is used, the programmer declares the table to be an array of pointers, like in elementtype *tablename[];. When the programmer subsequently specifies a particular element tablename[first index][second index], the compiler generates instructions to look up the address of the row specified by the first index, and use this address as the base when computing the address of the element specified by the second index.

Example

This function multiplies two 3x3 floating point matrices together.

void mult3x3f(float result[][3], const float A[][3], const float B[][3])
{
int i, j, k;
for (i = 0; i < 3; ++i) {
for (j = 0; j < 3; ++j) {
result[i][j] = 0;
for (k = 0; k < 3; ++k)
result[i][j] += A[i][k] * B[k][j];
}
}
}

In other languages

In other programming languages such as Pascal, indices may start at 1, so indexing in a block of memory can be changed to fit a start-at-1 addressing scheme by a simple linear transformation - in this scheme, the memory location of the ith element with base address

Base address

In computing, a base address is an address serving as a reference point for other addresses.In computers using relative addressing scheme, to obtain an absolute address, the relevant base address is taken and offset is added to it....

b and element size s is b+(i-1)s.

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.