整數除法與正弦函式最佳化技巧

在嵌入式系統開發中，高效的演算法至關重要。本文將介紹如何最佳化除以 6 的運算以及正弦函式的計算，以減少處理器負載和提升效能。對於除以 6，我們採用乘法和位移運算的組合來近似結果，藉此避免耗時的除法指令。針對正弦函式，我們則運用查表法和線性插值法，以預先計算好的數值取代複雜的浮點數運算。查表法的設計重點在於步長和索引計算，我們將步長設定為 2 的冪次，以便使用高效的位移運算。此外，我們還引入半步長的概念，使查表結果更貼近目標值，進一步提升精確度。最後，我們討論了線性插值法，它結合查表資料和簡單的代數運算，在精確度和效能之間取得平衡。

除以 6 的最佳化

在進行除法運算時，尤其是除以 6 這樣不是 2 的倍數的數字，通常會比較耗時。為了最佳化這個過程，我們可以使用一個技巧，即找到一個近似的乘法運算來替代除法。

首先，我們需要找到一個合適的乘數和 2 的次方數，使得乘數除以 2 的次方數能夠近似地等於 1/6。這樣，我們就可以將除以 6 的運算轉換為乘法和右移運算，從而提高效率。

以下是一些可能的乘數和對應的 2 的次方數，以及它們的近似誤差：

選擇一個合適的乘數和 2 的次方數後，我們可以實作除以 6 的運算。例如，選擇乘數為 171，2 的次方數為 10，我們可以實作如下：

#define DIVIDE_THREE_FACT_MULT 171
#define DIVIDE_THREE_FACT_SHIFT 10

int16_t DivideThreeFactorial(int16_t input) {
    int32_t tmp = input * DIVIDE_THREE_FACT_MULT;
    return (tmp >> DIVIDE_THREE_FACT_SHIFT);
}

這個實作方式比直接進行除法運算更快，但需要注意的是，這個方法需要事先知道除數才能構建函式，因此它並不適用於所有的情況。

對輸入進行縮放

對於某些函式，例如正弦函式，輸入範圍通常為 -π 到 π，輸出範圍為 -1 到 1。如果要避免使用浮點數，可以透過將輸入和輸出都乘以一個固定常數來實作縮放。例如，可以將輸入範圍改為 -1024π 到 1024π，然後輸出需要乘以一個適當的常數來補償。

對於一些函式，如果 f(Ax) = Af(x)，則可以簡單地使用縮放輸入來最佳化。但是，對於像正弦函式這樣不符合這個條件的函式，則需要小心地確保每個項只被乘以縮放因子一次，以避免輸入值被平方。

內容解密：

上述程式碼和方法展示瞭如何透過近似的乘法運算來最佳化除以 6 的過程，以及如何透過對輸入進行縮放來避免使用浮點數。這些方法在特定情況下可以提高效率，但需要根據具體需求和函式特性進行選擇和調整。

圖表翻譯：

  flowchart TD
    A[輸入] --> B[乘以常數]
    B --> C[右移運算]
    C --> D[輸出]

這個流程圖描述瞭如何透過乘以一個常數和右移運算來實作除以 6 的最佳化過程。

瞭解數學函式的近似計算

在實作數學函式的計算時，尤其是在資源有限的嵌入式系統中，對於浮點數運算的替代方案至關重要。這裡我們探討兩種方法：一種是使用泰勒級數進行近似計算，另一種是使用查表法（Lookup Tables）。

泰勒級數近似

泰勒級數是一種用於近似函式值的數學方法，透過展開函式為無窮級數的形式來實作。對於正弦函式，泰勒級數展開式為： [ \sin(x) = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \cdots ]

在實際應用中，為了簡化計算，通常只取級數展開式的前幾項。然而，這樣做會引入誤差，尤其是在輸入值較大的情況下。為了減少誤差，可以對輸入值進行縮放。例如，對輸入值 (x) 進行縮放： [ x_{scaled} = \frac{x}{2^{10}} ] 然後使用縮放後的輸入值計算正弦函式。

查表法（Lookup Tables）

查表法是一種快速的計算方法，透過預先計算好一系列輸入值對應的輸出值，並將這些結果儲存在一個表中。當需要計算某個輸入值對應的輸出值時，只需查詢這個表即可。

查表法的優點在於計算速度快，但需要額外的記憶體空間來儲存查表。設計查表時需要考慮輸入值的範圍和可接受的誤差，這些因素決定了查表的大小和查表中每個條目的精確度。

隱式輸入查表

在某些情況下，可以使用隱式輸入查表。這種方法不需要在查表中明確儲存輸入值，而是透過查表的索引直接對應輸入值。例如，對於一個以毫弧度（milliradians）為單位的正弦函式查表，可以透過索引直接計算出對應的輸出值。

實作查表

以下是一個簡單的查表實作例子，使用C語言定義了一個正弦函式查表：

