C++大数精度计算

头文件: // WTNumber.h: interface for the CWTNumber class. // ////////////////////////////////////////////////////////////////////// #if !defined(AFX_WTNUMBER_H__92E62B40_491A_4A75_AB89_FFB160DB2343__INCLUDED_) #define AFX_WTNUMBER_H__92E62B40_491A_4A75_AB89_FFB160DB2343__INCLUDED_ #if _MSC_VER 1000 #pragma once #endif // _MSC_VER > 1000 #define INT_BIT_MAX 255 #define FLOAT_BIT_MAX 255 class CWTNumber { private: int intbits; /* 整数数位*/ int floatbits; /* 小数有效数位*/ char infinite; /* 无穷大*/ char sign; /* 符号*/ char intpart[INT_BIT_MAX]; /* 整数部分*/ char floatpart[FLOAT_BIT_MAX]; /* 小数部分*/ private: char* m_sz; public: /* 算术函数指针类型.*/ typedef void (*PFNCALC)(const CWTNumber&,const CWTNumber&,CWTNumber&); CWTNumber(); CWTNumber(const char* szNum); ~CWTNumber(); /* 转换成字符串*/ char* ToString(); void FreeString(); /* 初始化WTNumber为0.*/ void InitWTNumberToZero(); /* 判断需要多少个字符空间存储WTNumber转换的字符串.*/ int StrLenByWTNumber(); /* 从字符串转换到WTNumber.*/ void StrToWTNumber(const char *arr); /* 从WTNumber转换到字符串.*/ void WTNumberToStr(char *szBuf); /* 调节数位,删除最高整数位是0的和最低小数位是0的数位.*/ void AdjustBits(); /* 移动小数点,delta=0不移动,delta 0往左移动,delta>0往右移动.*/ void MoveFloatPoint(int delta); /* 使无穷大 */ void MakeInfinite(); /* 比较2个数大小 */ int WTCompare(const CWTNumber& n) const; /* 判断是否为0 */ int IsZero() const; /* 赋值号重载*/ CWTNumber& operator=(const CWTNumber& n); /* 运算符重载 */ CWTNumber operator+(const CWTNumber& n); CWTNumber operator-(const CWTNumber& n); CWTNumber operator*(const CWTNumber& n); CWTNumber operator/(const CWTNumber& n); CWTNumber& operator+=(const CWTNumber& n); CWTNumber& operator-=(const CWTNumber& n); CWTNumber& operator*=(const CWTNumber& n); CWTNumber& operator/=(const CWTNumber& n); bool operator>(const CWTNumber& n); bool operator>=(const CWTNumber& n); bool operator<(const CWTNumber& n); bool operator<=(const CWTNumber& n); bool operator==(const CWTNumber& n); bool operator!=(const CWTNumber& n); /* 加法*/ static void WTAdd(const CWTNumber& n1,const CWTNumber& n2,CWTNumber& Res); /* 乘法*/ static void WTMultiply(const CWTNumber& n1,const CWTNumber& n2,CWTNumber& Res); /* 减法*/ static void WTSubtract(const CWTNumber& n1,const CWTNumber& n2,CWTNumber& Res); /* 除法*/ static void WTDivide(const CWTNumber& n1,const CWTNumber& n2,CWTNumber& Res); /* 根据算术函数返回结果 */ static char *Result(const char *val1,const char *val2,PFNCALC pfnCalc); }; #endif // !defined(AFX_WTNUMBER_H__92E62B40_491A_4A75_AB89_FFB160DB2343__INCLUDED_) 源文件: // WTNumber.cpp: implementation of the CWTNumber class. // ////////////////////////////////////////////////////////////////////// #include #include #include "WTNumber.h" ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// CWTNumber::CWTNumber() { InitWTNumberToZero(); } CWTNumber::CWTNumber(const char* szNum) { InitWTNumberToZero(); StrToWTNumber(szNum); } CWTNumber::~CWTNumber() { FreeString(); } void CWTNumber::FreeString() { if(m_sz) delete []m_sz; m_sz=NULL; } void CWTNumber::InitWTNumberToZero() { memset(this,0,sizeof(CWTNumber)); } int CWTNumber::StrLenByWTNumber() { int len = floatbits+intbits+1; if(intbits==0) len++; /* .1 --> 0.1*/ if(floatbits) len++; /* '.'*/ if(sign) len++; /* '-'*/ if(infinite) return 11; /* #INFINITE */ return len; } void CWTNumber::StrToWTNumber(const char *arr) { char *point; InitWTNumberToZero(); if(*arr=='-') /* 如果是负数*/ { arr++; sign=1; } point=strchr(arr,'.'); if(point) /* 找到小数点 */ { int n=intbits=point-arr; /* 计算出整数数位 */ while(n) /* 整数数位不==0则循环 */ { intpart[intbits-n]=arr[n-1]-'0'; /* 将数字低位存在低下标元素*/ n--; } while(*++point) { floatpart[floatbits]=*point-'0'; floatbits++; } } else /* 说明没写小数点,全是整数.*/ { int n=intbits=strlen(arr); while(n) { intpart[intbits-n]=arr[n-1]-'0'; n--; } } AdjustBits(); /* 处理-0 和0的情况*/ if(floatbits==0) { if(intbits==0 || intbits==1&&intpart[0]==0) sign=0; } } void CWTNumber::WTNumberToStr(char *szBuf) { int n=intbits,c; memset(szBuf,0,StrLenByWTNumber()); if(sign) /* 如果是负数*/ { *szBuf++='-'; } if(infinite) { strcat(szBuf,"#INFINITE"); return; } while(n) { szBuf[intbits-n]=intpart[n-1]+'0'; n--; } c=0; /* 是否加了0*/ if(intbits==0) { strcat(szBuf,"0"); c=1; } if(floatbits) strcat(szBuf,"."); n=0; while(n { szBuf[intbits+1+n+c]=floatpart[n]+'0'; n++; } } void CWTNumber::AdjustBits() { while(intbits>1&&intpart[intbits-1]==0) intbits--; while(floatbits&&floatpart[floatbits-1]==0) floatbits--; } void CWTNumber::MoveFloatPoint(int delta) { /* delta<0则往左移动小数点,delta>0则向右移动小数点 */ if(delta) { CWTNumber n=*this; InitWTNumberToZero(); sign=n.sign; if(delta<0) { int i; delta=-delta; for(i=delta;i { intpart[intbits++]=n.intpart[i]; } for(i=delta-1;i>=0;i--) { floatpart[floatbits++]=n.intpart[i]; } for(i=0;i { floatpart[floatbits++]=n.floatpart[i]; } } else { int i; for(i=delta;i { floatpart[floatbits++]=n.floatpart[i]; } for(i=delta-1;i>=0;i--) /* 小数到整数的部分*/ { intpart[intbits++]=n.floatpart[i]; } for(i=0;i { intpart[intbits++]=n.intpart[i]; } } } AdjustBits(); } void CWTNumber::MakeInfinite() { infinite=1; } int CWTNumber::WTCompare(const CWTNumber& n) const { /* 首先是比较符号*/ if(sign==0&&n.sign!=0) /* pn1是正数,pn2是负数*/ return 1; /* >*/ else if(sign!=0&&n.sign==0) /* pn1是负数,pn2是正数*/ return -1; /* <*/ else /* 同号状态*/ { /* 比较整数部分*/ if(intbits>n.intbits) /* pn1整数数位多*/ return sign?-1:1; else if(intbits return sign?1:-1; else /* 整数数位相同*/ { int i=intbits-1; /*指到最高位*/ while(i>=0) { if(intpart[i]>n.intpart[i]) return sign?-1:1; else if(intpart[i] return sign?1:-1; else i--; } /* 整数部分相同,比较小数部分*/ for(i=0;i { if(floatpart[i]>n.floatpart[i]) return sign?-1:1; else if(floatpart[i] return sign?1:-1; else i++; } if(i if(i return 0; /* 相等*/ } } } int CWTNumber::IsZero() const { if(floatbits==0&&intbits==0) return 1; if(floatbits==0&&intbits==1&&intpart[0]==0) return 1; return 0; } void CWTNumber::WTAdd(const CWTNumber& n1,const CWTNumber& n2,CWTNumber& Res) { Res.InitWTNumberToZero(); if(n1.sign^n2.sign) /*异号*/ { CWTNumber rn2=n2; rn2.sign=n1.sign; WTSubtract(n1,rn2,Res); } else /*同号*/ { int maxfloatbits=n1.floatbits>n2.floatbits?n1.floatbits:n2.floatbits; int addbit=0; /* 进位值*/ int i,j; for(i=maxfloatbits-1;i>=0;i--) { int value=n1.floatpart[i]+n2.floatpart[i]+addbit; addbit=value/10; /* 看看是否超过10. 设置进位值*/ Res.floatpart[i]=value%10; } Res.floatbits=maxfloatbits; /* 到此,小数部分计算完毕.*/ for(j=0;j { int value=n1.intpart[j]+n2.intpart[j]+addbit; addbit=value/10; Res.intpart[j]=value%10; Res.intbits++; } if(addbit>0) { Res.intpart[j]=addbit; Res.intbits++; } Res.sign=n1.sign; /*决定符号*/ Res.AdjustBits(); } } void CWTNumber::WTMultiply(const CWTNumber& n1,const CWTNumber& n2,CWTNumber& Res) { CWTNumber z1=n1,z2=n2; CWTNumber sum; int i,j; sum.InitWTNumberToZero(); Res.InitWTNumberToZero(); z1.MoveFloatPoint(z1.floatbits); z2.MoveFloatPoint(z2.floatbits); /* 计算z1*z2 */ for(i=0;i { CWTNumber tmp; /* 存放临时乘积*/ int addbit=0; tmp.intbits=z1.intbits+i; for(j=0;j { int value = z2.intpart[i]*z1.intpart[j]+addbit; addbit=value/10; tmp.intpart[j+i]=value%10; } if(addbit) { tmp.intpart[j+i]=addbit; tmp.intbits++; } WTAdd(sum,tmp,Res); sum=Res; } Res=sum; Res.MoveFloatPoint(-(n1.floatbits+n2.floatbits)); /* 判断符号,异号为负*/ if(n1.sign^n2.sign) Res.sign=1; } void CWTNumber::WTSubtract(const CWTNumber& n1,const CWTNumber& n2,CWTNumber& Res) { Res.InitWTNumberToZero(); if(n1.sign^n2.sign) /* 异号情况*/ { CWTNumber rn2=n2; rn2.sign=n1.sign; WTAdd(n1,rn2,Res); } else /* 同号情况*/ { int cmp=n1.WTCompare(n2); int swapflag,i,maxfloatbits,subtractbit; if(cmp==0) return; /* 相等就没必要再减了.*/ swapflag=n1.sign==0?cmp==-1:cmp==1; const CWTNumber* pn1=&n1; const CWTNumber* pn2=&n2; if(swapflag) { const CWTNumber *t=pn1; pn1=pn2; pn2=t; } maxfloatbits=pn1->floatbits>pn2->floatbits?pn1->floatbits:pn2->floatbits; subtractbit=0; /* 退位值*/ /* 先计算小数部分*/ for(i=maxfloatbits-1;i>=0;i--) { if(pn1->floatpart[i]-subtractbitfloatpart[i]) { int value=pn1->floatpart[i]-pn2->floatpart[i]-subtractbit+10; subtractbit=1; Res.floatpart[i]=value; } else { int value=pn1->floatpart[i]-pn2->floatpart[i]-subtractbit; subtractbit=0; Res.floatpart[i]=value; } } Res.floatbits=maxfloatbits; /* 至此小数部分计算完毕.*/ for(i=0;iintbits||iintbits;i++) { if(pn1->intpart[i]-subtractbitintpart[i]) { int value=pn1->intpart[i]-pn2->intpart[i]-subtractbit+10; subtractbit=1; Res.intpart[i]=value; } else { int value=pn1->intpart[i]-pn2->intpart[i]-subtractbit; subtractbit=0; Res.intpart[i]=value; } Res.intbits++; } Res.sign=swapflag?!n1.sign:n1.sign; /*决定符号*/ Res.AdjustBits(); } } void CWTNumber::WTDivide(const CWTNumber& n1,const CWTNumber& n2,CWTNumber& Res) { CWTNumber z1=n1,z2=n2; int deta=z2.floatbits-z1.floatbits; z1.MoveFloatPoint(z1.floatbits); z2.MoveFloatPoint(z2.floatbits); Res.InitWTNumberToZero(); if(n1.IsZero()) return ; if(n2.IsZero()) { Res.sign=n1.sign; Res.MakeInfinite(); return ; } z1.sign=z2.sign=0; /*统一符号,便于比较大小*/ while(z1.intbits!=z2.intbits) { /*确保数位相等,这步耗费很多时间*/ if(z1.intbits z1.MoveFloatPoint(1); deta--; } else { z2.MoveFloatPoint(1); deta++; } } while(Res.floatbits<(INT_BIT_MAX/2)) { int cmp=z1.WTCompare(z2); int n=10; CWTNumber mulres,subres; if(cmp==-1) { /*z1 z1.MoveFloatPoint(1); Res.floatpart[Res.floatbits++]=0; continue; } else if(cmp==0) { /*z1==z2*/ Res.floatpart[Res.floatbits++]=1; break; } do { /*找商*/ CWTNumber tmp; tmp.intpart[0]=--n; tmp.intbits=1; WTMultiply(z2,tmp,mulres); } while((cmp=mulres.WTCompare(z1))==1); Res.floatpart[Res.floatbits++]=n; if(cmp==0) break; WTSubtract(z1,mulres,subres); subres.MoveFloatPoint(1); z1=subres; } Res.MoveFloatPoint(1); Res.MoveFloatPoint(deta); /* 判断符号,异号为负*/ if(n1.sign^n2.sign) Res.sign=1; } char *CWTNumber::Result(const char *val1,const char *val2,PFNCALC pfnCalc) { CWTNumber n1,n2,res; n1.StrToWTNumber(val1); n2.StrToWTNumber(val2); pfnCalc(n1,n2,res); return res.ToString(); } char* CWTNumber::ToString() { FreeString(); m_sz=new char[StrLenByWTNumber()]; WTNumberToStr(m_sz); return m_sz; } CWTNumber& CWTNumber::operator=(const CWTNumber& n) { if(this!=&n) { FreeString(); memcpy(this,&n,sizeof(CWTNumber)); if(n.m_sz) { m_sz=strdup(n.m_sz); } } return *this; } CWTNumber CWTNumber::operator+(const CWTNumber& n) { CWTNumber res; CWTNumber::WTAdd(*this,n,res); return res; } CWTNumber CWTNumber::operator-(const CWTNumber& n) { CWTNumber res; CWTNumber::WTSubtract(*this,n,res); return res; } CWTNumber CWTNumber::operator*(const CWTNumber& n) { CWTNumber res; CWTNumber::WTMultiply(*this,n,res); return res; } CWTNumber CWTNumber::operator/(const CWTNumber& n) { CWTNumber res; CWTNumber::WTDivide(*this,n,res); return res; } CWTNumber& CWTNumber::operator+=(const CWTNumber& n) { CWTNumber n1=*this,n2=n; CWTNumber::WTAdd(n1,n2,*this); return *this; } CWTNumber& CWTNumber::operator-=(const CWTNumber& n) { CWTNumber n1=*this,n2=n; CWTNumber::WTSubtract(n1,n2,*this); return *this; } CWTNumber& CWTNumber::operator*=(const CWTNumber& n) { CWTNumber n1=*this,n2=n; CWTNumber::WTMultiply(n1,n2,*this); return *this; } CWTNumber& CWTNumber::operator/=(const CWTNumber& n) { CWTNumber n1=*this,n2=n; CWTNumber::WTDivide(n1,n2,*this); return *this; } bool CWTNumber::operator>(const CWTNumber& n) { return WTCompare(n)==1; } bool CWTNumber::operator>=(const CWTNumber& n) { return WTCompare(n)!=-1; } bool CWTNumber::operator<(const CWTNumber& n) { return WTCompare(n)==-1; } bool CWTNumber::operator<=(const CWTNumber& n) { return WTCompare(n)!=1; } bool CWTNumber::operator==(const CWTNumber& n) { return WTCompare(n)==0; } bool CWTNumber::operator!=(const CWTNumber& n) { return WTCompare(n)!=0; } 使用演示: #include #include "WTNumber.h" int main() { char sz1[256]=""; char sz2[256]=""; puts("请输入两个数字:"); while(scanf("%s%s",sz1,sz2)!=-1) { CWTNumber n1(sz1),n2(sz2); printf("两数相加结果:\n%s\n",(n1+n2).ToString()); printf("两数相减结果:\n%s\n",(n1-n2).ToString()); printf("两数相乘结果:\n%s\n",(n1*n2).ToString()); printf("两数相除结果:\n%s\n",(n1/n2).ToString()); puts("请输入两个数字:"); } return 0; } 运行结果: 请输入两个数字: 13 7 两数相加结果: 20 两数相减结果: 6 两数相乘结果: 91 两数相除结果: 1.85714285714285714285714285714285714285714285714285714285714285714285714285714285714285714285714285714285714285714285714285714

