BigInteger简单分析
早上看到一篇写使用BigInteger计算阶乘的文章,看了下源码,有点小收获。
BigInteger的主要内部数据:
int signum;
如果数值为正,则signum为1,值为负则signum为-1,值为0则signum为0。
int[] mag;
使用一个数组表示大数,例如: 如果大数用一个int就可以表示,则直接存这个数在mag[0]中,如果超出int的范围,就扩充这个数组,存储采用big endian方式。
简单分析,把BigInteger中的stripLeadingZeroBytes()函数拷贝出来并调用:
public class A {
// Copy from the jdk 1.6 source code
private static int[] stripLeadingZeroBytes(byte a[]) {
int byteLength = a.length;
int keep;
// Find first nonzero byte
for (keep = 0; keep < a.length && a[keep] == 0; keep++)
;
// Allocate new array and copy relevant part of input array
int intLength = ((byteLength - keep) + 3) / 4;
int[] result = new int[intLength];
int b = byteLength - 1;
for (int i = intLength - 1; i >= 0; i--) {
result[i] = a[b--] & 0xff;
int bytesRemaining = b - keep + 1;
int bytesToTransfer = Math.min(3, bytesRemaining);
for (int j = 8; j <= 8 * bytesToTransfer; j += 8)
result[i] |= ((a[b--] & 0xff) << j);
}
return result;
}
public static void main(String[] args) {
byte x[] = new byte[5];
for (int i = 0; i < x.length; i++)
x[i] = 2;
System.out.println(Arrays.toString(stripLeadingZeroBytes(x)));
System.out.println(new BigInteger(x).toString(2));
}
}
output
=============
[2, 33686018]
1000000010000000100000001000000010
// 分开就是 10 00000010 00000010 00000010 00000010
可以看出,此时的mag长度是2,mag[0] 保存的是溢出位2(big endian)。
顺便说一句,BigInteger和BigDecimal的作者是Bloch,都实现成他比较推崇的Immutable Object的形式,缺点是某些环境下可能产生性能问题。
=================================================
new updated 2010.1.4
可能产生性能问题时的解决方案
Bloch在Effect Java中对不可变类由于生产对象过多而可能产生性能问题提出了两种解决方案。
方案一:在不可变类中对可能产生重复数据的情况提供方法实现
例如:考虑到可能使用BigInteger进行幂元素,在BigInteger中直接提供pow函数:
BigInteger中的pow的内部实现并不会产生多余的BigInteger对象。但如果是个人使用BigInteger来实现x的n次方,即使使用平方后再相乘的方法,也会产生log2(N)个BigInteger对象,当n很大时,过多不必要的对象将占有大量空间,如果来不及回收则会导致out of memory。
提供这种方法实现的很大一个好处就是域共用,即:新产生的BigInteger可以共用“旧”的BigInteger的部分域。典型的例子有:
// BigInteger的negate()方法:
public BigInteger negate() {...}
// 新产生的BigInteger和旧的BigInteger仅仅符号位不同,mag数组时共用的。
// BigInteger的setBit()方法:
public BigInteger setBit(int n)
// 用于置BigInteger的某一位为1,新产生的BigInteger和旧的BigInteger仅仅在某个mag项不同。
缺点:不可能在不可变对象中提供所有可能的方法。
方案二:为不可变类提供一个相应的可变类
例如String是不可变类,StringBuilder是String的可变类。
分享到:
相关推荐
用java写的BigInteger,主要是实现一个内库
使用BigInteger类实现,实现了RSA的加解密
BigInteger不是基本数据类型之一,它其实更像String,是Java里的一个类,然而它的初始化方式却没有String那么方便可以直接赋值,而是跟其他自定义的类一样,要调用它的构造器进行初始化。
JavaScript支持大整数,页面需要进入BigInteger.js。才能使用
BigInteger, JS插件脚本
C#写的BigInteger,我也是下载的,在这个和大家分享吧
自己根据java的biginteger改写的c++大整数类,除法效率比较低,其他都还没什么问题
JAVABigInteger包.pdf
CSharp 4.0 .Net Framework V4.0 BigInteger 结构
类似java里面的BigInteger类型,进行大数存储和计算!
C# 实现的BigInteger操作 简单,快速..
这是我自己写分子分母是采用Biginteger类的分数类期末Java期末项目,如有需改进的地方请提出。
BigInteger的源代码,有英文注释
java练习_大数运算_BigInteger.pdf
网上c#生成rsa公钥和私钥并进行加解密的示例很多,但里面都是要用到BigInteger类,而这个类却没有下载地址,找了很久才找到,在这里分享给大家
GarbaGe的东西降价了!!!一分,就一分!!!好东西一定要分享啊啊啊!!! 本模板为高精度模板,大概可存储200位。 目前只支持:输入、输出、赋值、加法。 会不定期更新,请多多资瓷!
ipv6的ip地址转biginteger数字 直接能够测试
java 中BigInteger应用import java.util.Scanner; import java.math.BigInteger; public class Main{ public static void main(String[]args){ Scanner in=new Scanner(System.in); while(in.hasNext()){//has....
var BigInteger = require('node-biginteger'); var n = BigInteger.fromString('abc', 16); n.toString(16); 类方法:BigInteger.fromLong(val) 瓦尔朗 返回:BigInteger 类方法:BigInteger.fromString(val...
BigInteger_demo.zip