我想将两个小数长度不同的定点数相乘。 定点部分和小数部分分开存储:
123 . 4
fix . frac
sint32 . sint32
我使用两个变量，一个用于固定部分，一个用于小数部分。
我尝试使用 Karatsuba 算法。但是这个只适用于固定长度的小数。这两个数字的小数部分是不同的。它们可能是相同的，但对此有任何保证。 当然，最大可能值为 (2^32) - 1。
123.4 乘以 56.789 的最佳方法是什么？
// a = 123.4
signed int a_fxd = 123;
signed int a_frx = 4;
// b = 56.789
signed int b_fxd = 56
signed int b_frc = 789;
最佳答案
您需要决定小数部分的实际比例因子是多少。对于您的特定示例，看起来合适的因子可能是 1/1000 或 0.001。这意味着 56.789 表示为 56 + 789 × 0.001。但这意味着 123.4 将表示为 12 + 400 × 0.001。也就是说，您的问题有误:a_frx 将是 400，而不是 4。
我不知道Karatsuba's algorithm ，而且我怀疑它并不真正适用于这个问题。我只知道我在小学赚了多少。
让我们用sc 表示比例因子。所以我们的乘法其实是
( a_fxd + a_frx * sc ) * ( b_fxd + b_frx * sc )
乘以这个，我们得到
a_fxd * b_fxd + a_fxd * b_frx * sc + a_frx * b_fxd * sc + a_frx * b_frx * sc * sc
收集术语，我们有
a_fxd * b_fxd + (a_fxd * b_frx + a_frx * b_fxd + a_frx * b_frx * sc) * sc
因此，如果我们将产品表示为 p_fxd 和 p_frx，看起来我们会有
p_fxd = a_fxd * b_fxd
p_frx = a_fxd * b_frx + a_frx * b_fxd + a_frx * b_frx * sc
让我们插入实际值:
p_fxd = 123 * 56 = 6888
p_frx = 123 * 789 + 400 * 56 + 400 * 789 * 0.001 = 119762.600
但是还有一个问题，因为 p_frx 实际上应该是 0..999 范围内的整数。所以我们需要舍弃.600，携带119。所以我们最终的结果是
p_fxd = 6888 + 119 = 7007
p_frx = 762
这对应于正确的结果，123.4 × 56.789 = 7007.762。
...好吧，实际上，正确正确的结果是 7007.7626，或四舍五入到三位数，7007.763。所以严格来说，我们不应该丢弃我们在 p_frx 中得到的 .600，我们应该四舍五入。
当我们考虑负数的可能性时，可能还有一些额外的问题需要处理。
最后，是比例因子的选择。实际上，我在这里使用的 0.001 并不是一个实际值。对于通用算法，您可能会使用更像 1/10000、1/1000000000、1/32768、1/65536 或类似的东西。 (使用 2 的幂可以实现更大的范围和通常更有效的计算，但小数部分不太明显，并且与十进制表示的转换效率较低。例如，如果您使用 1/32768 的比例因子，a_frx 将是 13107，b_frx 将是 25853 或 25854。)
关于c - 如果固定部分和小数部分分开存储，如何将定点数相乘？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58622209/