ゼロベース番号付け

BCPL言語（ C言語の前身）の作成者であるマーティン・リチャーズは、アドレスとして使用されるポインタpの値がメモリ内の位置p +0にアクセスするため、言語内で配列の内容にアクセスし始める自然な位置として、0から始まる配列を設計しました。^{[ 5 ] [ 6 ]} BCPLは最初にIBM 7094向けにコンパイルされました。この言語は実行時間接参照ルックアップを導入しなかったため、これらの配列によって提供される間接参照の最適化はコンパイル時に行われました。^{[ 6 ]}それでも最適化は重要でした。^{[ 6 ] [ 7 ]}

1982年、エドガー・W・ダイクストラは、関連する論文「なぜ番号付けはゼロから始めるべきなのか」^{[ 8 ]}の中で、配列の添え字はゼロから始めるべきであると主張した。ゼロは最も自然な数だからである。彼は、連鎖不等式で配列範囲を囲むことで可能な配列範囲の設計について議論し、厳密な不等式と標準的な不等式を組み合わせて4つの可能性を示し、ゼロベースの配列は、実数と同様に、開区間、半開区間、閉区間を暗示する、ゼロから始まる重複しないインデックス範囲によって最もよく表現されることを確信している。ダイクストラがこの慣習を好む理由として、具体的には、閉じた「区間」( a ≤ i ≤ ( a − 1) ? ) よりも、空のシーケンス( a ≤ i < a  ? ) をより自然な方法で表現できること、そして自然数の半開「区間」では、部分シーケンスの長さが上限から下限を引いた値に等しいこと ( a ≤ i < bはiに対して( b − a )個の可能な値を与え、a、b、i はすべて整数) を挙げている。 

この用法は、 C、Java、Lispなど、多くの影響力のあるプログラミング言語に組み込まれた設計上の選択に由来します。これら3つの言語では、シーケンス型（C言語の配列、Javaの配列とリスト、Lispのリストとベクトル）は、添え字0から始まるインデックスで表されます。特にC言語では、配列がポインタ演算と密接に結びついているため、この方が実装が簡単になります。添え字は配列の開始位置からのオフセットを表すため、最初の要素のオフセットは0になります。

アドレスとオフセットによるメモリの参照は、ほぼすべてのコンピュータアーキテクチャでコンピュータハードウェアに直接表現されるため、C言語のこの設計上の詳細は、多少の人的要因を犠牲にしてコンパイルを容易にします。この文脈では、「ゼロ」を序数として使用することは厳密には正しくありませんが、この業界では広く使われている習慣です。FortranやCOBOLなどの一部のプログラミング言語は、高水準プログラミング言語として設計されていたため、配列の添え字が1から始まります。そのため、ゼロの発明よりずっと前に存在した通常の序数に対応する必要がありました。また、 Ada、ALGOL 60、PL/Iなどの一部のプログラミング言語では、各インデックスに任意の下限を設定できます。

Pascal では配列の範囲を任意の順序型 (列挙型を含む) にすることができ、Ada では任意の離散サブタイプにすることができます。APLでは実行時にプログラムでインデックスの原点を 0 または 1 に設定することができます。^{[ 9 ] [ 10 ]} LuaやVisual Basicなどの最近の言語では、同じ理由で同じ慣習を採用しています。

ゼロは符号なし整数の最小値であり、プログラミングやハードウェア設計において最も基本的な型の1つです。そのため、コンピュータサイエンスでは、ゼロは多くの種類の数値再帰の基底ケースとしてよく用いられます。コンピュータサイエンスにおける証明やその他の数学的推論は、しばしばゼロから始まります。こうした理由から、コンピュータサイエンスでは1ではなくゼロから番号を振ることは珍しくありません。

配列がサイクルを表すために使用される場合、モジュロ関数を使用してインデックスを取得すると便利ですが、その結果はゼロになる可能性があります。

