你好! 我陷入了对模幂运算概念的了解.当我需要它以及它如何工作时. 假设我将幂函数调用为: power(2,n-1). n = 10
Hello! I am getting stuck in understanding the concept of modular Exponentiation. When i need this and how this works. Suppose i am calling the power function as : power(2,n-1). How the loops will be executed for say n=10
#define m 1000000007 unsigned long long int power(unsigned long long int x, unsigned long long int n){ unsigned long long int res = 1; while(n > 0){ if(n & 1){ res = res * x; res = res % m; } x = x * x; x= x % m; n >>= 1; } return res; }
推荐答案
从DAle链接的Wikipedia页面上的模定律(关于您的上一个问题),我们可以获得两个公式:
From the modulo laws on DAle's linked Wikipedia page (on your previous question), we can obtain two formulas:
根据第一个公式,很明显,我们可以根据n / 2的结果迭代地计算n的模数.这是通过线条完成的
From the first formula it is clear that we can iteratively calculate the modulo for n from the result for n / 2. This is done by the lines
x = x * x; x = x % m;因此,算法中有log n个步骤,因为每次x的指数加倍.步数计数由n >>= 1和while (n > 0)完成,它们对log n步数进行计数.
There are thus log n steps in the algorithm, because each time the exponent of x doubles. The step counting is done by n >>= 1 and while (n > 0), which counts log n steps.
现在,您可能想知道1)为什么这部分没有设置res的值,以及2)这些行的目的是什么
Now, you may be wondering 1) why doesn't this part set the value of res, and 2) what is the purpose of these lines
if(n & 1){ res = res * x; res = res % m; }这是必要的,因为在迭代的某些点,无论是开始还是结束,n的值都可能是奇数.我们不能只是忽略它,而是继续使用公式1,因为这意味着我们将跳过的力量为x! (整数除法是四舍五入的,例如5 >> 1 = 2,我们将使用x^4而不是x^5).如果n为奇数(即n % 2 = n & 1 = 1),则此if语句处理情况.它只是使用上面的公式2来将x的单次幂加"到结果中.
This is necessary as at certain points in the iteration, be it the start or the end, the value of n may be odd. We can't just ignore it and keep using formula 1, because that means we would skip a power of x! (Integer division rounds down, so e.g. 5 >> 1 = 2, and we would have x^4 instead of x^5). This if statement handles the case when n is odd, i.e. n % 2 = n & 1 = 1. It simply uses formula 2 above to "add" a single power of x to the result.
更多推荐
模幂(模运算中的幂)
发布评论