首页 > 其它语言 > 算法之运算 模的指数运算

算法之运算 模的指数运算

模的指数运算

  • 真言

家人万岁,亲情万岁。

  • 引言

哎呀,放假了,回家了,村里建设挺好哈,晚上大娘婶婶出来跳舞了,我还在coding,有鸡叫的日子真好,喜欢农村,I‘m a 农民,还不是村干部!

  • 模的指数运算
原来模的功能是这么的强大,以前没有太在意它,实在是愧疚呀。模赋予了单位很大的意义,使得大数据可以被我们处理,这就是我对模的理解。
问题定义:给定x和y,计算x的y次方模N的值,其中N有数百位长。
算法如下(递归的算法)
原理如下

  • 实验

  • 代码
    • 只要算法是递归的,我都会在转换成非递归的算法,同时给大家。
    • test1.cpp
    • [cpp] view plaincopy

      1. #include<iostream>
      2. #include<stack>
      3. using namespace std;
      4. // function modexp in recursion
      5. int modexp_re(int x,int y,int N);
      6. // function modexp without recursion
      7. int modexp_nonre(int x,int y,int N);
      8. int const N = 10000 ;
      9. // function main
      10. int main()
      11. {
      12.     int a,b,i = 0;
      13.     while(i < 100)
      14.     {
      15.         a = rand()%10000;
      16.         b = rand()%10000;
      17.         cout<<"a="<<a<<" , b="<<b<<" , N ="<<N<<" , modexp_re = "<<modexp_re(a,b,N)<<endl;
      18.         cout<<"a="<<a<<" , b="<<b<<" , N ="<<N<<" , modexp_nonre = "<<modexp_nonre(a,b,N)<<endl;
      19.         i++;
      20.     }
      21.     system("pause") ;
      22.     return 0 ;
      23. }
      24. // function modexp in recursion
      25. int modexp_re(int x,int y,int N)
      26. {
      27.     // exception
      28.     if(N <= 0)
      29.     {
      30.         cout<<"exception of function modexp_re input N "<<endl;
      31.         return -1;
      32.     }
      33.     // exit
      34.     if(y == 0)
      35.         return 1;
      36.     else
      37.     {
      38.         int z = modexp_re(x,y/2,N);
      39.         if(y%2 == 0)
      40.             return ( (z%N) * (z%N) ) % N;
      41.         else return ((((x%N) * (z%N)) %N) *(z%N) )% N;
      42.     }
      43. }
      44. // function modexp without recursion
      45. int modexp_nonre(int x,int y,int N)
      46. {
      47.     // exception
      48.     if(N <= 0)
      49.     {
      50.         cout<<"exception of function modexp_re input N "<<endl;
      51.         return -1;
      52.     }
      53.     // exit
      54.     if(y == 0)
      55.         return 1;
      56.     else
      57.     {
      58.         int result,z;
      59.         stack<int> * s = new stack<int>;
      60.         while(y >= 1)
      61.         {
      62.             s->push(y);
      63.             y = y/2;
      64.         }
      65.         result = x % N;
      66.         while(s->size()>1)
      67.         {
      68.             z = s->top();
      69.             s->pop();
      70.             result = ( (result%N) * (result%N) )%N;
      71.             if(s->empty())
      72.                 break;
      73.             else if(z*2 != s->top())
      74.             {
      75.                 result = (result * (x%N) )%N;
      76.             }
      77.         }
      78.         return result;
      79.     }
      80. }

本文固定链接: http://www.devba.com/index.php/archives/4473.html | 开发吧

报歉!评论已关闭.