高速な累乗計算
累乗(x^n)を単純に計算すると、オーダーは O(n)となり効率が悪いです。
そこで、nを2の累乗に分解して計算する高速化手法が一般に知られています。
3^11 は以下のように計算できます。
3^11 = 3^(1+2+8)
= 3^1 × 3^2 × 3^8
= 3 × 9 × 6561
= 177147
この方法のオーダーは、O(log2(n)) です。
http://d.hatena.ne.jp/kazu-yamamoto/20090223/1235372875


冪乗 - Wikipedia
効率的な演算法コンピュータ上で冪乗演算を行なう効率的な演算方法としてバイナリ法（二進数法）とも呼ばれる演算方法を示す。
この方法を使うと、指数となる自然数がいかに巨大であっても高々そのビット数の2倍の回数の乗算で算出することが可能になり、
繰り返し掛けるよりも大幅に効率がよくなる。
特にRSA暗号やフェルマーテストなどにおいて各演算後に必要となる剰余演算の回数を減らす効果がある。