查找表

由於從內存中提取數值經常要比複雜的計算速度快很多，所以這樣得到的速度提升是很顯著的。

一個經典的例子就是三角表。每次計算所需的正弦值在一些應用中可能會慢得無法忍受，為了避免這種情況，應用程序可以在剛開始的一段時間計算一定數量的角度的正弦值，譬如計算每個整數角度的正弦值，在後面的程序需要正弦值的時候，使用查找表從內存中提取臨近角度的正弦值而不是使用數學公式進行計算。

在計算機出現之前，人們使用類似的表格來加快手工計算的速度。非常流行的表格有三角、對數、統計 density 函數。另外一種用來加快手工計算的工具是滑動計算尺。

一些折衷的方法是同時使用查找表和插值這樣需要少許計算量的方法，這種方法對於兩個預計算的值之間的部分能夠提供更高的精度，這樣稍微地增加了計算量但是大幅度地提高了應用程序所需的精度。根據預先計算的數值，這種方法在保持同樣精度的前提下也減小了查找表的尺寸。

在圖像處理中，查找表經常稱為LUT，它們將索引號與輸出值建立聯繫。顏色表作為一種普通的 LUT 是用來確定特定圖像所要顯示的顏色和強度。

另外需要注意的一個問題是，儘管查找表經常效率很高，但是如果所替換的計算相當簡單的話就會得不償失，這不僅僅因為從內存中提取結果需要更多的時間，而且因為它增大了所需的內存並且破壞了高速緩存。如果查找表太大，那麼幾乎每次訪問查找表都會導致高速緩存缺失，這在處理器速度超過內存速度的時候愈發成為一個問題。在編譯器優化的 rematerialization 過程中也會出現類似的問題。在一些環境如Java 編程語言中，由於強制性的邊界檢查帶來的每次查找的附加比較和分支過程，所以查找表可能開銷更大。

何時構建查找表有兩個基本的約束條件，一個是可用內存的數量；不能構建一個超過能用內存空間的表格，儘管可以構建一個以查找速度為代價的基於磁盤的查找表。另外一個約束條件是初始計算查找表的時間——儘管這項工作不需要經常做，但是如果耗費的時間不可接受，那麼也不適合使用查找表。

許多計算機只能執行基本的算術運算，而不能直接計算給定值的正弦值，它們使用如下面泰勒級數（en:Taylor series）這樣的複雜公式計算相當高精度的正弦值：

(x 接近 0)

然而，這樣的計算費用可能是非常大的，尤其是在低速的處理器上。有許多的應用程序，尤其是傳統的計算機圖形每秒需要幾千次的正弦值計算。一個常用的解決方案就是在剛開始計算許多均勻分佈數值的正弦值，然後在表中查找最接近所需 x 的正弦值，這個值非常接近於正確的數值，這是因為正弦函數是一個有限變化率的連續函數。例如：

real array sine_table[-1000..1000]

for x from -1000 to 1000

sine_table[x] := sine(x/1000/pi)

function lookup_sine(x)

return sine_table[round(x/1000/pi)]

Image:Interpolation example linear.png

部分正弦函數的線性插值不幸的是，查找表需要一定的空間：如果使用 IEEE 雙精度浮點數的話，將會需要 16,000 字節。如果使用較少的採樣點，那麼精度將會大幅度地下降。一個較好的解決方案是線性插值，在表中待計算點左右兩側兩個點的值之間連直線，這個點對應的直線上的值就是所計算點的正弦值。這種方法計算速度也很快，對於如正弦函數這樣的平滑函數來説也有更高的精度。這裏是使用線性插值的一個例子：

function lookup_sine(x)

x1 := floor(x/1000/pi)

y1 := sine_table[x1]

y2 := sine_table[x1+1]

return y1 + (y2-y1)*(x/1000/pi-x1)

當使用插值的時候，可以得益於不均勻採樣，也就是説在接近直線的地方，使用較少的採樣點，在變化較快的地方使用較多的採樣點以最大限度地接近實際的曲線。更多的信息請參考插值。

population function。例如，數字 37 的二進制形式是 100101，所以它包含有三個設置成 1 的位。一個計算 32 位整數中 1 的位數的簡單c語言程序是：

int count_ones(unsigned int x) {

int i, result = 0;

for(i=0; i<32; i++) {

result += x & 1;

x = x >> 1;

}

return result;

}

不幸的是，這個簡單的算法在現代的架構上將需要數以百計的時鐘週期才能完成，這是因為它造成了許多分支和循環，而分支的速度是很慢的。這可以使用 loop unrolling 和其它一些聰明的技巧進行改進，但是最簡單快捷的解決方案是查找表：簡單地構建一個 包含每個字節可能值包含的 1 的個數的256 個條目的表。然後使用這個表查找整數中每個字節包含的 1 的個數，並且將結果相加。沒有分支、四次內存訪問、幾乎沒有算術運算，這樣與上面的算法相比就可以大幅度地提升速度。

int count_ones(unsigned int x) {

return bits_set[x & 255] + bits_set[(x >> 8) & 255]

+ bits_set[(x >> 16) & 255] + bits_set[(x >> 24) & 255];

}

----------------------------------------------------------------------

#include

#define BYTE unsigned char

/* 定義查找表 */

BYTE numTable[256] =

{

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,

3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3,

4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,

3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3,

4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,

6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4,

5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3,

4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4,

4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6,

7, 6, 7, 7, 8

};

int main(int argc, char *argv[])

{

int i, num = 0;

BYTE a = 0;

/* 接收用户輸入 */

printf("\nPlease Input a BYTE(0~255):");

scanf("%d", &a);

/* 計算1 的個數 */

/* 用BYTE 直接作為數組的下標取出1 的個數，妙哉！ */

printf("\nthe num of 1 in the BYTE is %d", checknum[a]);

return 0;

}

在數字邏輯中，n位查找表可以使用多路複用器來實現，它的選擇線是 LUT 的輸入，它的輸入是常數。n 位 LUT 通過將布爾邏輯函數建模為真值表從而可以編碼任意 n 位輸入，這是編碼布爾邏輯函數的一個有效途徑，4 位 LUT 實際上是現代 FPGAs 的主要元件。

採用這種結構的PLD芯片我們就可以稱之為FPGA：如altera的ACEX,APEX系列,xilinx的Spartan,Virtex系列等。

查找表（Look-Up-Table)簡稱為LUT，LUT本質上就是一個RAM。 目前FPGA中多使用4輸入的LUT，所以每一個LUT可以看成一個有4位地址線的16x1的RAM。 當用户通過原理圖或HDL語言描述了一個邏輯電路以後，PLD/FPGA開發軟件會自動計算邏輯電路的所有可能的結果，並把結果事先寫入RAM,這樣，每輸入一個信號進行邏輯運算就等於輸入一個地址進行查表，找出地址對應的內容，然後輸出即可。