Numeración basada en cero

Martin Richards , creador del lenguaje BCPL (precursor de C ), diseñó arreglos que se inician en 0 como la posición natural para acceder al contenido del arreglo en el lenguaje, ya que el valor de un puntero p utilizado como dirección accede a la posición p + 0 en la memoria. ^{[ 5 ] [ 6 ]} BCPL se compiló por primera vez para el IBM 7094 ; el lenguaje no introdujo búsquedas de indirección en tiempo de ejecución , por lo que la optimización de indirección proporcionada por estos arreglos se realizó en tiempo de compilación. ^{[ 6 ]} Sin embargo, la optimización fue importante. ^{[ 6 ] [ 7 ]}

En 1982, Edsger W. Dijkstra, en su pertinente nota «Por qué la numeración debería empezar en cero» ^{[ 8 ],} argumentó que los subíndices de los arreglos deberían empezar en cero, ya que es el número más natural . Al analizar posibles diseños de rangos de arreglos encerrándolos en una desigualdad encadenada, combinando desigualdades estrictas y estándar para obtener cuatro posibilidades, demostró que, en su opinión, los arreglos basados ​​en cero se representan mejor mediante rangos de índices que no se superponen, los cuales comienzan en cero, aludiendo a intervalos abiertos, semiabiertos y cerrados, como en el caso de los números reales. Los criterios de Dijkstra para preferir esta convención son, en detalle, que representa secuencias vacías de una manera más natural ( a ≤ i < a  ?) que los "intervalos" cerrados ( a ≤ i ≤ ( a − 1)  ? ), y que con "intervalos" semiabiertos de números naturales, la longitud de una subsecuencia es igual al límite superior menos el límite inferior ( a ≤ i < b da ( b − a ) valores posibles para i , con a , b , i todos enteros).

Este uso se deriva de decisiones de diseño presentes en muchos lenguajes de programación influyentes , como C , Java y Lisp . En estos tres, los tipos de secuencia (arreglos en C, arreglos y listas en Java, y listas y vectores en Lisp) se indexan comenzando con el subíndice cero. Particularmente en C, donde los arreglos están estrechamente ligados a la aritmética de punteros , esto simplifica la implementación: el subíndice se refiere a un desplazamiento desde la posición inicial del arreglo, por lo que el primer elemento tiene un desplazamiento de cero.

La referencia a la memoria mediante una dirección y un desplazamiento se representa directamente en el hardware de prácticamente todas las arquitecturas informáticas, por lo que este detalle de diseño en C facilita la compilación, aunque a costa de ciertos factores humanos. En este contexto, usar "cero" como ordinal no es estrictamente correcto, pero es una práctica común en este ámbito. Algunos lenguajes de programación, como Fortran o COBOL , tienen subíndices de matriz que comienzan con uno, ya que fueron concebidos como lenguajes de programación de alto nivel y, como tales, debían tener una correspondencia con los números ordinales habituales , que son muy anteriores a la invención del cero . Y algunos lenguajes de programación, como Ada , ALGOL 60 y PL/I , permiten un límite inferior arbitrario para cada índice.

Pascal permite que el rango de una matriz sea de cualquier tipo ordinal (incluidos los tipos enumerados) y Ada permite cualquier subtipo discreto. APL permite establecer el origen del índice en 0 o 1 durante el tiempo de ejecución mediante programación. ^{[ 9 ] [ 10 ]} Algunos lenguajes más recientes, como Lua y Visual Basic , han adoptado la misma convención por la misma razón.

El cero es el valor entero sin signo más pequeño, uno de los tipos más fundamentales en programación y diseño de hardware. En informática, el cero se usa frecuentemente como caso base para muchos tipos de recursión numérica . Las demostraciones y otros razonamientos matemáticos en informática a menudo comienzan con cero. Por estas razones, en informática no es inusual numerar desde cero en lugar de desde uno.

Si se utiliza una matriz para representar un ciclo, es conveniente obtener el índice con una función módulo , que puede dar como resultado cero.

Con la numeración basada en cero, un rango se puede expresar como el intervalo semiabierto [ 0, n ) , en contraposición al intervalo cerrado [1, n ] . Los rangos vacíos, que suelen aparecer en los algoritmos, son difíciles de expresar con un intervalo cerrado sin recurrir a convenciones obtusas como [1, 0] . Debido a esta propiedad, la indexación basada en cero reduce potencialmente los errores de desfase de uno y los errores de delimitación . ^{[ 8 ]} Por otro lado, el recuento de repeticiones n se calcula de antemano, lo que hace que el uso del conteo de 0 a n − 1 (inclusive) sea menos intuitivo. Algunos autores prefieren la indexación basada en uno, ya que se corresponde más estrechamente con la forma en que se indexan las entidades en otros contextos. ^{[ 11 ]}