const int16_t sinLookup[] = {
    -58, // x = -3200
    -335, // x = -2800
    -676, // x = -2400
    -910, // x = -2000
    -1000, // x = -1600
    -933, // x = -1200
    -718, // x = -800
    -390, // x = -400
    0, // x = 0
    389, // x = 400
    //...
};

這個查表假設輸入值以毫弧度為單位，並且輸出值也進行了相應的縮放。

最佳化正弦函式查表法

在最佳化正弦函式的過程中，我們探討了使用查表法來提高效率。然而，為了確保查表法的精確度和效率，我們需要仔細設計查表的步長和索引計算方式。

查表步長和索引計算

最初，我們使用了一個非2的冪次的步長（400），這導致了索引計算中需要進行除法操作。這種方法會增加處理時間，因此我們改為使用2的冪次的步長（512），使得索引計算可以使用位移操作，從而提高效率。

uint8_t index = (x - (-3145)) >> 9;
y = sinLookup[index];

查表精確度和偏移

雖然查表法可以提供快速的結果，但它也可能導致精確度問題。為了提高查表的精確度，我們需要確保查表值能夠覆寫輸入範圍的中心。這可以透過在索引計算中新增半步長來實作：

uint8_t index = (x - (-3145 - 256)) >> 9;
y = sinLookup[index];

查表設計和修改

在設計和修改查表法時，我們需要考慮查表的範圍和步長。為了提高查表的精確度和效率，我們可以使用半步長來中心化查表結果。此外，為了方便維護和理解，我們應該在程式碼中新增清晰的註解和定義。

#define BASE_SIN_LOOKUP (-3124 - 256)
#define SHIFT_SIN_LOOKUP 9

const int16_t sinLookup[] = {
    3, // x @ -3145, for range -3401 to -2888
    -487, // x @ -2633, for range -2889 to -2376
    -853, // x @ -2121, for range -2377 to -1864
    -1000, // x @ -1609, for range -1865 to -1352
};

線性插值法

在查表法中，即使用中心偏移，仍可能需要更準確的結果，而不是單一數字涵蓋一系列輸入。在這種情況下，線性插值法可能是一種選擇。

線性插值法的原理

線性插值法是一種簡單的代數方法，需要從查表中選取兩個值：輸入值以下的值和輸入值以上的值。如圖 12-8 所示，目標是找到特定 x 值的輸出，因此使用兩個最接近的點。由於輸入和輸出值相關，因此將其視為點而非個別值更為簡單。

struct sPoint {
    int16_t x;
    int16_t y;
};

線性插值法的實作

線性插值法的程式碼很簡單，只需注意避免在乘法過程中溢位。

// 這個線性插值法程式碼實作以下公式：
// y = p0.y + ((x-p0.x)*(p1.y-p0.y))/(p1.x-p0.x);
// 但以安全的方式進行運算。
int16_t Interpolate(struct sPoint p0, struct sPoint p1, int16_t x) {
    int16_t y;
    int32_t tmp; // 使用 int32_t 來避免溢位
    tmp = (x - p0.x);
    tmp *= (p1.y - p0.y);
    tmp /= (p1.x - p0.x);
    y = p0.y + tmp; // 現在可以安全地傳回 int16_t
    return (y);
}

線性插值法的優點和限制

這種方法即使輸入值不在兩個點之間也能夠正常工作。如果輸入值剛好在查表的邊界之外，可以使用查表中的最後兩個點進行插值（雖然可能會有精確度損失）。注意，線性插值法使用了除法，這意味著會消耗一些處理器週期以換取更高的精確度和更小的查表尺寸（程式碼空間）。透過將除法最佳化為位移（如前面的正弦查表所示），可以避免除法，但這會使插值函式依賴於查表資料。如果有多個查表，可能需要多個插值函式或一個帶有引數的函式來描述位移值。這會使程式碼更難閱讀，並使資料和程式碼之間的聯絡更加脆弱。

從效能最佳化的視角來看，本文探討瞭如何避免在資源受限的嵌入式系統中進行耗時的浮點數運算，特別是針對除法和正弦函式的計算。文章分析了使用近似乘法替代除以 6 的方法，以及利用查表法和線性插值法計算正弦函式的技巧。對於除法，選擇合適的乘數和位移量能有效提升效率，但需要預先確定除數。查表法在計算速度上表現出色，但需要平衡記憶體空間和精確度。線性插值法能進一步提升查表法的精確度，但引入了除法運算，需要權衡效能損耗。技術限制深析顯示，這些方法並非適用所有場景，例如近似乘法不適用於動態除數，查表法需要額外記憶體，而線性插值法則增加了計算複雜度。對於重視效能的嵌入式系統開發者，建議根據具體應用場景選擇合適的最佳化策略，例如，在記憶體允許的情況下，查表法結合線性插值能取得良好的精確度和效能平衡。玄貓認為，隨著嵌入式系統硬體效能的提升和編譯器最佳化技術的發展，未來這些近似計算方法仍將持續演進，在功耗、效能和程式碼複雜度之間取得更佳的平衡。