首页 / 算法 / BUG 记录：移位运算与扩展欧几里得算法
BUG 记录：移位运算与扩展欧几里得算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了BUG 记录：移位运算与扩展欧几里得算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2864字，纯文字阅读大概需要5分钟。
内容图文
BUG 记录：移位运算与扩展欧几里得算法
起因
上个月就开始打算用C++写一个ECC的轮子（为什么？折磨自己呗！），奈何自己水平有点差，拖到现在才算写完底层的大数运算。在实现欧几里得算法的时候，我开始纠结了...
欧几里得算法的两种实现
耳熟能详的实现方案
这个实现只要了解过欧几里得算法的同学都很清楚，我把维基百科上的代码粘贴到这里，最开始我也是按照这样的方式写出来的代码，没过几个测试，bug就出来了。
def ext_euclid(a, b):
old_s,s=1,0
old_t,t=0,1
old_r,r=a,b
if b == 0:
return 1, 0, a
else:
while(r!=0):
q=old_r//r
old_r,r=r,old_r-q*r
old_s,s=s,old_s-q*s
old_t,t=t,old_t-q*t
return old_s, old_t, old_r乍一看，这个实现真是天衣无缝，毫无破绽，但是要是实现大数运算的时候，如果要是这么想的话，就太naive了。
矩阵计算欧几里得算法
原理我就不抄了，刚学会的，链接在此
这两个方法看起来其实是等价的，第二个方法无非就是拿矩阵表示了一下，有同学会问了，这能有啥区别？
书本上的方法的问题所在
其实最开始的时候，我在我的大数系统实现的时候，我就意识到了有可能会有这样的问题：
注意上面代码中循环中的操作，减法？乘法？
q*s和q*t其实在a和b很大的时候有溢出的风险。
注意到这个问题之后，我用python实现了一下，果然！这个操作会溢出！又用python实现了一个matrix，这回没有这个问题。（我把代码放在最后)
结论
仔细看看这两种方法，第二种方法其实是一种推迟了减法的做法。矩阵上的元素始终在增长，且不会超过a和b的最高位，代价就是多了两个需要存储的元素。
移位运算坑死我这样的小白
我修改了上面的代码，又测试了一下，还是不对，我慌了，最终使用中间量对比大法，一步一步去对比，人肉检查，我发现了问题所在。
实现gcd免不了带余除法（欧几里得除法）的操作，对于除法，我本来还想优化优化，但是奈何水平有点捉急，最后写了个textbook division（列等式减法那种），里面的当然有移位运算了，就是这个移位运算搞我。
void NB::rshift(int bitnum){
/* calculate block num and remain num */
int blocknum = bitnum/64;
int remainnum = bitnum%64;
WORD tmp1 = 0;
WORD tmp2 = 0;
/* first step , move the blocknum */
for(int i=0;i<MAX_number_word;i++){
if(i-blocknum>=0){
this->val[i-blocknum] = this->val[i];
}
}
for(int i=MAX_number_word-1;i>=MAX_number_word-blocknum;i--){
this->val[i] = 0;
}
/* second step , move the remainnum */
for(int i=MAX_number_word-1;i>=0;i--){
tmp1 = this->val[i]<<(WORDSIZE-remainnum);
this->val[i] = this->val[i]>>remainnum;
this->val[i] += tmp2;
tmp2 = tmp1;
}
}毫无破绽的代码（划掉，并不是）。注意第二步写移位运算的时候有一句:
tmp1 = this->val[i]<<(WORDSIZE-remainnum);
当remainnumd=0,就会出现移位WORDSIZE的情况，聪明的小伙伴都知道，这种情况在C++标准里是没有定义的，即
移位运算的右操作符的大小应该大于等于0小于左操作符的最大位数，其余情况是未定义的。
所以不太聪明但是有效的做法->
/* second step , move the remainnum */
for(int i=MAX_number_word-1;i>=0;i--){
if(remainnum==0){
tmp1 = 0;
}else{
tmp1 = this->val[i]<<(WORDSIZE-remainnum);
}
this->val[i] = this->val[i]>>remainnum;
this->val[i] += tmp2;
tmp2 = tmp1;
}结束
表达了对眼前有码，心中无码的境界的期待。
内容总结
以上是互联网集市为您收集整理的BUG 记录：移位运算与扩展欧几里得算法全部内容，希望文章能够帮你解决BUG 记录：移位运算与扩展欧几里得算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。