

各种大数(BigInteger in bc, java, perl, php …)
Posted by watashi in summary, tags: bash, bc, BigInteger, haskell, java, perl, php, python, ruby, summary计算机内的整数往往是固定长度的,比如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