Posts Tagged “bc”

Feb 10 2010

各种大数(BigInteger in bc, java, perl, php …)

Posted by watashi in summary, tags: , , , , , , , , ,

计算机内的整数往往是固定长度的，比如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的

Comments 7 Comments »