微客导航 » 文章资讯 » C++实现大整数乘法

C++实现大整数乘法

2023-08-14 01:24:04 166

算法竞赛入门经典这本书并没有对大数乘法实现，所以自己补充了一下，乘法的实现很简单，就是再其数据结构基础上把每宽为8位的十进制数看成多项式的系数，vector的下标看成多项式的指数，然后再对应相乘相加就可以了，注意系数超过8位将超八位的补分进位。

我这里是笛卡尔相乘。一般来说是够用的。

但其实多项式乘法算法还有很多更高效的。

#include
#include
#include
#include
usingnamespacestd;
typedeflonglongLL;
structBigInteger{
staticconstintBASE=100000000;
staticconstintWIDTH=8;
vectors;

BigIntegeroperator=(conststring&str){
s.clear();
intx,len=(str.length()-1)/WIDTH+1;
for(inti=0;is.size(),lenb=b.s.size(),lenc=lena+lenb-1;
LL*buf=newLL[lenc+1];
for(inti=0;is[i])*((LL)b.s[j]);
buf[i+j+1]+=buf[i+j]/BASE;
buf[i+j]=buf[i+j]%BASE;
}
for(inti=0;i=0;i--){
intbuf=b.s[i],h=8;
while(buf>0){buf/=10;h--;}
for(intj=0;j
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

返回顶部
3162201930
czq8825@qq.com

C++实现大整数乘法

热门推荐

随机推荐