高效(循环)算法计算模25？

Question

我有一个代码,我在其中计算x%25.x总是取正值但其动态范围很大.

我发现这个计算轴%25的特殊代码片段需要大周期.我需要优化它.

由于表可能存在大的内存大小,因此排除了预先计算的查找表.

作为第二种方法,我在下面编码了一个片段(C代码) -

mod(a, b)
{   
    int r = a;  
    while(r >= b)
    {      
        r = r - b;
    }   
    return r;
}

1.)如何针对周期进一步优化此代码(将其压缩到最大值)？

2.)是否有任何完全不同的优化方式来实现x%25(我知道它不是一个常见的操作,但仍然,寻找人们可能在他们的经验中使用的聪明输入,这可能会让我感到麻烦.).

谢谢.

-广告

编辑:

我认为在C中使用本机模运算符%,内部使用除法运算(/),这在我正在使用的处理器上是昂贵的.(没有div指令).因此,尝试查看自定义实现是否可以使用%运算符击败固有计算.

-广告

Answer 1

我建议阅读Hacker's Delight.它描述了常数除数的非常快的余数算法.他们几乎肯定会击败一般算法.

更新:这是一些示例代码...它可能可以重做以避免临时长时间.

unsigned mod25(unsigned n)
{
    unsigned reciprocal = 1374389535; // 2^35 / 25
    unsigned div25 = ((unsigned long long)n * reciprocal) >> 35;
    return n - div25 * 25;
}

Answer 2

这是我提出的另一个解决方案:

int mod25(int x){
  /* 25 * (all powers of 2 <= INT_MAX), descending */
  if (x >= 1677721600) x -= 1677721600;
  if (x >=  838860800) x -=  838860800;
  if (x >=  419430400) x -=  419430400;
  if (x >=  209715200) x -=  209715200;
  if (x >=  104857600) x -=  104857600;
  if (x >=   52428800) x -=   52428800;
  if (x >=   26214400) x -=   26214400;
  if (x >=   13107200) x -=   13107200;
  if (x >=    6553600) x -=    6553600;
  if (x >=    3276800) x -=    3276800;
  if (x >=    1638400) x -=    1638400;
  if (x >=     819200) x -=     819200;
  if (x >=     409600) x -=     409600;
  if (x >=     204800) x -=     204800;
  if (x >=     102400) x -=     102400;
  if (x >=      51200) x -=      51200;
  if (x >=      25600) x -=      25600;
  if (x >=      12800) x -=      12800;
  if (x >=       6400) x -=       6400;
  if (x >=       3200) x -=       3200;
  if (x >=       1600) x -=       1600;
  if (x >=        800) x -=        800;
  if (x >=        400) x -=        400;
  if (x >=        200) x -=        200;
  if (x >=        100) x -=        100;
  if (x >=         50) x -=         50;
  if (x >=         25) x -=         25;
  return x;
}

这不使用除法或乘法,只有27次比较,最多27次减法.

要说服自己这样做有点困难,但确实如此(至少对于x的非负值).

上面的代码实际上是这个展开的版本:

int mod25(int x){
  int divisor;
  for(int divisor = 1677721600; divisor >= 25; divisor >>= 1) {
    if (x >= divisor) x -= divisor;
  }
  return x;
}

通过展开它,我们避免进行循环比较以及更换代码的代价.你甚至可以使用Duff的设备部分展开它,如果你觉得如此倾向,但总共只有27次迭代,而且每次迭代的代码都很少,我倾向于一直展开它.

以下是它的工作原理:每个非负整数x可以表示为(n*25)+ k,其中n是非负整数,k是0到24之间的整数.k也恰好是我们想要的结果,所以,如果我们可以计算x - (n*25),我们就会得到答案.不过,我们希望能够在不知道n的情况下做到这一点.

想想二进制中的n.如果我们可以关闭我们得到的1位中的每一位.一种方法是从2的大功率开始并向下工作,只有当n的当前值大于2时才减去2的每个幂.或等于2的幂.

由于我们处理(n*25),我们实际上需要2次25的递减次幂.因为k严格小于25,并且我们考虑的最小除数是25,所以即使我们处理时也是如此(n*25)+ k.

所以每次比较+减法都将n的一位归零,最后我们留下k,余数.

Answer 3

因为你想要模数一个常数,你可以通过使用倒数乘法来击败它.本文展示了如何以这种方式除以常数,并最终如何从中得到余数.

Answer 4

我受到了Pax的回答的启发,并制作了一个更通用的算法.

int mod(int a, int b) {
    int s = b;
    while (s <= a) {
        s <<= 1;
    }
    int r = a;
    while (r >= b) {
        s >>= 1;
        if (s <= r) {    
            r -= s;
        }
    }
    return r;
}

这减去二的倍数的动力b来自a直到结果被发现.

编辑:添加if条件,使其正常工作.

例如,如果这是100%7,它首先计算7*2*2*2*2 = 112.然后它将112(s)除以2并从100(r)(何时s <= r)减去它并且不断地做这直到找到模数.因此,

s = 112 / 2 = 56, r = 100 - 56 = 44
s = 56 / 2 = 28, r = 44 - 28 = 16
s = 28 / 2 = 14, r = 16 - 14 = 2

因此,100%7 = 2

Answer 5

这是我能想到的最好的:

int mod25(int x)
{
    while((x = (x & 31) + 7 * (x >> 5)) >= 25)
        x -= 25;

    return x;
}

它近似x % 25与x % 32 + 7 * (x/32).该值将超过倍数25,这允许递归.

性能似乎是足够的:x = 2147483647(aka INT_MAX)的值需要11次迭代.

Answer 6

哦,我的<选择的神灵>.我无法相信其中的一些答案.

首先,重复减法,即使是Pax的版本,也永远不会是最佳的.考虑以下:

20 % 25

使用重复减法简单快捷,但是:

65535 % 25

将会非常缓慢,600多次迭代.这是16位数的平均300次迭代.至于32位数,好吧,甚至不去那里.

最快的方法是使用长除法.见尼基的回答.

但是,这就是编译器将要生成的东西,至少,人们希望它是编译器生成的东西.最好检查一下您是否正在使用编译器来获取利基处理器.

加快这一速度的最好方法是首先不要模数.为什么需要获得模数,并且可以重新分解代码/算法以避免模数,或者至少使模数变得微不足道.

Answer 7

循环的问题在于它是O(n) - 对于大的r值,它会非常慢.我建议这样的事情:

for (int s = MAX_SHIFT; s>=0; s--)
  if (r > (b<<s)) r -= (b<<s);

但我怀疑你的编译器正在做比这更昂贵的事情.