论文部分内容阅读
摘要：大数计算在实际应用中被大量使用，JDK基础类库中的java.math.BigInteger类能够表示任意精度的整数并在其上进行常见数学运算。文中通过介绍该类关键的成员域和构造过程，清晰地给出了该类存储大数的方法，对学习和使用该类具有积极的意义。
关键词：大数 构造 有效位 符号
0 引言
建立模型并计算是使用数学解决现实问题的一般性过程。自古至今，模型的建立主要依靠人来完成；而计算有所不同，它是一个机械的过程，因为机器比人更快、更准确，所以在历史过程中机器越来越多地参与，后来电子计算机诞生，它以无与伦比的高速度和可靠性超越了人和其它一切计算工具，在现代社会生活中被大量使用。
使用机器进行计算，需要解决的一个关键问题是如何存储一个数。计算机中通常的做法是，把源数据转换为二进制表示形式，然后存储在特定存储单元中。需要计算时，运算器负责将存储单元中的数据转换为结果。鉴于成本、复杂度等因素，运算器每次转换的二进制数据不能太多，所以存储单元不能设计得太大，这就导致计算机不能直接处理太大的数。
为了解决上述问题，软件开发人员将大数分解为多个可以被运算器直接处理的较小的数，然后分别计算并组合出结果，这种方法更多地以库的形式出现，如GMP、Miracl等。Josh Bloch和Michael McCloskey为JDK类库编写了java.math.BigInteger类（后文简称BigInteger），可以表示和计算任意精度的整数，包含丰富的方法，使用简单，非常适合在计算密集性不高的应用环境下使用。
1 关键成员域
数的关键信息是大小和符号。在存储时，主流大数库的方法有两种，一种是直接存储源数的补码；另一种分别存储源数的符号和大小。BigInteger采用后者，使用到的成员域包括整数signum和数组mag；
signum存储源数的符号，可能的取值包含-1、0和1，分别表示目标数是负数、0和正数；mag数组存储源数的大小，每个数组元素存储32个比特位，以无符号数的形式解析，数组元素之间按照高位优先的顺序排列。需要特别指出的是，mag数组中第0个元素值不为0，如果源数为0，则mag不包含数组元素，同时signum取值为0。
2 构造过程概述
BigInteger的构造方法被多次重载，可以接受不同表示形式的源数据，如补码和字符串等；也可以设置符号位和基数。为了支持这些功能，需要实现下面5个过程：
①验证参数的合法性；②移除源數据无效位；③转换源数据为mag数组；④去除mag数组无效位；⑤判断signum取值。
以上过程中，①和⑤容易实现，在此不做讨论，下文重点讨论②、③和④中的关键步骤。
3 去除无效位
对整数而言，最高位的0无意义，在处理时应该被去除以节省计算空间和时间，即②和④两个过程的目的。两者具体步骤相似，区别有三：一是源数据的类型比mag数组多，除了共有的int数组外，还有byte、char数组以及字符串；二是源数据以补码的形式表示时，无效位的字面值为-1；三是源数据不需要产生新的数据，定位有效位起始索引即可，mag数组不能包含无效位，必须产生新的数组。以下代码具有代表意义，摘自BigInteger中的trustedStripLeadingZeroInts方法。
int keep；
for (keep=0；keep if (keep > 0) {
int result[] = new int[val.length - keep]；
for(int i=0；i result[i] =val[keep+i]；
return result；
}
return val；
代码中val是一个待处理的int数组，变量keep表示有效位的起始索引。第一个for循环实现对keep的定位；分支语句判断是否包含无效位，条件成立则初始化和返回刚好容纳有效位的result数组，不成立则返回原val数组。BigInteger中其它去除无效位的过程与此相似，不再赘述。
4 转换源数据为mag数组
BigInteger为了后期处理方便，必须把各种类型的源数据转换为int数组mag，即过程③。期间主要涉及到的两个步骤，分别是计算mag数组长度和元素值。
4.1 计算mag数组长度
当源数据以byte数组的形式出现时，计算mag数组长度较为容易。例如以下摘自BigInteger中stripLeadingZeroBytes方法的代码。
int byteLength=a.length；
int intLength=((byteLength-keep)+3)/4；
代码中a是一个待处理的byte数组，byteLength是它的长度，keep同上，intLength是mag数组长度的精确值。
当源数据以字符串或字符数组的形式出现时，表示源数的字面值，直接计算mag数组长度较需要用到对数运算，效率较低。BigInteger使用查表的方式代替对数运算，表格预先存储在long数组bitsPerDigit中，数组中元素索引为基数，值为以2为底基数的对数再乘以1024，如果有小数位再加1取整。在具体计算时，只需要查表和简单的基本运算，即可得出结果。例如以下代码摘自BigInteger中以字符串和int为参数的构造方法中。
intnumBits=(int)(((numDigits*bitsPerDigit[radix])>>>10)+ 1)；
int numWords=(numBits+31)/32；
代码中radix是源数字面值的基数，numDigits是有效数字个数，则numBits是以2为底numDigits的对数的近似值，即源数二进制有效位的长度，numWords即mag数组的长度。前文中的采用1024作为乘数是为了以上代码可以采用高效的无符号右移运算代替除法运算，使用long类型定义bitsPerDigit数组是为了防止乘法运算溢出。
4.2 计算mag数组元素值
当源数据以byte数组的形式出现时，使用移位和或运算容易计算mag数组元素值。
当源数据以字符串或字符数组的形式出现时，首先查表得出每次最多可以计算的字符个数，然后进行计算。以下代码摘自BigInteger中以字符数组为参数的构造方法中，该方法假设基数为10。
int firstGroupLen = numDigits % digitsPerInt[10]；
if (firstGroupLen == 0)
firstGroupLen = digitsPerInt[10]；
mag[mag.length-1]=parseInt(val，cursor，cursor+=firstGroupLen)；
while (cursor < len) {
int groupVal=parseInt(val，cursor，cursor+=digitsPerInt[10])；
destructiveMulAdd(mag，intRadix[10]，groupVal)；
}
代码中digitsPerInt数组元素的索引为基数，值为每个基数对应的每次最多能够计算的字符个数，numDigits同上，firstGroupLen是第一次计算的长度，cursor是有效位起始索引，parseInt方法用于将字符数组中指定起始位到结束位表示的字面值转换为int值，mag数组是已转换的结果，计算完成后即为最终结果。循环语句判断cursor后是否还有未转换的数据，条件成立则继续转换，groupVal是当前待转换的字面值对应的int值，intRadix是一个int数组，索引为基数，值为每个基数对应的有可能的最大groupVal加1，destructiveMulAdd方法的作用是将第1个int数组参数乘以第二个int参数加上第三个int参数，结果保存在第一个int数组参数中，即将当前待转换值groupVal添加到已转换数组mag中。
5 结语
BigInteger可以稳定可靠地对大整数进行数学运算，是JDK中高精度小数运算的基础。文中介绍了BigInteger的两个成员域的功能，并重点讨论了BigInteger移除无效位和转换数据的关键算法，能够对学习该类工作原理和使用、扩展该类起到帮助作用。同时BigInteger中多次使用查表代替运算，能够在一定程度上提高运行效率和降低编码复杂度，不失为一种简单高效的编程方法，应该被推广使用。
参考文献：
[1]O’Reilly Taiwan公司.JAVA技术手册[M].南京：东南大学出版社.2006，10.
[2]马朝晖，陈美红.Java语言导学[M].北京：机械工业出版社.2003，1.
[3]陈昊鹏.Java编程思想.北京：机械工业出版社[M].2007，6.
[4]王溢琴，齐悦.大整数运算的抽象类研究与设计[J].武汉：软件导刊.2010，1.
关键词：大数 构造 有效位 符号
0 引言
建立模型并计算是使用数学解决现实问题的一般性过程。自古至今，模型的建立主要依靠人来完成；而计算有所不同，它是一个机械的过程，因为机器比人更快、更准确，所以在历史过程中机器越来越多地参与，后来电子计算机诞生，它以无与伦比的高速度和可靠性超越了人和其它一切计算工具，在现代社会生活中被大量使用。
使用机器进行计算，需要解决的一个关键问题是如何存储一个数。计算机中通常的做法是，把源数据转换为二进制表示形式，然后存储在特定存储单元中。需要计算时，运算器负责将存储单元中的数据转换为结果。鉴于成本、复杂度等因素，运算器每次转换的二进制数据不能太多，所以存储单元不能设计得太大，这就导致计算机不能直接处理太大的数。
为了解决上述问题，软件开发人员将大数分解为多个可以被运算器直接处理的较小的数，然后分别计算并组合出结果，这种方法更多地以库的形式出现，如GMP、Miracl等。Josh Bloch和Michael McCloskey为JDK类库编写了java.math.BigInteger类（后文简称BigInteger），可以表示和计算任意精度的整数，包含丰富的方法，使用简单，非常适合在计算密集性不高的应用环境下使用。
1 关键成员域
数的关键信息是大小和符号。在存储时，主流大数库的方法有两种，一种是直接存储源数的补码；另一种分别存储源数的符号和大小。BigInteger采用后者，使用到的成员域包括整数signum和数组mag；
signum存储源数的符号，可能的取值包含-1、0和1，分别表示目标数是负数、0和正数；mag数组存储源数的大小，每个数组元素存储32个比特位，以无符号数的形式解析，数组元素之间按照高位优先的顺序排列。需要特别指出的是，mag数组中第0个元素值不为0，如果源数为0，则mag不包含数组元素，同时signum取值为0。
2 构造过程概述
BigInteger的构造方法被多次重载，可以接受不同表示形式的源数据，如补码和字符串等；也可以设置符号位和基数。为了支持这些功能，需要实现下面5个过程：
①验证参数的合法性；②移除源數据无效位；③转换源数据为mag数组；④去除mag数组无效位；⑤判断signum取值。
以上过程中，①和⑤容易实现，在此不做讨论，下文重点讨论②、③和④中的关键步骤。
3 去除无效位
对整数而言，最高位的0无意义，在处理时应该被去除以节省计算空间和时间，即②和④两个过程的目的。两者具体步骤相似，区别有三：一是源数据的类型比mag数组多，除了共有的int数组外，还有byte、char数组以及字符串；二是源数据以补码的形式表示时，无效位的字面值为-1；三是源数据不需要产生新的数据，定位有效位起始索引即可，mag数组不能包含无效位，必须产生新的数组。以下代码具有代表意义，摘自BigInteger中的trustedStripLeadingZeroInts方法。
int keep；
for (keep=0；keep
int result[] = new int[val.length - keep]；
for(int i=0；i
return result；
}
return val；
代码中val是一个待处理的int数组，变量keep表示有效位的起始索引。第一个for循环实现对keep的定位；分支语句判断是否包含无效位，条件成立则初始化和返回刚好容纳有效位的result数组，不成立则返回原val数组。BigInteger中其它去除无效位的过程与此相似，不再赘述。
4 转换源数据为mag数组
BigInteger为了后期处理方便，必须把各种类型的源数据转换为int数组mag，即过程③。期间主要涉及到的两个步骤，分别是计算mag数组长度和元素值。
4.1 计算mag数组长度
当源数据以byte数组的形式出现时，计算mag数组长度较为容易。例如以下摘自BigInteger中stripLeadingZeroBytes方法的代码。
int byteLength=a.length；
int intLength=((byteLength-keep)+3)/4；
代码中a是一个待处理的byte数组，byteLength是它的长度，keep同上，intLength是mag数组长度的精确值。
当源数据以字符串或字符数组的形式出现时，表示源数的字面值，直接计算mag数组长度较需要用到对数运算，效率较低。BigInteger使用查表的方式代替对数运算，表格预先存储在long数组bitsPerDigit中，数组中元素索引为基数，值为以2为底基数的对数再乘以1024，如果有小数位再加1取整。在具体计算时，只需要查表和简单的基本运算，即可得出结果。例如以下代码摘自BigInteger中以字符串和int为参数的构造方法中。
intnumBits=(int)(((numDigits*bitsPerDigit[radix])>>>10)+ 1)；
int numWords=(numBits+31)/32；
代码中radix是源数字面值的基数，numDigits是有效数字个数，则numBits是以2为底numDigits的对数的近似值，即源数二进制有效位的长度，numWords即mag数组的长度。前文中的采用1024作为乘数是为了以上代码可以采用高效的无符号右移运算代替除法运算，使用long类型定义bitsPerDigit数组是为了防止乘法运算溢出。
4.2 计算mag数组元素值
当源数据以byte数组的形式出现时，使用移位和或运算容易计算mag数组元素值。
当源数据以字符串或字符数组的形式出现时，首先查表得出每次最多可以计算的字符个数，然后进行计算。以下代码摘自BigInteger中以字符数组为参数的构造方法中，该方法假设基数为10。
int firstGroupLen = numDigits % digitsPerInt[10]；
if (firstGroupLen == 0)
firstGroupLen = digitsPerInt[10]；
mag[mag.length-1]=parseInt(val，cursor，cursor+=firstGroupLen)；
while (cursor < len) {
int groupVal=parseInt(val，cursor，cursor+=digitsPerInt[10])；
destructiveMulAdd(mag，intRadix[10]，groupVal)；
}
代码中digitsPerInt数组元素的索引为基数，值为每个基数对应的每次最多能够计算的字符个数，numDigits同上，firstGroupLen是第一次计算的长度，cursor是有效位起始索引，parseInt方法用于将字符数组中指定起始位到结束位表示的字面值转换为int值，mag数组是已转换的结果，计算完成后即为最终结果。循环语句判断cursor后是否还有未转换的数据，条件成立则继续转换，groupVal是当前待转换的字面值对应的int值，intRadix是一个int数组，索引为基数，值为每个基数对应的有可能的最大groupVal加1，destructiveMulAdd方法的作用是将第1个int数组参数乘以第二个int参数加上第三个int参数，结果保存在第一个int数组参数中，即将当前待转换值groupVal添加到已转换数组mag中。
5 结语
BigInteger可以稳定可靠地对大整数进行数学运算，是JDK中高精度小数运算的基础。文中介绍了BigInteger的两个成员域的功能，并重点讨论了BigInteger移除无效位和转换数据的关键算法，能够对学习该类工作原理和使用、扩展该类起到帮助作用。同时BigInteger中多次使用查表代替运算，能够在一定程度上提高运行效率和降低编码复杂度，不失为一种简单高效的编程方法，应该被推广使用。
参考文献：
[1]O’Reilly Taiwan公司.JAVA技术手册[M].南京：东南大学出版社.2006，10.
[2]马朝晖，陈美红.Java语言导学[M].北京：机械工业出版社.2003，1.
[3]陈昊鹏.Java编程思想.北京：机械工业出版社[M].2007，6.
[4]王溢琴，齐悦.大整数运算的抽象类研究与设计[J].武汉：软件导刊.2010，1.