高效（周期WISE）算法来计算模25？ [英] Efficient (cycles wise) algorithm to compute modulo 25?

问题描述

我有一个code，其中我正在计算x％的25点¯x始终为正值，但其动态范围大。

I have a code in which i am computing x % 25. x always takes a positive value but its dynamic range is large.

我发现了这个特殊的code片计算X％25正在大循环。我需要优化它。

I found out that this particular code piece of computing a x % 25 is taking large cycles. I need to optimize it.

$ P $对计算查找表排除因该表的可能的大的存储大小。

Pre-computed lookup table is ruled out due to the possible large memory size of the table.

由于第二种方法I codeD下方的片段（C code） -

As second approach i coded a fragment below(C code) -

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

1）如何优化这一code为进一步周期（拧到最大）？

1.) How can i optimize this code further for cycles(squeeze it to max)?

2）是否有完全不同的优化方式，实现X％25（我知道它不是一个常见的​​操作，不过，在寻找聪明的输人可能在他们的经验已经使用可能NELP我）。

2.) Is there any entirely different optimized way to achieve x % 25( i know its not a common operation, but still, looking for clever inputs people might have used in their experience which might nelp me.).

感谢您。

-AD

编辑：

我觉得用在C本地模运算符％，内部使用除法运算（/），这是我使用的处理器上昂贵的。（不派息指令）。因此，想看看是否定制实现可以用％运算符击败了固有的计算。

I think using a native modulo operator % in C , internally uses a division operation (/) which is costly on the processor i am using.(No div instruction). hence trying to see if custom implemetation can beat the inherent computation using % operator.

-AD

推荐答案

我建议您阅读黑客的喜悦。它描述了恒除数非常快剩余的算法。他们几乎肯定会击败通用算法。

I suggest reading Hacker's Delight. It describes very fast remainder algorithms for constant divisors. They would almost certainly beat a general algorithm.

更新：下面是一些例子code ...大概可以修改，以避免临时长长

Update: Here is some example code... It can probably be reworked to avoid the temporary long long.

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

这篇关于高效（周期WISE）算法来计算模25？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！