英文写作第一反应词替换表

多同学经常把第一反应词翻来覆去的用，这样的后果就是：第一，写文章时用词的质量一直上不去；第二，一直缺乏对背过的单词的应用以及通过应用的语境理解和辨析。下面，我给大家列举了我们在写作常用的那些第一反应词的替换表，旨在告诉大家，要让自己的语言表达能力书面化，多样化。

很多同学在写作的时候，往往想到某个意思，立刻脑子中想到都是例如I think, important, show, because, moreandmore等等这些词汇，这些词汇在英语教学中，我们称他们为第一反应词，所谓第一反应词，很好理解，就是每个人第一时间反应出来的这些表达。那么，如果要写出一篇高质量的文章，除了内容，词的使用能够表现出你的英语能力，我们很多同学的阅读词汇量远远大于写作词汇量，原因很简单，大家背了很多漂亮的单词，但是却从不给他们“出镜”的机会，而是把这些第一反应词翻来覆去的用，这样的后果就是：第一，写文章时用词的质量一直上不去；第二，一直缺乏对背过的单词的应用以及通过应用的语境理解和辨析。下面，我给大家列举了我们在写作常用的那些第一反应词的替换表，旨在告诉大家，要让自己的语言表达能力书面化，多样化。

through－>in term of/via

