大数相乘(支持浮点数)

发布时间:2016-12-10 21:00:49 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"大数相乘(支持浮点数)",主要涉及到大数相乘(支持浮点数)方面的内容,对于大数相乘(支持浮点数)感兴趣的同学可以参考一下。

// $Id: multi.cpp 7 2006-11-02 06:30:51Z JiangMiao $ // JiangMiao's Blog http://blog.csdn.net/antter #include <iostream> #include <string> using namespace std; #define SAFE_DELETE(p) if((p)!=NULL){delete p;p=NULL;} typedef unsigned long DWORD; #define OK 0 #define FAIL (DWORD)-1 class bignumFunc { public: /// 转换字符串为 inline static char* strToInt(const string& in) { char* rt=new char[in.size()]; for(size_t i=0;i<in.size();i++) { rt[i]=in[i]-'0'; } return rt; } }; class bignum { char* str; size_t length; size_t point; public: bignum():str(NULL),length(0),point(0) { } ~bignum() { } bignum(const bignum& b) { init(b.length); length=b.length; point=b.point; memcpy(str,b.str,length); } size_t size() { return length; } DWORD reset() { SAFE_DELETE(str); length = 0; point = 0; return OK; } // 分配空间 DWORD init(size_t length) { reset(); str=new char[length]; memset(str,0,length); return OK; } // 读入string DWORD read(const string& in) { return read(in.c_str(),in.size()); } DWORD read(const char* in,size_t length) { init(length); char* str=this->str; size_t i; for(i=0;i<length;i++) { (*str++)=(*in++)-'0'; if((*in)=='.') { i++; break; } } point=i; if(i==length) { this->length=i; return OK; } i++; for(;i<length;i++) { (*str++)=(*++in)-'0'; } this->length=i-1; return OK; } //输出到string string toString() { string rt; rt.reserve(length+1); size_t i; for(i=0;i<point;i++) { rt.append(1,str[i]+'0'); } if(length!=point) { rt.append(1,'.'); for(;i<length;i++) { //这里可加入小数点后的末尾0不输出 rt.append(1,str[i]+'0'); } } return rt; } /** * 大数相乘,最大位数 0.04G 即32位int/(9*9) */ static bignum* mul(bignum* rt,bignum* sa,bignum* sb) { size_t la=sa->length; size_t lb=sb->length; size_t xs=sa->point+sb->point;//小数位数 size_t lr=la+lb; //最大可能位数 char* a=sa->str; char* b=sb->str; unsigned int* r=new unsigned int[lr];//分配结果空间 size_t ia,ib,ir; rt->init(lr); memset(r,0,lr*sizeof(int)); for(ia=0;ia<la;ia++) //相乘 { for(ib=0;ib<lb;ib++) { ir=ib+ia+1; r[ir]+=a[ia]*b[ib]; } } for(ir=lr-1;ir>0;ir--) //进位 { int add=r[ir]/10; r[ir-1]+=add; r[ir]%=10; } size_t i=0; for(ir=0;ir<lr;ir++) //除去前面多余的0 { if(r[ir]!=0) break; i++; } xs-=i; i=0; char* dr=rt->str; for(;ir<lr;ir++) //生成字串 { dr[i++]=r[ir]; } //Reserved: 除去尾部多余0,如果放入输出函数可提升效率 rt->length=i; rt->point=xs; delete r; return rt; } }; class bignumBuilder { public: static bignum* build(const string& str) { bignum* bn=new bignum(); bn->read(str); return bn; } }; /* Revision: 6 2006-11-2 5:30 提升性能的改进设想: 1. 使用char* 代替string 2. 多数相乘返回非string,最后由intToStr进行字串输出,可极大地节省预处理和生成的时间 实现以上两点性能提升至少45%,乱猜的 :) ------------------------------------------- Revision: 7 2006-11-2 14:12 修改: 1. 对字符串进行封装为bignum 2. 内部由char* 代替string 3. 支持浮点运算. 性能提升50% 提升性能的改进设想: 1. 对于小型的long,int,__int64等,采用非string的处理方式,以减少整型与字串转换. 实现以上1点,性能大约提升5%~10%,乱猜的 :) ------------------------------------------- */ /// 以下为测试文件 #include "windows.h" int main(int argc,char** argv) { string rt; bignum* an=new bignum(); bignum* bn=new bignum(); bignum* cn=new bignum(); LARGE_INTEGER fre,begin,end; QueryPerformanceFrequency(&fre); QueryPerformanceCounter(&begin); /* 10000阶乘测试 cn->read("1"); for(int i=1;i<=10000;i++) { bignum* tmp=an; an=cn; cn=tmp; char b[6]; _itoa_s(i,b,10); bn->read(b); bignum::mul(cn,an,bn); } */ /* 浮点数相乘 */ an->read("3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989"); bignum::mul(cn,an,an); QueryPerformanceCounter(&end); cout<<"Spend "<<(end.QuadPart-begin.QuadPart)*1000000/fre.QuadPart<<"ns"<<endl; cout<<cn->size()<<endl; //cout<<cn->toString()<<endl; system("pause"); return 0; } /* 测试10000!的结果 * C4 2.66MHZ revision: 6 Spend 16911238ns //17s 35660. ------------------------ revision: 7 10000阶乘 Spend 8441291ns (8.5秒)提升50% 35660 //1000位大浮点数相乘 Spend 3147ns 2001 请按任意键继续. . . */ http://blog.csdn.net/antter/article/details/1362761 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> using namespace std; #define N 100 //将在数组中保存的字符串转成数字存到int数组中 void getdigits(int *a,char *s) { int i; char digit; int len = strlen(s); for(i = 0; i < len; ++i) { digit = *(s + i); *(a + len - 1 - i) = digit - '0';//字符串s="12345",因此第一个字符应该存在int数组的最后一个位置 } } //将数组a与数组b逐位相乘以后存入数组c void multiply(int *a,int *b,int *c) { /* 数组a中的每位逐位与数组b相乘,并把结果存入数组c 比如,12345*12345,a中的5与12345逐位相乘 对于数组c:*(c+i+j)在i=0,j=0,1,2,3,4时存的是5与各位相乘的结果 而在i=1,j=0,1,2,3,4时不光会存4与各位相乘的结果,还会累加上上次相乘的结果.这一点是需要注意的!!! */ for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) *(c + i + j) += *(a + i) * *(b + j); //这里是移位、进位 for(int i = 0; i < 2 * N - 1; ++i) { *(c + i + 1) += *(c + i)/10; //将十位上的数向前进位,并加上原来这个位上的数 *(c + i) = *(c + i)%10; //将剩余的数存原来的位置上 } } int main() { int a[N] = {0},b[N]= {0},c[2*N] = {0}; char s1[N] = "99999999999999999999999999999999999999999999999"; getdigits(a,s1); getdigits(b,s1); multiply(a,b,c); int j = 2*N-1; while(c[j] == 0) j--; for(int i = j;i >= 0; --i) printf("%d",c[i]); printf("\n"); system("pause"); return 0; }  

上一篇:Failed to execute goal org.apache.maven.plugins:
下一篇:SpringMvc工作原理

相关文章

相关评论