C编程中的不动点算法
我正在尝试创建一个高精度存储股票价格的应用程序。 目前我正在使用双倍这样做。 为了节省内存，我可以使用任何其他数据类型吗？ 我知道这与定点运算有关，但我无法弄明白。
定点运算背后的想法是存储值乘以一定量，使用所有微积分的相乘值，并在需要结果时将其除以相同的量。 此技术的目的是使用整数算术（int，long …），同时能够表示分数。
在C中执行此操作的通常且最有效的方法是使用位移运算符（<<和>>）。 对于ALU来说，移位是一个非常简单和快速的操作，并且这样做具有在每个移位上将整数值乘以（<<）和除（>>）2的特性（此外，可以完成相同的许多移位）一个人的价格）。 当然，缺点是乘数必须是2的幂（这通常不是问题，因为我们并不真正关心那个精确的乘数值）。
现在假设我们想使用32位整数来存储我们的值。 我们必须选择2倍乘数。 让我们将蛋糕分成两部分，所以说65536（这是最常见的情况，但你可以真正使用2的任何幂，这取决于你的精度需求）。 这是2 16 ，这里的16意味着我们将使用16个最低有效位（LSB）作为小数部分。 其余部分（32 – 16 = 16）用于最高有效位（MSB），即整数部分。
integer (MSB) fraction (LSB) vv 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内置浮点运算：
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的数量（这里没有真正的陷阱，这是非常明显的）。 不要使用simple long，因为sizeof（long）可以等于sizeof（int）。 如果int为32位，则使用long long ，因为long long保证最小为64位（或者使用int64_t，int_least64_t等，在stdint.h中声明）。 换句话说，使用两倍于定点类型的类型，这是公平的。 最后，如果您无法访问> = 64位类型，可能是时候进行模拟，至少对于您的输出。
这些是定点算术背后的基本思想。
小心负值。 有时它会变得棘手，尤其是在显示最终价值的时候。 此外，C是关于有符号整数的实现定义（即使现在这个问题的平台非常罕见）。 您应该始终在您的环境中进行最少的测试，以确保一切按预期进行。 如果没有，如果你知道你做了什么，你可以解决它（我不会在此发展，但这与算术移位与逻辑移位和2的补码表示有关）。 但是，对于无符号整数，无论你做什么，你都绝对安全，因为无论如何行为都是明确定义的。
另请注意，如果32位整数不能表示大于2 32 - 1的值，则使用2 16的定点运算会将范围限制为2 16 - 1！ （并用签名整数将所有这一切除以2，在我们的例子中，我们的可用范围为2 15 - 1）。 然后目标是选择适合该情况的SHIFT_AMOUNT。 这是整数部分幅度和分数部分精度之间的权衡。
现在有了真正的警告：这种技术绝对不适合精确度最高的领域（金融，科学，军事......）。 通常浮点（浮点/双点）通常也不够精确，即使它们具有比定点整体更好的属性。 无论值如何，定点具有相同的精度（在某些情况下这可能是一个优势），其中浮点精度与值幅度成反比（即，幅度越低，得到的精度越高......嗯，这比这更复杂，但你明白了。） 浮点数的幅度也大于等效（位数）整数（定点与否），以及高值精度损失的成本（甚至可以达到增加1甚至更高的精度）更大的值根本没有效果，这是整数不可能发生的事情。
如果你在那些敏感的领域工作，你最好使用专用于任意精度目的的库（去看看gmplib ，它是免费的）。 在计算科学中，实质上，获得精确度大约是用于存储值的位数。 你想要高精度？ 使用位。 就这样。
我看到了两个选项。 如果您在金融服务行业工作，那么您的代码可能会遵守标准，以确保精度和准确性，因此无论内存成本如何，您都必须遵循这些标准。 我知道该业务通常资金充足，因此支付更多内存应该不是问题。 🙂
如果这是供个人使用，那么为了获得最大精度，我建议您使用整数并在存储之前将所有价格乘以固定因子。 例如，如果你想要的东西准确到便士（可能不够好），将所有价格乘以100，这样你的单位实际上是美分而不是美元，并从那里开始。 如果你想要更高的精度，请乘以更多。 例如，准确到百分之一分（我听说过的标准是常用的），将价格乘以10000（100 * 100）。
现在有了32位整数，乘以10000几乎没有留下大量美元的空间。 实际的32位限制为20亿意味着只能表达高达20000美元的价格：2000000000/10000 = 20000.如果你将20000乘以某种东西会变得更糟，因为可能没有空间来保存结果。 因此，我建议使用64位整数（ long long ）。 即使您将所有价格乘以10000，仍然有足够的空间来保持较大的价值，即使在乘法中也是如此。
固定点的技巧是，无论何时进行计算，您都需要记住每个值实际上是一个基础值乘以一个常量。 在加或减之前，需要将值乘以较小的常量以匹配具有较大常量的值。 在你乘以之后，你需要除以某个东西以使结果回到乘以所需的常数。 如果你使用2的非幂作为常数，则必须进行整数除法，这在时间上是昂贵的。 许多人使用两个幂作为常数，因此他们可以转而不是分裂。
如果这一切看起来很复杂，那就是。 我认为最简单的选择是使用双打并在需要时购买更多内存。 它们具有53位精度，大约为9千万亿，或几乎16位十进制数。 是的，当你与数十亿人合作时，你仍然可能会失去便士，但如果你关心这一点，那么你就不是正确的亿万富翁。 🙂
如果您的唯一目的是节省内存，我不建议您这样做。 价格计算中的错误可以累积，你会搞砸它。
如果你真的想要实现类似的东西，你可以只采用价格的最小间隔，然后直接使用int和整数运算来操纵你的数字？ 您只需在显示时将其转换为浮点数，这将使您的生活更轻松。