c - C编程中的定点算法

Question

我正在尝试创建一个可以高精度存储股票价格的应用程序。目前，我正在使用double。为了节省内存，我可以使用其他任何数据类型吗？我知道这与定点算法有关，但我无法弄清楚。

Answer 1

定点算术背后的想法是，您将乘以一定数量的值存储起来，对所有微积分使用乘后的值，并在需要结果时将其除以相同的数量。该技术的目的是使用整数算术(int，long ...)，同时能够表示分数。

在C中执行此操作的最常用且最有效的方法是使用移位运算符(<<和>>)。对于ALU而言，移位位是一种非常简单，快速的操作，并且具有将整数值乘以(<<)并除以(>>)在每个移位时将其除以2的属性(此外，对于完全相同的移位可以进行许多移位)价格单)。当然，缺点是乘数必须是2的幂(通常，这本身就不是问题，因为我们并不真正在乎那个确切的乘数值)。

现在，我们要使用32位整数存储值。我们必须选择2乘方的幂。让我们将蛋糕一分为二，例如65536(这是最常见的情况，但是您可以根据精度的需要使用2的任意幂)。这是216，这里的16表示我们将对小数部分使用16个最低有效位(LSB)。其余部分(32-16 = 16)用于最高有效位(MSB)，即整数部分。

     integer (MSB)    fraction (LSB)
           v                 v
    0000000000000000.0000000000000000

让我们把它放在代码中:

#define SHIFT_AMOUNT 16 // 2^16 = 65536
#define SHIFT_MASK ((1 << SHIFT_AMOUNT) - 1) // 65535 (all LSB set, all MSB clear)

int price = 500 << SHIFT_AMOUNT;

这是您必须存储的值(结构，数据库等)。请注意，即使当今大多数情况下，int在C语言中也不一定是32位。同样，在没有进一步声明的情况下，默认情况下也会对其进行签名。您可以将unsigned添加到声明中以确保。更好的是，如果您的代码高度依赖整数位大小(可以引入一些技巧)，则可以使用uint32_t或uint_least32_t(在stdint.h中声明)。毫无疑问，为您的定点类型使用typedef会更安全。

要对此值进行微积分时，可以使用4个基本运算符:+，-，*和/。您必须记住，在增加和减少一个值(+和-)时，该值也必须移位。假设我们要在我们的500价格中增加10:

price += 10 << SHIFT_AMOUNT;

但是对于乘法和除法(*和/)，不得移动乘法器/除数。假设我们要乘以3:

price *= 3;

现在，通过将价格除以4来使事情变得更有趣，因此我们弥补了一个非零的小数部分:

price /= 4; // now our price is ((500 + 10) * 3) / 4 = 382.5

这就是规则。当您想在任何时候获取实际价格时，必须右移:

printf("price integer is %d\n", price >> SHIFT_AMOUNT);

如果需要小数部分，则必须将其屏蔽掉:

printf ("price fraction is %d\n", price & SHIFT_MASK);

当然，该值不是我们可以称为十进制分数的值，实际上它是[0-65535]范围内的整数。但是它与小数部分范围[0-0.9999 ...]完全对应。换句话说，映射看起来像:0 => 0，32768 => 0.5，65535 => 0.9999 ...

一种简单的将其视为小数的方法是在这一点上采用C内置的float算法:

printf("price fraction in decimal is %f\n", ((double)(price & SHIFT_MASK) / (1 << SHIFT_AMOUNT)));

但是，如果您不支持FPU(硬件或软件)，则可以使用这样的新技能来获得完整的价格:

printf("price is roughly %d.%lld\n", price >> SHIFT_AMOUNT, (long long)(price & SHIFT_MASK) * 100000 / (1 << SHIFT_AMOUNT));

表达式中的0数大约是小数点后所需的位数。在给定分数精度的情况下，不要高估0的数量(这里没有真正的陷阱，这很明显)。不要使用简单的long，因为sizeof(long)可以等于sizeof(int)。如果int为32位，请使用long long，因为long long的最小值应保证为64位(或使用stdint.h中声明的int64_t，int_least64_t等)。换句话说，使用的大小是定点类型的两倍，这很公平。最后，如果您不能访问> = 64位类型，也许是时候执行它们了，至少对于您的输出而言。

这些是定点算术背后的基本思想。

小心负值。有时，这可能会变得棘手，特别是当需要显示最终值时。此外，C是关于带符号整数的实现定义的(即使如今在这方面很不常见的平台)。您应该始终在您的环境中进行最少的测试，以确保一切都按预期进行。如果没有，您可以在知道自己要做什么的情况下进行破解(我不会在此基础上发展，但这与算术移位与逻辑移位以及2的补码表示有关)。但是，对于无符号整数，无论​​如何操作，大多数情况下都是安全的，因为无论如何，行为都得到了很好的定义。

另请注意，如果32位整数不能表示大于232-1的值，则使用带有216的定点算法会将范围限制为216-1! (并用有符号整数将所有这些除以2，在我们的示例中将为我们提供215-1的可用范围)。然后的目标是选择适合该情况的SHIFT_AMOUNT。这是整数部分大小和小数部分精度之间的权衡。

现在是真正的警告:此技术绝对不适用于精度最优先的 Realm (金融，科学，军事...)。通常的浮点数(float / double)通常也不够精确，即使它们的整体性能比定点数更好。定点无论值如何都具有相同的精度(在某些情况下这可能是一个优点)，其中浮点精度与值的大小成反比(即，大小越小，您获得的精度越高...好吧，这比这更复杂，但您明白了)。浮点数的大小也要比等效的(位数)整数(无论是否定点)大得多，这会损失高值而导致精度损失的代价(您甚至可以达到加1甚至是较大的值根本没有任何作用，整数不会发生这种情况。

如果您在那些明智的 Realm 中工作，那么最好使用专门用于任意精度目的的库(请查看gmplib，它是免费的)。从本质上讲，在计算科学中，获得精度与您用于存储值的位数有关。您想要高精度吗？使用位。就这样。