最有效地利用定點的Sqrt

我做什麼，我認爲是一個很好的fixed-point square root algorithm：最有效地利用定點的Sqrt

template<int64_t M, int64_t P> 
typename enable_if<M + P == 32, FixedPoint<M, P>>::type sqrt(FixedPoint<M, P> f) 
{ 
    if (f.num == 0) 
     return 0; 
    //Reduce it to the 1/2 to 2 range (based around FixedPoint<2, 30> to avoid left/right shift branching) 
    int64_t num{ f.num }, faux_half{ 1 << 29 }; 
    ptrdiff_t mag{ 0 }; 
    while (num < (faux_half)) { 
     num <<= 2; 
     ++mag; 
    } 

    int64_t res = (M % 2 == 0 ? SQRT_32_EVEN_LOOKUP : SQRT_32_ODD_LOOKUP)[(num >> (30 - 4)) - (1LL << 3)]; 
    res >>= M/2 + mag - 1; //Finish making an excellent guess 
    for (int i = 0; i < 2; ++i) 
     //       \ | /
     //        \ |/
     //        _| V L 
     res = (res + (int64_t(f.num) << P)/res) >> 1; //Use Newton's method to improve greatly on guess 
     //        7 A r 
     //       /| \ 
     //       / | \ 
     //      The Infamous Time Eater 
    return FixedPoint<M, P>(res, true); 
}

然而，剖析（在釋放模式）後，我發現該師在這裏佔據了83％的時間內，該算法花費。我可以通過用乘法替換該分區來加速6倍，但這是錯誤的。不幸的是，我發現整數除法比乘法慢得多。有什麼辦法可以優化嗎？

如果此表是必要的。

const array<int32_t, 24> SQRT_32_EVEN_LOOKUP = { 
    0x2d413ccd, //magic numbers calculated by taking 0.5 + 0.5 * i/8 from i = 0 to 23, multiplying by 2^30, and converting to hex 
    0x30000000, 
    0x3298b076, 
    0x3510e528, 
    0x376cf5d1, 
    0x39b05689, 
    0x3bddd423, 
    0x3df7bd63, 
    0x40000000, 
    0x41f83d9b, 
    0x43e1db33, 
    0x45be0cd2, 
    0x478dde6e, 
    0x49523ae4, 
    0x4b0bf165, 
    0x4cbbb9d6, 
    0x4e623850, 
    0x50000000, 
    0x5195957c, 
    0x532370b9, 
    0x54a9fea7, 
    0x5629a293, 
    0x57a2b749, 
    0x59159016 
};

SQRT_32_ODD_LOOKUP只是SQRT_32_EVEN_LOOKUP通過sqrt(2)分。

來源

2016-03-18 user155698

如果您包含像C++ –

這樣的編程語言標記，則需要更多地關注此問題請嘗試[sqrt by binary search without multiplication]（http://stackoverflow.com/a/34657972/2521214）到你的固定點（應該只是一個改變LUT值的問題）我認爲它應該更快，但你需要在你的平臺上測量 – Spektre

[快速定點功率，日誌，exp和sqrt]（http：// stackoverflow。 com/q/4657468/995714），[尋找ARM Thumb2的有效整數平方根算法]（http://stackoverflow.com/q/1100090/995714） –

重新發明輪子，真的，而不是一個好方法。正確的解決方法是使用NR計算1/sqrt(x)，然後乘一次得到x/sqrt(x) - 只需預先檢查x==0。

之所以這麼好是因爲y=1/sqrt(x)的NR步驟只是y = (3y-x*y*y)*y/2。這是直接的乘法。

來源

2016-03-18 09:24:41 MSalters

我認爲應該是'y =（3 - x * Y * Y）* Y/2'。 – user155698

感謝您的提示。我最初認爲這是行不通的，因爲倒數平方根將在1的另一邊（對於FixedPoint <2, 30>'或FixedPoint <32, 0>'非常不好）。然而，使用'y =（3-x * y * y/C^2）* y/2'來抵消逆平方根以得到在2^29和2^31之間的'y'。這個算法比舊算法精確一點，但速度提高了3倍。 – user155698

@ user155698：您可以使用第4個NR步驟，速度仍然快2倍。 – MSalters

最有效地利用定點的Sqrt

回答

相關問題