在定点类型上实现模数 [英] implementing a modulus on fixed point type

问题描述

因此，目前我正在帮助开发一种编程语言，并且我们已经达到必须使用C ++作为骨干语言来实现定点类型的程度，以便能够编写这种语言.我能够弄清楚如何添加，减去，相乘，除，但是对于如何完成模数和指数的绘制，我是一个空白.我觉得我快要找出指数了，所以我将把这个问题集中在模数上.

当前，我要做的是输入一个字符串文字并跟踪基数的点，并找到距字符串末尾的距离，这给了我缩放系数.之后，我们保留整个大整数，该整数应被约束为固定类型(除非出现除法...或可能的模数的情况，此时我们将基数的小数侧增加到大小的至少一半整数部分的整数).我已经实现了一些方法，通过乘以10来获取基数左侧和基数右侧的值(我希望以10为底的精度而不是以2为底的速度)来获得基数将坐下.我用谷歌搜索了如何在定点类型上实现模数，但无济于事.

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

为澄清起见，我们将要使用的硬件是通用的.至于我想要的定义...这就是为什么我在这里的原因.我不知道我想要什么，我想知道一些示例和不同的选择.真的，我只是想了解这一点.

示例:

说我有一个fixed8x8，我推出了2％1.2(这里也可以是2.0)，结果应该是0.8.扩展右侧尺寸以补偿精度的一条好规则是什么?

解决方案

修正为1.2％2 == 1.2，则只需忽略小数，例如这等于12％20 == 12

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

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

要详细说明如何使用乘法来加快运算速度，以及您需要可忽略小数的乘法例程的原因，

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

 自动回答= A;一会儿(answer> = M)答案-= M;//现在，您的答案就在答案中 

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

 自动回答= A-M * number_of_iterations; 

当然，我们不会知道，所以目标是减少我们需要的迭代次数.这可以通过逆分解来完成-给定数字M，找到可以乘以10(左数一位)的次数，但仍然小于A，因此例如如果A为1023.32并且M为4.1，则可以将M乘以10两次，得到M * 10 * 10 = 410.M * 10 * 10，保留A'= 203.32，并继续重复直到您的A的工作副本小于M.此转折方法通常将O(N)运算转换为O(log(N))运算，前提是您不会在计算上增加太多开销(在我的PIC 16F实现中，我必须小心，因为该芯片只有384字节的总内存，所以不用说，它比原先的速度要慢)./p>

我的工作大部分是在base-2上完成的，但是相同的想法也可以转换为base-10，因此这样的操作应该可以大大减少迭代次数，尤其是对于较大的项目(可以根据您的实际情况进行调整)内部表示法，因此您可以在每个步骤中使用数字移位而不是乘法):

 自动电流A = A;while(currentA> = M){自动缩放M = M;while(标度M * 10< currentA)标定的M * = 10;//此第二个循环阻止重新计算scaledM，其中//currentA>n * scaledM的n小于n10;在base-2中不需要而(当前A>标度M)currentA-=标度M;} 

完成后，currentA将包含您的模数.

so currently I'm helping develop a programming language, and we've reached the point where we have to implement a fixed point type using C++ as our backbone language to write this in. I am able to figure out how to add, subtract, multiply, divide, however I am drawing a blank for how to accomplish this for modulus and exponentials. I feel I am close to figuring out exponentials, so I will focus this question on modulus.

Currently what I do is I take in a string literal and track the point of the radix and find the distance of that from the end of the string, and this gives me my scaling factor. After that we keep the entire big integer, which is supposed to be constrained to a fixed type (unless circumstances like division...or possibly modulus, arise, at which point we increase the fractional side of the radix to atleast half of the size of the integer portion). I have implemented ways to grab values to the left of the radix and to the right of the radix by multiplying by factors of 10 (I want the accuracy that comes with base 10 as opposed to the speed of base 2) to get the place where the radix will sit. I have googled looking up how to implement modulus on fixed point types, to no avail.

I can't seem to figure out how one would go about implementing it. Is there a way of implementing this? Do people know of a generalized algorithm? Anything to point me in the right direction? Remember, I'm aiming for accuracy. Speed is nice too, but the prime directive is accuracy.

To clarify, the hardware we would be operating on is generalized. As for the definition of what I want...that's somewhat why I'm here. I don't know what I want, I want to know some examples and different options to choose from. Really I'm just trying to learn about this.

EXAMPLE:

say I have a fixed8x8 and I push out 2 % 1.2 (2 could be 2.0 as well here), the result should come back 0.8. What's a good rule for going about extending the size of the right side to compensate for accuracy?

解决方案

With the correction of 1.2 % 2 == 1.2, then just ignore the decimal, e.g. this is the same as 12 % 20 == 12

You can just use subtraction to compute this, if speed is truly not necessary. E.g. for any A % M, just keep subtracting M from A until A < M, for M != 0 (infinite loop!). This will provide the same result, 1.2, since subtraction really isn't affected by decimal points when represented as fixed-point.

If speed matters, and you don't have multiplication routines that can ignore the decimal (most won't), you may need to build them, since at 8x8 you won't have enough space to shift the entire value into the left-side (for some operations, I implemented 24x8 fixed point registers in my PIC 16F library to allow higher precision when performing computations on 16x8 fixed point).

To elaborate on using multiplication for faster arithmetic, and the reason you would need multiplication routines that can ignore the decimal,

First we analyze the slower subtraction approach using this pseudo-C++ code:

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

But if we knew how many iterations were necessary beforehand, we could just:

auto answer = A - M * number_of_iterations;

Of course, we won't know that, so the goal is to reduce the number of iterations that we need rather. This can be done with reverse-factorization - given a number M, find how many times you can multiply it by 10 (one digit to the left) and it still be less than A, so e.g. if A is 1023.32 and M is 4.1, you can multiply M by 10 twice, resulting in M*10*10 = 410. Subtract this from A until A < M*10*10, leaving A'=203.32, and continue to repeat until your working copy of A is less than M. This turns approach generally turns an O(N) operation into an O(log(N)) operation, provided you don't add too much overhead with the computations (in my PIC 16F implementation, I had to be careful because the chip only had 384 bytes of total memory, so needless to say, it was slower than it could have been).

I mostly did my work in base-2, but the same ideas translate to base-10 as well, so something like this should greatly reduce the number of iterations, especially for larger items (and this can be adjusted depending on your internal representation, so you can use digit-shifting rather than multiplication for each step):

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;
}

And currentA will contain your modulus when this completes.

这篇关于在定点类型上实现模数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！