智能的方式來做近似int溢出計算

有沒有什麼聰明的方法來解決這個問題？智能的方式來做近似int溢出計算

uint32_t a = 16637510; 
uint32_t b = 45627362; 
uint32_t c = 0; 
c = a * 100000/b //overflows 
c = (a * 100/b)*1000 //gives 36000

我需要得到結果c = 36463或更好36464.並且需要快速，非浮動操作。 CPU是STM32F4

更新：

接受的答案被轉換爲100000〜100000ULL（64位），但作爲@PeterJ建議（和刪除他的回答）使用STM32F4 FPU是更快然後除以64點的操作

Timer t; 
int i; 
t.start(); 
for(i = 1; i <= 100000; ++i) c = a * 100000ULL/b; 
t.stop(); 
printf("64\ttakes %f seconds, du is %d\n", t.read(), c); 
t.reset(); 
t.start(); 
for(i = 1; i <= 100000; ++i) c = (uint32_t)((float)a * 100000.0f/(float)b); 
t.stop(); 
printf("float\ttakes %f seconds, du is %d\n", t.read(), c); 
t.reset();

64需要0.086669秒，杜是57333
浮子需要0.017779秒，杜是57333

來源

2017-07-06 luzik

不用擔心。你不喜歡它 - 我把它刪除:) –

只有大概的32位數學解決方案存在。 'a，b'的範圍是什麼？什麼是容忍誤差（+/- 1？） – chux

溢出有多常見？他們是一個例外，還是他們發生在每個數據集？ – ensc

這個怎麼樣？

c = a * 100000ULL/b; // gives 36463

對於GCC生成用於該操作，並且溢出的原始c = a * 100000/b組裝參見https://godbolt.org/g/aemCyw。請注意，使用__aeabi_uldivmod代替__aeabi_uidiv。

來源

2017-07-06 17:53:55 Tim

原始代碼a取自輸入捕捉TIM，所以它應該保持32.我會做一些速度測試來比較64位分區與你的浮點版本 – luzik

當64位數學運算很昂貴時，有時32位唯一近似解決方案可能會顯着更快。取決於處理器/編譯器。

讓我們看看只用32位數學可以做什麼。

b == 100000 == 0x186A0並讓我們假設它是固定的 - 一個17位數字。

a == 16637510 == 0x00FDDE46，但OP表示它在+/- 1000以內。所以它是一個24位數字。 b是一個26位數字。有了這些限制，最終商總是會在36464附近（16位數字）

我們可以分的產品操作數a,b使用16個左右的a和顯著位16左右的b最顯著位而不會失去太多意義。然後我們有一個不會溢出32位數學的16位* 16位產品。

我們可以利用b僅有12位有效位，使代碼最多可以使用產品中24位a的20位（32-12）最高有效位。

中間產品是41位，所以我們需要將乘法縮減至少9位。

#define SCALE_A 4 
#define SCALE_M 5 
// Insure SCALE_A + SCALE_M >= 9 to avoid overflow 
// Perhaps other scales like SCALE_A 8, SCALE_M 1 will be faster. 

uint32_t scale(uint32_t a, uint32_t b) { 
    uint32_t product = (a >> SCALE_A)*(100000 >> SCALE_M); 
    uint32_t c = product/(b >> (SCALE_A + SCALE_M)); 
    return c; 
}

如果OP更快/更好？也許。簡單的另一種方法來考慮。我將留給用戶使用，以便進行性能分析。

來源

2017-07-06 20:16:04 chux

使用'（uint16_t）（a >> 8）*（100000 >> 1） '可能允許使用16 * 16到32位乘法作爲發射碼。 – chux

智能的方式來做近似int溢出計算

回答

相關問題