ことさら−古都プログラマーの更級日記

京都でお寺を回りながら御朱印集めをしていたエンジニアのブログ。おもに技術的なはなしとか日常的なはなし

JavaのBigInteger.modPowはどの程度使えるのか

繰り返し二乗法とは

AOJの問題でこんなものがあります

Power | Aizu Online Judge

mとnが入力として与えられるので、mn を 1000000007 で割った余りを出力せよという問題です。n が最大で 109 なので、単純にn-1回「掛けてmodで割る」を繰り返しても間に合いません。

問題ページの下の方に行ったら解説ページがあるので、そこを読んでもらえばわかると思いますが、ここでは「繰り返し二乗法」というアルゴリズムを使います。x4 を (x2)2 と考えると、単純アルゴリズムだと3回かかってた計算が2回で済みます。log(n) 回で計算が済むというものです。

JavaだとBigIntegerで解ける…?

しかしこの問題、Javaだとこれだけのコードで済みます。

import java.io.*;
import java.util.*;
import java.math.*;


class Main {
    static Scanner sc = new Scanner(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception {
        BigInteger n = new BigInteger(sc.next());
        BigInteger m = new BigInteger(sc.next());
        System.out.println(n.modPow(m, new BigInteger("1000000007")));
    }
}

BigIntegerのmodPowというメソッドを使うと一発で終わってしまうのです。これがAcceptされるということは、この中では繰り返し二乗法が使われていることになります。また、modの計算までよしなにやってくれているようなのです。

BigIntegerは遅いというイメージがあったので驚きでした。繰り返し二乗法を使っていると、logオーダーになり、オーダー的にはかなり小さくなるので、一回の計算のオーダーが多少悪かったとしても間に合うというオチなのかもしれません。BigIntegerのメソッドについて調べてみて、今後使う機会があれば使ってみたいと思います。