巨大回数の繰り返し - JavaScript - c4se記：さっちゃんですよ☆

アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法
　http://blog.livedoor.jp/dankogai/archives/51172176.html

function (str, n){
    var result = '';
    for(n *= 1; n > 0; n >>>= 1, str += str) if (n & 1) result += str;
    return result;
}

というコードが紹介されていた。なるほどね。
アルゴリズムの基は、以下。

冪乗 - Wikipedia
　http://ja.wikipedia.org/wiki/冪乗

指数 n を二進表記したものを n とし、n の最下位桁を n[0]、最上位桁を n[m]、最下位から数えて k 桁目を n[k] と表記する。

2乗していく値 p := a とし、結果値 v := 1 とする。

k := 0 とする（最下位）。

n[k] が 1 ならば v := v * p とする。

p := p * p

k := k + 1

k ≦ m なら 4. に戻る。

指数 n を二進表記したものを n とし、n の最下位桁を n[0]、最上位桁を n[m]、最下位から数えて k 桁目を n[k] と表記する。

結果値 v := 1 とし、

k := m とする（最上位）。

v := v * v

n[k] が 1 ならば v := v * a とする。

k := k - 1

k ≧ 0 なら 4. に戻る。

それぞれコードに落とすと、

Math_power_d = function(n, m){
  n = Number(n); m = Number(m);
  if(n == 0) return 0;
  if(m == 0) return n;
  var r = 1;
  for(; m>0; m>>>=1, n*=n)
    if(m & 1) r *= n;
  return r;
};

Math_power_u = function(n, m){
  n = Number(n); m = Number(m);
  if(n == 0) return 0;
  if(m == 0) return n;
  var r = n;
  for(; m>0; m<<=1, r*=r)
    if(m.toString(2)[0] == "1") r *= n;
  return r;
};