ゼロベースの番号付けでは、範囲は閉区間 [1, n] ではなく、半開区間[ 0 , n )として表現できます。アルゴリズムでよく発生する空の範囲は、 [1, 0]のような分かりにくい慣習に頼らずに閉区間で表現するのは困難です。この特性により、ゼロベースのインデックス付けは、オフバイワンエラーやフェンスポストエラーを減らす可能性があります。^{[ 8 ]}一方、繰り返し回数nは事前に計算されるため、0 からn − 1 (含む)までカウントする方法は直感的ではありません。一部の著者は、他のコンテキストでエンティティがインデックス付けされる方法により近いことから、1 ベースのインデックス付けを好みます。^{[ 11 ]}

この規約のもう一つの特徴は、現代のコンピュータで実装されているモジュロ演算の使用です。通常、モジュロ関数は、N を法とする任意の整数を0、1、2、...、N − 1のいずれかの数にマッピングします ( N ≥ 1 )。このため、配列インデックスがゼロから始まる場合、アルゴリズム (ハッシュテーブルのインデックスを計算する式など) の多くの式を、モジュロ演算を使用してコードで簡潔に表現できます。

ポインタ操作は、前述のアドレス/オフセットロジックのおかげで、ゼロベースのインデックスに対してより簡潔に表現することもできます。例として、a が配列の最初の要素のメモリ アドレス、iが目的の要素のインデックスであるとします。インデックス番号が 1 から始まる場合、目的の要素のアドレスは次の式で計算されます。

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

ここで、sは各要素のサイズです。対照的に、インデックス番号が 0 から始まる場合、式は次のようになります。

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

このより単純な式は、実行時に計算するのに効率的です。

しかし、配列を1からインデックス付けしたい言語では、すべての配列アドレスをa ′ = a – sで表すという慣例を採用することができます。つまり、最初の配列要素のアドレスを使用する代わりに、そのような言語では、最初の実際の要素の直前に位置する仮想要素のアドレスを使用します。1から始まるインデックスのインデックス式は次のようになります。

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

したがって、実行時におけるゼロベースインデックスの効率性向上は本来的なものではなく、配列を仮想的なゼロ番目の要素のアドレスではなく、最初の要素のアドレスで表現するという決定の結果生じるものです。しかし、その仮想的な要素のアドレスは、配列とは無関係なメモリ内の別の項目のアドレスである可能性も十分にあります。

表面的には、この仮想要素は多次元配列にはうまく対応できません。多次元配列をゼロからインデックス付けすると、線形アドレス空間への単純な（連続的な）変換（インデックスを順番に体系的に変化させる）が、1からインデックス付けする場合よりも簡単に見えます。たとえば、3次元配列A[ P ][ N ][ M ]を、どちらもM ⋅ N ⋅ P個の要素を持つ線形配列L[ M⋅N⋅P ]にマッピングする場合、ゼロベースのインデックス付けでL[ r ] = A[ z ][ y ][ x ]となる特定の要素にアクセスするための線形配列のインデックスrは、 [0 ≤ x < P ]、[0 ≤ y < N ]、[0 ≤ z < M ]、および[0 ≤ r < M ⋅ N ⋅ P ]で計算されます。

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

1 から始まるインデックス ( [1 ≤ x′ ≤ P ]、[1 ≤ y′ ≤ N ]、[1 ≤ z′ ≤ M ]、[1 ≤ r′ ≤ M ⋅ N ⋅ P ] ) で全ての配列を整理し、要素の同様の配置を仮定すると、

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

同じ要素にアクセスするには、より複雑に見えるかもしれません。もちろん、[ z = z ′ – 1]、[ y = y ′ – 1]、 [ x = x ′ – 1]なので、 r ′ = r + 1です。シンプルで日常生活の例としては、ゼロの発明によって可能になった位取り記数法があります。位取り記数法では、十の位、百の位、千の位、その他のすべての桁はゼロから始まり、一の位のみが1から始まります。^{[ 12 ]}

この状況は用語の混乱を招く可能性があります。ゼロベースのインデックス方式では、最初の要素は「要素番号ゼロ」であり、同様に、12番目の要素は「要素番号11」です。したがって、序数から番号付けされたオブジェクトの数への類推が生じます。n個のオブジェクトの最大のインデックスはn - 1であり、これはn番目の要素を指します。このため、混乱を避けるために、最初の要素はゼロ番目の要素と呼ばれることがあります。