operate－>manipulate

offspring－>descendant

inevitable－dispensable

detail－>specific

explain－>interpret

obvious－>conspicuous

hurt－>vulnerable

use－>employ/utilize

value－>merit

provide－>lend－>offer

true－>accurate

leading to－>contribute to/ conduce to/result in

more and more－>increasing/growing

hardly－>merely－>barely

well-known－>outstanding

large－>miraculous/marvelous

although－>albeit/notwithstanding

in fact－>actually/virtually

want－>intend to/tend to/be inclined to

because－>in that

may be－>probably

to sum－>to summarize/in conclusion

explain－>interpret/illustrate

change－>alert

chance－>alternative

custom－>convention/tradition

think－>contemplate/muse/meditate/retrospect

arouse－>ignite/stimulate/spur/motivate

limit－>stress/hinder/hamper

key－>crucial/vital/consequential

old－>ancient

emphasis－>accentuate

devote to－>dedicate to

character－>trait/individuality/idiosyncrasy/personality

expect－>anticipate

join－>participate

delegate－>representative

bias－>prejudice/discriminate/tendency

thrive－>palmy/floushing/prosperity

clash－>conflict/collision/rencounter

publicize－>propagandize

agree partly－>agree with reserve

proper－>apposite

want to－>desire

big city－>metropolis

