在 int 溢出附近进行计算的聪明方法

Question

有什么聪明的方法可以解决这个问题吗？

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 takes 0.086669 seconds, du is 57333
float takes 0.017779 seconds, du is 57333

Answer 1

这个怎么样？

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

请参阅https://godbolt.org/g/aemCyw 了解gcc 为此操作生成的程序集和溢出的原始c = a * 100000 / b。请注意，使用 __aeabi_uldivmod 而不是 __aeabi_uidiv。

Answer 2

当 64 位数学计算成本很高时，有时仅 32 位的近似解可能会快得多。取决于 processor/compiler.

让我们看看仅使用 32 位数学可以做什么。

b == 100000 == 0x186A0 让我们假设它是固定的 - 一个 17 位数。

a == 16637510 == 0x00FDDE46，但 OP 说它在 +/- 1000 以内。所以它是一个 24 位数字。 b 是一个 26 位数。有了这些限制，最后的商将始终在 36464 附近（一个 16 位数）

我们可以缩放乘积操作数 a,b 以使用 a 的 16 位左右的有效位和 b 的 16 位左右的最高位，而不会失去太多意义。然后我们有一个不会溢出 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;
}

如果这个 faster/better 为 OP？可能是。只是要考虑的另一种方法。我将把它留给用户内联以进行性能分析。

在 int 溢出附近进行计算的聪明方法

smart way to do calculation near int overflow

c

integer-overflow