C++實(shí)現(xiàn)大整數(shù)乘法
算法競賽入門經(jīng)典 這本書并沒有對大數(shù)乘法實(shí)現(xiàn),所以自己補(bǔ)充了一下,乘法的實(shí)現(xiàn)很簡單,就是再其數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上把每寬為8位的十進(jìn)制數(shù)看成多項(xiàng)式的系數(shù),vector的下標(biāo)看成多項(xiàng)式的指數(shù),然后再對應(yīng)相乘相加就可以了,注意系數(shù)超過8位 將超八位的補(bǔ)分進(jìn)位。
我這里是笛卡爾相乘。一般來說是夠用的。
但其實(shí)多項(xiàng)式乘法算法還有很多更高效的。
#include <iostream> #include <vector> #include <cstring> #include <cstdio> using namespace std; typedef long long LL; struct BigInteger{ static const int BASE = 100000000; static const int WIDTH = 8; vector<int> s; BigInteger operator = (const string& str){ s.clear(); int x, len=(str.length()-1)/WIDTH+1; for(int i=0;i<len;i++){ int r=str.length()-i*WIDTH; int l=max(0,r-WIDTH); sscanf(str.substr(l,r-l).c_str(),"%d",&x); s.push_back(x); } return *this; } BigInteger operator * (const BigInteger& b){ BigInteger c; int lena=this->s.size(),lenb=b.s.size(),lenc=lena+lenb-1; LL *buf =new LL[lenc+1]; for(int i=0;i<lenc+1;i++)buf[i]=0; for(int i=0;i<lena;i++) for(int j=0;j<lenb;j++){ buf[i+j]+=(this->s[i])*((LL)b.s[j]); buf[i+j+1]+=buf[i+j]/BASE; buf[i+j]=buf[i+j]%BASE; } for(int i=0;i<lenc;i++)c.s.push_back(buf[i]); if(buf[lenc])c.s.push_back(buf[lenc]); return c; } BigInteger operator * (const int& x){ char c[128]; sprintf(c,"%d",x); string str(c); BigInteger res; res=str; return *this*res; } }; ostream& operator<<(ostream& out,const BigInteger& b){ int len=b.s.size(); out<<b.s[len-1]; for(int i=len-2;i>=0;i--){ int buf=b.s[i],h=8; while(buf>0){buf/=10;h--;} for(int j=0;j<h;j++)out<<0; if(b.s[i])out<<b.s[i]; } return out; } int main() { int n;BigInteger b; b="1000000000000"; cout<< b<<endl; cout<< (b*b)*4*b*b <<endl; }
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
C語言結(jié)構(gòu)體中內(nèi)存對齊的問題理解
內(nèi)存對齊”應(yīng)該是編譯器的“管轄范圍”。編譯器為程序中的每個(gè)“數(shù)據(jù)單元”安排在適當(dāng)?shù)奈恢蒙?。但是C語言的一個(gè)特點(diǎn)就是太靈活,太強(qiáng)大,它允許你干預(yù)“內(nèi)存對齊”。如果你想了解更加底層的秘密,“內(nèi)存對齊”對你就不應(yīng)該再模糊了2022-02-02C++實(shí)現(xiàn)LeetCode(48.旋轉(zhuǎn)圖像)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(48.旋轉(zhuǎn)圖像),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07C++通過boost.date_time進(jìn)行時(shí)間運(yùn)算
這篇文章介紹了C++通過boost.date_time進(jìn)行時(shí)間運(yùn)算的方法,文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-06-06C語言深入分析遞歸函數(shù)的實(shí)現(xiàn)
遞歸(recursive)函數(shù)是“自己調(diào)用自己”的函數(shù),無論是采用直接或間接調(diào)用方式。間接遞歸意味著函數(shù)調(diào)用另一個(gè)函數(shù)(然后可能又調(diào)用第三個(gè)函數(shù)等),最后又調(diào)用第一個(gè)函數(shù)。因?yàn)楹瘮?shù)不可以一直不停地調(diào)用自己,所以遞歸函數(shù)一定具備結(jié)束條件2022-04-04