Java: BigInteger で階乗を計算する

自然数ってのは限りがありません。もし上限 n があったと仮定すると、 n+1 が整数、これは矛盾します。よって上限はない。数学ってのは証明ができていいですね。

ところがいざプログラムで実装となるとガラスの壁ってのがあるわけです。ご存じのとおり整数型の上限は64ビット long で　-9223372036854775808　から 9223372036854775807。

これだともっと大きな整数は扱えません。そこで、Java では整数を抽象化し、BigInteger として制限のない整数を表現します。

この BigInteger、四則演算は揃っているのですが、演算メソッドが限られていて、階乗がありません。いちいち定義すればいいわけですが、こんなところで立ち止まっていては世界が見えてこない。

そこで、BigInteger で階乗を計算するコードを載せておきます。

	public static BigInteger factorial(BigInteger x){
	return factorial(x,BigInteger.ONE);
	}
	public static BigInteger factorial(BigInteger x, BigInteger lowerLimit) throws NumberFormatException{
	BigInteger res=BigInteger.ONE;
	if(x.equals(BigInteger.ZERO))
	{
	return res;
	}
	else if(x.compareTo(BigInteger.ZERO)<0 || x.compareTo(lowerLimit)<0)
	{
	throw new NumberFormatException();
	}
	BigInteger i=lowerLimit;
	for(;i.compareTo(x)<=0;i=i.add(BigInteger.ONE))
	{
	res=res.multiply(i);
	}
	return res;
	}

view raw factorial.java hosted with ❤ by GitHub

この階乗を使うと、組み合わせなど計算ができます。階乗で定義されるやつですね。

	public static BigInteger combinatoire(BigInteger n, BigInteger k){
	BigInteger res=BigInteger.ZERO;
	if(n.compareTo(k)==0)
	res=BigInteger.ONE;
	else if(k.equals(BigInteger.ONE))
	res=n;
	else if(n.equals(BigInteger.ONE))
	res=BigInteger.ONE;
	else if(n.compareTo(k)<0)
	res=BigInteger.ZERO;
	else if(0<n.compareTo(k))
	res=Combinatoire.factorial(n).divide(Combinatoire.factorial(k).multiply(Combinatoire.factorial(n.subtract(k))));
	));
	return res;
	}

view raw Combinatoire.java hosted with ❤ by GitHub

実はこの組み合わせ、再帰で定義できます。パスカルの三角形といわれるやつです。

	public static BigInteger combinatoire(BigInteger n, BigInteger k){
	BigInteger res=BigInteger.ZERO;
	if(n.compareTo(k)==0)
	res=BigInteger.ONE;
	else if(k.equals(BigInteger.ONE))
	res=n;
	else if(n.equals(BigInteger.ONE))
	res=BigInteger.ONE;
	else if(n.compareTo(k)<0)
	res=BigInteger.ZERO;
	else if(0<n.compareTo(k))
	res=combinatoire(n.subtract(BigInteger.ONE),k.subtract(BigInteger.ONE)).add(combinatoire(n.subtract(BigInteger.ONE),k));
	return res;
	}

view raw Pascal.java hosted with ❤ by GitHub

証明はこちら。