算法之运算模的指数运算

孤风一剑 1月 20, 2014 179 0

模的指数运算

真言

家人万岁，亲情万岁。

引言

哎呀，放假了，回家了，村里建设挺好哈，晚上大娘婶婶出来跳舞了，我还在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;
  5. // function modexp in recursion
  6. int modexp_re(int x,int y,int N);
  7. // function modexp without recursion
  8. int modexp_nonre(int x,int y,int N);
  10. int const N = 10000 ;
  12. // function main
  13. int main()
  14. {
  15. int a,b,i = 0;
  16. while(i < 100)
  17. {
  18. a = rand()%10000;
  19. b = rand()%10000;
  20. cout<<“a=”<<a<<” , b=”<<b<<” , N =”<<N<<” , modexp_re = “<<modexp_re(a,b,N)<<endl;
  21. cout<<“a=”<<a<<” , b=”<<b<<” , N =”<<N<<” , modexp_nonre = “<<modexp_nonre(a,b,N)<<endl;
  22. i++;
  23. }
  24. system(“pause”) ;
  25. return 0 ;
  26. }
  28. // function modexp in recursion
  29. int modexp_re(int x,int y,int N)
  30. {
  31. // exception
  32. if(N <= 0)
  33. {
  34. cout<<“exception of function modexp_re input N “<<endl;
  35. return -1;
  36. }
  37. // exit
  38. if(y == 0)
  39. return 1;
  40. else
  41. {
  42. int z = modexp_re(x,y/2,N);
  43. if(y%2 == 0)
  44. return ( (z%N) * (z%N) ) % N;
  45. else return ((((x%N) * (z%N)) %N) *(z%N) )% N;
  46. }
  47. }
  49. // function modexp without recursion
  50. int modexp_nonre(int x,int y,int N)
  51. {
  52. // exception
  53. if(N <= 0)
  54. {
  55. cout<<“exception of function modexp_re input N “<<endl;
  56. return -1;
  57. }
  58. // exit
  59. if(y == 0)
  60. return 1;
  61. else
  62. {
  63. int result,z;
  65. stack<int> * s = new stack<int>;
  66. while(y >= 1)
  67. {
  68. s->push(y);
  69. y = y/2;
  70. }
  71. result = x % N;
  72. while(s->size()>1)
  73. {
  74. z = s->top();
  75. s->pop();
  76. result = ( (result%N) * (result%N) )%N;
  77. if(s->empty())
  78. break;
  79. else if(z*2 != s->top())
  80. {
  81. result = (result * (x%N) )%N;
  82. }
  83. }
  84. return result;
  85. }
  86. }

算法之运算模的指数运算

模的指数运算

标签

文章归档

模的指数运算

标签

相关推荐

标签

文章归档