ルックアップテーブル
線形探索や力まかせ探索では、リストの各要素との比較を次々に行い、対応する値が見つかったらその値が検索結果となる。このような検索方法では、対応する値がリスト中になかったり、あるいはリストの後ろの方にあったりといった原因で簡単に性能が悪化してしまう。一次元の配列や連結リストでは通常、このようなルックアップは入力値に合致する要素があるか判断するために行われる。
ただし、このテーブルは相当の大きさになる。IEEE倍精度浮動小数点数を使用する場合なら、テーブルのサイズは16,000バイト以上にもなる。サンプル数を減らす方法もあるが、これは代わりに精度が著しく悪化する。この問題の一つの解決方法としては線形補間がある。これは、テーブル中でxと隣り合っている2つの値の間に直線を引き、この直線上の値を求めるという方法である。これは計算も速く、滑らかな関数においてもかなり正確な値を求められる。線形補間を利用した例は以下のようになる。
その他には、正弦と余弦の関係、および対称性を利用して、少しの計算時間を引き換えにテーブルのサイズを1/4にする方法がある。この場合、ルックアップテーブルを作成する際に、第一象限だけを対象とする(つまり、 0 ≦ x ≦ π 2 {\displaystyle 0\leqq x\leqq {\frac {\pi }{2}}} の範囲のみ正弦の計算を行う)。値を求める際は、変数を第一象限に当てはめなおす。