计算机内的整数往往是固定长度的,比如32位整数,如果整数超出表示范围则会发生溢出。大数(BigInteger)则是具有任意精度的数(arbitrary precision number),是一个实际运用中常见,尤其在程序设计竞赛里频繁出现的数据结构。java因为带有BigInteger类,而成为竞赛中解决大数问题的首选,而C/C++则需要第三方库提供大数支持。至于其他很多语言,都有语言或标准库级别上的高精度运算支持,只不过其中很多除了在SPOJ和GCJ外恐怕都不怎么能用于水题。Small factorials里有在SPOJ中使用高精度的例子。

Perl: Math::BigInt

Math::BigInt提供了非常多方法,而且很多方法也有对应的运算符重载,支持bin, oct, dec, hex格式字符串与BigInt之间的相互转化,几乎没有不支持的操作,包括三角函数,二项式系数都有。不过Math::BigInt有很多不同的实现,其中最快的是Math::BigInt::GMP,效果还是非常理想的,但是默认的Math::BigInt::Calc就慢得不能忍了,远比php, java, ruby, python的都要慢。另外Math::BigFloat是基于Math::BigInt的高精度浮点数。

use Math::BigInt lib => 'GMP';
use Math::BigFloat try => 'GMP';
print Math::BigFloat->bpi(64), "\n"; # 3.14...
my $x = new Math::BigInt('0x123456789abcdef');
my $y = Math::BigInt->new('0b101010101010101');
print $x + $y, "\n";
print join(":", $x->copy()->bdiv($y)), "\n";

Bash: bc

说bash支持高精度不是很严谨,不过bc(白痴)是Linux下一个支持任意精度数字计算的语言,也算半个标配。bc支持算术运算(+, -, *, /, %, ^等),逻辑运算(<=, ==, ||等),流程控制(if, while, for等),函数定义(define)。bc本身就可以写成脚本执行。

#!/usr/bin/bc -q

define e(n) {
	auto i, p, s;
	p = 10 ^ n;
	s = 2 * p;
	for (i = 2; p > 0; ++i) {
		p /= i;
		s += p;
	}
	return s;
}

print "input a integer: "
x = read()
e(x)
quit

# input a integer: 40
# 27182818284590452353602874713526624977552

Php: BCMath

bc是Binary Calculator的缩写。bc*函数的参数都是操作数加上一个可选的[int scale],比如string bcadd(string $left_operand, string $right_operand[, int $scale]),如果scale没有提供,就用bcscale的缺省值。这里大数直接用一个由0-9组成的string表示,计算结果返回的也是一个string。

  • bcadd — 将两个高精度数字相加
  • bccomp — 比较两个高精度数字,返回-1, 0, 1
  • bcdiv — 将两个高精度数字相除
  • bcmod — 求高精度数字余数
  • bcmul — 将两个高精度数字相乘
  • bcpow — 求高精度数字乘方
  • bcpowmod — 求高精度数字乘方求模,数论里非常常用
  • bcscale — 配置默认小数点位数,相当于就是Linux bc中的”scale=”
  • bcsqrt — 求高精度数字平方根
  • bcsub — 将两个高精度数字相减

Python: long

Python有int和long。int是定长的,而long是大数,现在的python在int运算结果超出范围会自动转为long,很久很久以前是会溢出的。效率不错,相对Python而言……

Ruby: Bignum

Ruby有Fixnum和Bignum。Fixnum是定长的,而Bignum可表示任意精度,如果Fixnum运算的结果超出Fixnum的表示范围,就会自动用Bignum表示,而不会溢出。效率不错,相对Ruby而言……

Haskell: Prelude.Integer

Haskell有Int和Integer,分别是定长整数和高精度整数。Haskell是强类型的语言,所以自动转换类型这种事情是根本不可能的……又因为Haskell可以不显示说明变量类型而由编译器自己去yy,所以更要注意避免溢出,在必要的地方使用toInteger :: Integral a => a -> Integer。Haskell里的Integer的效率极好!!

Java: java.math.BigInteger

java.math.BigInteger是immutable arbitrary-precision integers,使用的时候注意immutable,选择效率高的实现方式。java.math.BigInteger主要提供了基本算术运算和位运算的支持,像sqrt这样的函数就不支持,构造函数也不支持”+1″这样有前导+号的string,会抛java.lang.NumberFormatException。java.math.BigDecimal则提供了immutable arbitrary-precision signed decimal numbers。

7 Responses to “各种大数(BigInteger in bc, java, perl, php …)”
  1. watashi says:

    C#

    F#

    VB .Net

    C++ .Net

    其实都是.Net Framework 4.0开始支持的System.Numeric.BigInteger (MSDN)
    接口和Java的很像,也是immutable的,不过有运算符重载,所以应该好用很多
    方法除了基本的加减乘除外,只有Log,没有Sqrt或者Sin,Atan2这样高级的东东
    由于在reference System.Numeric里,也许会CE
    没有BigDecimal

  2. fancy says:

    c/c++的fft大数快搞死我了……

  3. stan says:

    路过ym

  4. owen_water says:

    [quote]因为Haskell可以不显示说明变量类型而由编译器自己去yy[/quote]..
    yy美..

  5.  
Leave a Reply