智能的方式来做近似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溢出计算

回答

相关问题