// $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("
");
system("pause");
return 0;
}