时间：2022-08-28 12:26:36
摘要:以浮点运算的基本理论为基础,结合大整数类BigInteger的研究,采用面向对象技术,提出大数类BigDecimal的一种设计方法,并给出加、减、乘和除法的算法,最后给出C#语言程序实现。
关键词:大数类;.NET;算法
中图分类号:TP311文献标识码:A文章编号:1007-9599 (2010) 06-0000-03
Achievement of the BigDecimal Class Based on BigIntege
Li Wenhua
(College of Information Science&Technology,Hainan University,Haikou570228,China)
Abstract:Based on the basic theory of floating-poing calculation,combining the research of the BigInteger class,using object-oriented technology,puts forward a kind of deisgn method of BigDecimal class,and then gives its addition,subtraction,multiplication and division of the algorithm,and finally gives c# program.
Keywords:BigDecimal Class;.NET;Algorithm
冯•络伊曼计算机,CPU的计算功能只能计算整数(integer,二进制),需要计算小数(decimal)的时候,就需要利用整数计算能力,通过一定的“方法”完成小数计算,这个“方法”就叫小数运算,它分为定点(fix)和浮点(float)运算两种。其中定点运算是将小数看成是由整数部分和小数部分m.n两个部分分别去计算,因非常浪费计算机资源,基本上不被采用。
一、浮点数表示方法
IEEE(电子电气工程师协会)在I985年制定的IEEE 754二进制浮点运算规范,是浮点运算事实上的工业标准,也是其它进制浮点运算的重要技术参考。
计算机中的浮点运算,是小数点位置不固定,最大限度地扩大数值的表示范围,保持数值的有效精度,协调数值在表示范围和精度方面的要求,使计算机能够表示和运算较大的数字。为了满足小数点浮动的要求,任何一个数必须有两部分组成,一部分是阶码E,另一部分是尾数M,其中用阶数E表示小数点的位置,而尾数M表示一个数的有效数字。记为:
f=M×bE--------①
这种表示方法小数点不直观存在,并随E值浮动(浮点运算因此而得名)。
如数f=528000250031.1234567891234,对于基b=10(十进制)情况下,可以表示成:0.5280002500311234567891234×1012,也可表示成5280002500311234567891234×10-13,而在b=109情况下[1],可以表示成:0.000000528 000250031 123456789 123400000×10000000002,也可表示成528 000250031 123456789 123400000×1000000000-2。
文献[2]给出了十进制下的浮点数的另一种表示形式,这里将其扩展为任意基b(进制)的情况,即将①式以另一种形式表示:
f=M×bE=fn-1fn-2⋯f1f0f-1⋯f-m=fn-1bn-1+ fn-2bn-2+⋯+f1b1+f0b0+f-1b-1+⋯+f-mb-m----②
其中fi是一个b进制数字,可以有0,1,2,⋯⋯b-1任意数字,bi表示数码fi在数中的位置。如前面的f在基b=109时可表示为528b1+250031b0+123456789b-1+1234b-2.
②式的两边同乘以因子bk可得到:
F=bkf=bk×M×bE=M×bE+k=fn-1bn+k-1+fn-2bn+k-2+⋯+f1b1+k+ f0b0+k+f-1bk-1+⋯+f-mbk-m---(3)
此时每个数码左移k位(这里的“位”不能理解为就是十进制位,而应理解为b 进制下的位,如b=109时,一个位就是一个9位十进制数),相对的小数点右移k位。当k>=m 时小数点右移到数尾部,浮点数F就是一个整数了,此是有F=bkf,即f=Fb-k,即f变成尾数为纯整数的浮点数形式。利用浮点数的这个特点,可以将浮点运算转换成整数的运算。
二、基于BigInteger的BigDecimal类及算法设计
(一)基于BigInteger的BigDecimal类设计
对于大的小数,即超出普通编程语言的浮点值集范围的数,都可以转化为一个大整数M乘bE的形式,所以自然就想到利用BigInteger类[3]构造一个新的大数类BigDecimal来解决大数浮点计算问题。
从以上分析可以发现,在以b为基的浮点数域里,唯一决定一个大数的就是M和E。为了充分发挥BigInteger的作用,我们对①式进行规范化要示,即M必须大整数,E是int型整数。
有两种设计方案可供选择,一种是采用继承,即BigDecimal继承BigInteger,增加一个E,以及几个构造函数,并且重写+,-,*,/运算过程。
另一种设计方案是采用组合,即构建一个类BigDecimal,成员里包含一个BigInteger和一个E,当然也要构造函数,以及重新编写+,-,*,/运算过程。
面向对象的设计原则建议尽可能用组合而少用继承来设计新的数据类型,且采用继承方式构建BigDecimal,表达的意思是BigDecimal是一个BigInteger―“大数是一种大整数”,而采用组合方式构建,表达的意思是BigDecimal里有BigInteger―“大数里有大整数”,显然组合方式更能表达原意,因此,这里给出采用组合方式设计的BigDecimal类,如图1所示,下面给予简要说明。
1.变量部分。
JI―基b,JILEN―基b的10进制长度,weiShu―大数的尾数,必须是一个大整数,jie―大数的阶数,jingDu--精度要求,即保留小数点后jingDu“位”。
2.成员函数说明。
第一类是构造函数。构造函数主要用于BigDecimal对象的创建及其初始化,其中BigDecimal(BigInteger:bi,int:integer)最最具代表性的构造函数,使用最频繁,即用一个大整数―尾数和一个普通整数―阶数,就构造生成了一个大数。为了使用构造的大数更加规范,尽可能少产生无效数据,任何一个构造函数在构造大数时,应去掉尾部多余的“0”。
第二类是基本操作函数。如getJie()是获得大数的阶数,即小数点的位置(相对于指定的基而言),bigDecPnt()是输出大数,getBigInteger()是获得数的大整数部分,setJingdu(int)重新设置精度要求,getJingdu()是获得精度要求,bigDecWrite()是保存大数。
第三类是大数运算函数。它是BieDecimal的关键,共提供了两种形式,一种是运算函数定义形式,其中函数名是.NET的CLS规范指定的运算符函数名,另一种是运算符重载形式的函数,它能最大程度地为用户提供便利的运算符计算。
为了适应不同情况下的大数运算,每种运算提供了多种形式的重载,如BigDecimal对象的加运算,共设计了BigDecimal+BigDecimal,BigDecimal+BigInteger,BigInteger+BigDecimal,BigDecimal+float,float+BigDecimal等5种形式的运算符重载(多态)。
(二)主要算法设计
对于多态的“+、-、*、/”运算符方法,都只给出其最具代表性的两个BigDecimal对象的四则运算的算法设计,因为其它形式可以转化为这种形式进行,其它方法因较为简单,本文不作详细介绍。
1.加/减法计算。
两个浮点数进行加减运算,其基本法则就是小数位对齐,如果以(1)所表示的形式描述,就是当两个浮点数的尾数都是纯整数且阶数相等时,才能进行加减运算。如果阶数不相等,可以采用将阶数大的数的小数点右移、阶数同步降低的办法解决,因为这种办法能保证尾数总是为纯整数,而阶数能变为相等的目的,这样就可以进行加减运算了。
如a1=355.598=355598*10-3,a2=549.81=54981*10-2均为规范化表达,从阶数看,a2比a1高1,为了方便a1、a2进行加减运算,需要将a2的尾数的“小数点”右移1个,同时阶降为-3,即有a2=549810*10-3,变成a1、a2同阶了,这样a1+a2就可以直接进行尾数的加法运算了,即(355598+549810)*10-3=905408*10-3=905.408,减法依如此。
下面以给出两个大数bdl,bd2相加算法(其中大数均为规范后的格式,即尾数为纯整数,且不考虑有效数位问题):
获取两个数的阶数p1,p2,比较p1,p2大小
如果p1>p2//说明db1小数点需右移,以降低阶数)
p=p2
bd1>>(p1-p2)//调用大整数的右移运算
否则
如果p2>p1
p=p1
bd2>>(p2-p1)
否则
p=p1//此情况下p1与p2相等
返回BigDecimal(bd1.getBigInteger()+bd2.getBigInteger(),p)
2.乘法计算。
乘法运算更为简单,不需要调整两数的小数点位置,只须将两个数的尾数部分相乘,阶数相加,就能得到结果了,下面给出bd1与bd2相乘的算法(不考虑有效数位问题):
获取两个数的阶数p1,p2,并令p=p1+p2
返回BigDecimal(bd1.getBigInteger()*bd2.getBigInteger(),p)
3.算术除计算方法。
算法最为复杂,需要考虑精度要求,以及不能整除情况下的“四舍五入”问题, 其中“四舍五入”是十进制下的说法,对于b进制,应该是大于或等于b/2时“五入”,否则就“四舍”。
假设规范化的a1= a1.M×ba1.E,a2=a2.M×ba2.E,a1/a2=(a1.M/a2.M的整数部分)×ba1.E-a2.E,可以明显看出来,所得结果的小数点后的数位由-(a1.E-a2.E)唯一确定:
当-(a1.E-a2.E)小于精度数位+1时,必须“放大”a1的尾数,即a1.M右移(jingDu+1)-(a2.E-a1.E)个位,同时a1.E变小为a1.E’=a1.E-(1+jingDu-(a2.E-a1.E))=a2.E-jingDu-1,a1/a2的整数商的阶数为a1.E’-a2.E=(a2.E-jingDu-1)-a2.E=-(jingdu+1),最后,我们只须对尾数的“个位”进行“四舍五入”判断即可。
相似的,当-(a1.E-a2.E)大于精度数位+1时,必须“放大”a2的尾数,即a2.M右移-(a1.E-a2.E)C(jingDu+1)位,同时a2.E变小为a2.E’=a2.E-(-(a1.E-a2.E)C(jingDu+1))=a1.E+(jingDu+1)位,a1/a2的整数商的阶数为a1.E-a2.E’=a1.E-(a1.E+(jingDu+1))=-(jingdu+1), 最后,我们只须对尾数的“个位”进行“四舍五入”判断即可。
依然用上例的a1与a2进行a1/a2进行分析,假设要求精度为2,即保留小数点后2位有效数字,此时有a1/a2=0.646…,保留2位有效数位是0.65,因为整数除法只能得到整数部分,因此,我们采用的算法要保证利用整数除法得到的商是放大了103(b3)的数(只能是整数),然后再还原,才到得到满足精度要求的数。
比如,规范化后的a1=355598*10-3,a2=549.81=54981*10-2,-(a1.jie-a2.jie)=1,比要求的精度2小,需要将a1尾数放大101+1倍,而对应的阶数要减少(1+1),即a1=35559800*10-5,再计算a1.M/a2.M=35559800/54981=646余42074,而些时a1.E-a2.E=(-5)-(-2)=-3,满足精度要求的计算结果为646*10-3=0.646,因其“个位”6>10/2,需要进位,故为0.65.下面给出db1/bd2的算法过程:
获取得两个数的阶p1,p2
设tempJingDu=bd1的精度要求
如果-(p1-p2) < tempJingDu+1
bd1>> tempJingDu+1-(p2-p1) //大整数bd1移位运算
否则
如果-(p1-p2)>tempJingDu+1
bd2>>(p2-p1)-(tempJingDu+1)
否则
bd1,bd2均不移位
计算bd1/bd2的商,记为tempQuotient,此时,对应的阶数为-(tempJingDu+1)
如果tempQuotient的最低“位”>=b/2//需要“五入”
返回BigDecimal(tempQuotient
否则//只须“四舍”
返回BigDecimal(tempQuotient
以上设计的四则运算算法过程除了增加少量大整数的移位运算外,均转化为相应的大整数运算,故各算法的复杂度均与相应的大整数的四则运算复杂度同阶。
三、基于.NET的BigDecimal实现
根据C#的特点[4],基于.NET的大数类BigDecimal用C#完成最为合适。为保证C#编的大数类完全符合CLS规范,添加CLSCompliant特性到程序集上,编译器会强制整个程序集都是CLS兼容的,如果存在与CLS不兼容的结构,编译器会自动报错。大数类的C#源代码文件BigDecimalCalssLib.cs主要代码如下:
using BigIntegerClassLib //引用大整数类库
[assembly:CLSCompliant(true)] //编译器CLS规范检查
namespaceBigDecimalClassLib
{publicclassBigDecimal
{privateconstintJI=1000000000;//基=109
privateconstintJILEN=9; //基长度
privateBigIntegerweiShu;//大数的尾数
privateintjie; //阶数
privateintjingDu;//精度要求
public BigDecimal() { weiShu = new BigInteger() ; jie = 0; };//构造大数“0”
publicBigDecimal(str:string) { … }; //用字符串构造大数
publicBigDecimal(BigInteger:bi,int:integer)//用大整数
{weiShu = bi ;jie = integer ; } //尾数和阶数构造大数
……
publicstringbigDecPnt(int sign){…}//返回大数字符串
publicboolean bigDecWrite(string pathName ) {…} //将大数存贮到文件中,返回true表示正常
public BigInteger getBigInteger( )//返回大数的尾数部分
{ retrun weiShu ;}
public int getJie( ) {return jie; }//返回大数的阶数部分
publicvoid setJingdu(int tempJingdu) //设置精度
{ jingDu =tempJingDu ;}
publicintgetJingdu( ) { return jingDu; } //返回精度
publicbooleanbigDecFileRead(string pathName){…}//从文件中读取大数。返回true表示正常
/* 运算符重载部分,先实现符合CLS规范的运算符函数重载,再实现相应的运算符重载 */
public static BigDecimal op_Addition(BigDecimal bd2)
{ int p,p1,p2;//大数+大数运算符函数形式
p1=this.jie;p2=bd2.getJie();//大数本身相当于db1
if(p1>p2)
{ p= p2;
bd1>>(p1-p2);//大整数的移位运算
}
Else
{ if ( p2>p1)
{ p=p1;
bd2>>(p2-p1);
}
Else
p=p1; //说明两个阶数相同
}
return BigDecimal( bd1.getBigInteger()
+bd2.getBigInteger(),p);
｝
public static BigDecimal op_Addition(BigInteger ,bi2){…} //大数+大整数形式,过程略,下同
public static BigDecimal op_Addition(float f2) {…}//大数+普通数运算符函数形式
public static BigDecimal operator +(BigDecimal bd1 , BigDecimal bd2){//大数+大数运算符形式
return bd1.op_Addition(bd2); }
public static BigDecimal operator +(BigDecimal bd1 , BigInteger bi2){ //大数+大整数运算符形式
return bd1.op_Addition(bd2);}
public static BigDecimal operator +( BigInteger bi1 , BigDecimal bd2){//大整数+大数运算符形式
return bd2.op_Addition(bi1);}
public static BigDecimal operator +( BigDecimal bd1 ,float f2){//大数+普通数运算符形式
return bd1.op_Addition(f2);}
public static BigDecimal operator +(float f1,BigDecimal bd2){ //普通数+大数运算符形式
return bd2.op_Addition(f1);}
……//其它运算符与运算符函数重载,略
……//其它运算函数,略
}
大数类BigDecimal扩展并丰富了.NET基本类库集,完善了BigInteger的数据处理能力,使得.NET平台有了完整的大数处理能力,为.NET平台的大数应用提供了基础。
参考文献:
[1]李文化,董克家.大整数精确运算的数据结构与基选择[J].计算机工程与应用,2006,32
[2]雷宏洲.J2ME的浮点计算的简单实现[J].计算机与信息技术,2007,11:84-86
[3]李文化.基于.NET的大整数类设计与实现[J].海南大学学报,2010,2
[4]王昊亮,陈昕.Visual C#程序设计教程[M].清华大学出版社,2003,10
作者简介:李文化(1968.12-),男,硕士,副教授,主要研究方向为数据计算、信息系统,
基金项目:2010年度海南省自然科学基金项目支持