lawmaking－>legislation

first－>primarily

but－>nonetheless/nevertheless

child－>juvenile

absorb－>assimilate

hand in－>render

undermine－>sap/enervate/debilitate

get into chaos－>with chaos ensuing

key－>pivot/crux

sway－>vacillate

fanatic patriotism－>jingoism/chauvinism

persusive－>thorough/sound/specific/convincing

consider－>take into account

vague－>gratuitous/unwarranted/oversimplified

absorb－>assimilate
agree partly－>agree with reserve
although－>albeit/notwithstanding
arouse－>ignite/stimulate/spur/motivate
because－>in that
bias－>prejudice/discriminate/tendency
big city－>metropolis
but－>nonetheless/nevertheless
chance－>alternative
change－>alert
character－>trait/individuality/idiosyncrasy/personality
child－>juvenile
clash－>conflict/collision/rencounter
consider－>take into account
custom－>convention/tradition
delegate－>representative
detail－>specific
devote to－>dedicate to
emphasis－>accentuate
expect－>anticipate
explain－>interpret
explain－>interpret/illustrate
fanatic patriotism－>jingoism/chauvinism
first－>primarily
get into chaos－>with chaos ensuing
hand in－>render
hardly－>merely－>barely
hurt－>vulnerable
in fact－>actually/virtually
inevitable－dispensable
join－>participate
key－>crucial/vital/consequential
key－>pivot/crux
large－>miraculous/marvelous
lawmaking－>legislation
leading to－>contribute to/ conduce to/result in
limit－>stress/hinder/hamper
may be－>probably
more and more－>increasing/growing
obvious－>conspicuous
offspring－>descendant
old－>ancient
operate－>manipulate
persusive－>thorough/sound/specific/convincing
proper－>apposite
provide－>lend－>offer
publicize－>propagandize
sway－>vacillate
think－>contemplate/muse/meditate/retrospect
thrive－>palmy/floushing/prosperity
through－>in term of/via
to sum－>to summarize/in conclusion
true－>accurate
undermine－>sap/enervate/debilitate
use－>employ/utilize
vague－>gratuitous/unwarranted/oversimplified
value－>merit
want to－>desire
want－>intend to/tend to/be inclined to
well-known－>outstanding