Otra característica de esta convención reside en el uso de la aritmética modular, tal como se implementa en las computadoras modernas. Generalmente, la función módulo asigna a cualquier entero módulo N uno de los números 0, 1, 2, ..., N − 1 , donde N ≥ 1. Gracias a esto, muchas fórmulas en algoritmos (como la que se usa para calcular los índices de una tabla hash) se pueden expresar elegantemente en código utilizando la operación módulo cuando los índices de los arreglos comienzan en cero.

Las operaciones con punteros también pueden expresarse de forma más elegante en un índice basado en cero debido a la lógica subyacente de dirección/desplazamiento mencionada anteriormente. Para ilustrarlo, supongamos que a es la dirección de memoria del primer elemento de un array e i es el índice del elemento deseado. Para calcular la dirección del elemento deseado, si los índices comienzan desde 1, la dirección deseada se calcula mediante esta expresión:

${\displaystyle a+s\times (i-1),}$

donde s es el tamaño de cada elemento. En cambio, si los números de índice cuentan desde 0, la expresión se convierte en

${\displaystyle a+s\times i.}$

Esta expresión más simple es más eficiente para calcular en tiempo de ejecución .

Sin embargo, un lenguaje que desee indexar arreglos desde 1 podría adoptar la convención de que cada dirección de arreglo se representa mediante a ′ = a – s ; es decir, en lugar de usar la dirección del primer elemento del arreglo, dicho lenguaje usaría la dirección de un elemento ficticio ubicado inmediatamente antes del primer elemento real. La expresión de indexación para un índice basado en 1 sería entonces:

${\displaystyle a'+s\times i.}$

Por lo tanto, la ventaja de eficiencia en tiempo de ejecución que ofrece la indexación basada en cero no es inherente, sino un efecto de la decisión de representar un array con la dirección de su primer elemento en lugar de la dirección del ficticio elemento cero. Sin embargo, la dirección de ese elemento ficticio bien podría ser la de algún otro elemento en memoria no relacionado con el array.

Superficialmente, el elemento ficticio no se adapta bien a matrices multidimensionales. Indexar matrices multidimensionales desde cero hace que una conversión ingenua (contigua) a un espacio de direcciones lineal (variando sistemáticamente un índice tras otro) parezca más simple que cuando se indexa desde uno. Por ejemplo, al mapear la matriz tridimensional A[ P ][ N ][ M ] a una matriz lineal L[ M⋅N⋅P ] , ambas con M ⋅ N ⋅ P elementos, el índice r en la matriz lineal para acceder a un elemento específico con L[ r ] = A[ z ][ y ][ x ] en indexación basada en cero, es decir [0 ≤ x < P ] , [0 ≤ y < N ] , [0 ≤ z < M ] , y [0 ≤ r < M ⋅ N ⋅ P ] , se calcula mediante

${\displaystyle r=z\cdot M\cdot N+y\cdot M+x.}$

Al organizar todos los arreglos con índices basados ​​en 1 ( [1 ≤ x′ ≤ P ] , [1 ≤ y′ ≤ N ] , [1 ≤ z′ ≤ M ] , [1 ≤ r′ ≤ M ⋅ N ⋅ P ] ), y asumiendo una disposición análoga de los elementos, se obtiene

${\displaystyle r'=(z'-1)\cdot M\cdot N+(y'-1)\cdot M+(x'-0)}$

para acceder al mismo elemento, lo que sin duda parece más complicado. Por supuesto, r ′ = r + 1, ya que [ z = z ′ – 1], [ y = y ′ – 1] y [ x = x ′ – 1]. Un ejemplo sencillo y cotidiano es la notación posicional , que la invención del cero hizo posible. En la notación posicional, las decenas, las centenas, los millares y todos los demás dígitos comienzan con cero; solo las unidades comienzan con uno. ^{[ 12 ]}

Esta situación puede generar cierta confusión terminológica. En un esquema de indexación basado en cero, el primer elemento es el "elemento número cero"; asimismo, el duodécimo elemento es el "elemento número once". Por lo tanto, surge una analogía entre los números ordinales y la cantidad de objetos numerados: el índice más alto de n objetos será n − 1 , y se refiere al n -ésimo elemento. Por esta razón, a veces se hace referencia al primer elemento como el elemento cero , para evitar confusiones.