c++ - 在定点类型上实现模数

Question

所以目前我正在帮助开发一种编程语言，我们已经到了必须使用 C++ 作为我们的主干语言来实现定点类型来编写它的地步。我能够弄清楚如何添加，减法，乘法，除法，但是对于如何实现模数和指数，我正在画一个空白。我觉得我快要算出指数了，所以我会把这个问题集中在模数上。

目前我所做的是接收一个字符串文字并跟踪基数的点并找到它与字符串末尾的距离，这给了我我的比例因子。之后我们保留整个大整数，它应该被限制为固定类型(除非出现诸如除法......或模数之类的情况，此时我们将基数的小数边增加到至少一半整数部分)。我已经实现了通过乘以 10 的因子来获取基数左侧和基数右侧的值的方法(我想要基数 10 的精度而不是基数 2 的速度)以获得位置基数会坐下。我在谷歌上搜索了如何在定点类型上实现模数，但无济于事。

我似乎无法弄清楚如何实现它。有没有办法实现这个？人们知道广义算法吗？有什么可以指出我正确的方向吗？请记住，我的目标是准确性。速度也不错，但首要的是准确性。

澄清一下，我们要操作的硬件是通用的。至于我想要什么的定义……这就是我来这里的原因。我不知道我想要什么，我想知道一些例子和不同的选择。真的，我只是想了解一下。

示例:

假设我有一个固定的 8x8 并且我推出 2 % 1.2(这里 2 也可能是 2.0)，结果应该返回 0.8。扩展右侧的大小以补偿准确性的好的规则是什么？

Answer 1

修正为 1.2 % 2 == 1.2，则忽略小数，例如这与 12 % 20 == 12 相同

如果确实不需要速度，您可以只使用减法来计算。例如。对于任何 A % M，只需从 A 中减去 M 直到 A < M，因为 M != 0(无限循环!)。这将提供相同的结果 1.2，因为当表示为定点时，减法实际上不受小数点的影响。

如果速度很重要，并且您没有可以忽略小数点的乘法例程(大多数不会)，您可能需要构建它们，因为在 8x8 时，您没有足够的空间将整个值移入左侧(对于某些操作，我在我的 PIC 16F 库中实现了 24x8 定点寄存器，以便在对 16x8 定点执行计算时允许更高的精度)。

详细说明使用乘法进行更快的算术运算，以及您需要可以忽略小数的乘法例程的原因，

首先，我们使用伪 C++ 代码分析较慢的减法方法:

auto answer = A;
while(answer >= M)
  answer -= M;
// now, your answer is in answer

但如果我们事先知道需要多少次迭代，我们就可以:

auto answer = A - M * number_of_iterations;

当然，我们不会知道，所以我们的目标是减少我们需要的迭代次数。这可以通过反向分解来完成——给定一个数字 M，找出你可以将它乘以 10 多少次(左边一位数字)并且它仍然小于 A，例如如果A为1023.32，M为4.1，则可以将M乘以10两次，得到M*10*10 = 410。用A减去A，直到A < M*10*10，A'=203.32，继续重复直到你的 A 的工作拷贝小于 M。这种方法通常将 O(N) 操作转换为 O(log(N)) 操作，前提是你不增加太多的计算开销(在我的 PIC 16F 中实现，我必须小心，因为芯片只有 384 字节的总内存，所以不用说，它比它应该的要慢)。

我的大部分工作都是以 2 为基数进行的，但同样的想法也适用于以 10 为基数，所以像这样的东西应该会大大减少迭代次数，尤其是对于较大的项目(这可以根据你的情况进行调整内部表示，因此您可以对每个步骤使用数字移位而不是乘法):

auto currentA = A;
while(currentA >= M){
  auto scaledM = M;
  while(scaledM*10 < currentA)
    scaledM *= 10;
  // this second loop prevents recomputing scaledM where
  // currentA > n*scaledM for some n < 10; not needed in base-2
  while(currentA > scaledM)
    currentA -= scaledM;
}

完成后 currentA 将包含您的模数。