求平方根倒数的算法

zhiqiang九月 19, 2008 计算机科学

下面这个求的函数号称比直接调用sqrt库函数快4倍，来自游戏Quake III的源代码。

float InvSqrt (float x){     float xhalf = 0.5f*x;     int i = *(int*)&x;     i = 0x5f3759df - (i>>1);     y = *(float*)&i;     y = y*(1.5f - xhalf*y*y);     return x; }

我们这里分析一下它的原理（指程序的正确性，而不是解释为何快）。

分析程序之前，我们必须解释一下float数据在计算机里的表示方式。一般而言，一个float数据共32个bit，和int数据一样。其中前23位为有效数字，后面接着一个8位数据表示指数，最后一位表示符号，由于这里被开方的数总是大于0，所以我们暂不考虑最后一个符号位。此时

如果我们把计算机内的浮点数看做一个整数，那么

现在开始逐步分析函数。这个函数的主体有四个语句，分别的功能是：

int i = *(int*)&x; 这条语句把转成。

i = 0x5f3759df - (i>>1); 这条语句从计算。

y = *(float*)&i; 这条语句将转换为。

y = y*(1.5f - xhalf*y*y); 这时候的y是近似解；此步就是经典的牛顿迭代法。迭代次数越多越准确。

关键是第二步 i = 0x5f3759df - (i>>1); 这条语句从计算，原理:

令，用和带入之后两边取对数，再利用近似表示，算一算就得到

若取，就是程序里所用的常量0x5f3759df。至于为何选择这个，则应该是曲线拟合实验的结果。