プロフィール

島田圭二

Author:島田圭二
Follow shimanp on Twitter

カレンダー
10 | 2017/11 | 12
- - - 1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 - -
読断と変見内検索
訪問ありがとうございます
最近のコメント
最近のトラックバック
関連リンク
カテゴリー
月別アーカイブ


スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。


スポンサー広告 | 【--------(--) --:--:--】 | Trackback(-) | Comments(-)
べき乗アルゴリズム - 下位桁編
アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 - 404 Blog Not Found
function (str, n){
var result = '';
for(n *= 1; n > 0; n >>>= 1, str += str) if (n & 1) result += str;
return result;
}

通常、べき乗の計算はべき乗の数だけ掛け合わせて計算を行う。
例えば24の場合、2×2×2×2となり、2を4つ掛け合わせる。
この計算の仕方だとべき乗の数が増えれば増えただけ掛け合わせることになる。
しかし、冒頭のアルゴリズムを使用するとlog n回で済み、処理が早くなるようだ。
でもwikiのべき乗アルゴリズムを見てもいまいち、何をやっているのかよくわからない。。。
とりあえず、wiki通りにjavaで書いてみた。
public long beki(long p, int n) {
long v = 1;
for(; n > 0; n >>>= 1){
if((n & 1)==1){
v*=p;
}
p*=p;
}
return v;
}

一応正常に動作するようだが、まだよくわかっていない、、、がなんとか説明してみることにする。

プログラムはとりあえず置いておいて、べき乗の性質から


wikiにもあるがべき乗には、
(ax)2 = a2x
という性質がある。この性質が重要。
具体的な数字を当てはめると、
(22)2 = 22*2
となる。つまりこれは(22)2 = 24ということである。
この考えで行くと
28 は ((22)2)2となる。
実はこの時点で計算が大分減っていることに気づくと思う。
普通に計算すると28は2×2×2×2×2×2×2×2と2を7回掛ける必要がある。
しかし、((22)2)2とすると、まず、22の計算をして4になり次に、4×4の計算をして16になり、
最後に16×16の計算をして256となり、3回の計算で済む。
なんと7回の計算が3回に減るのである。このアルゴリズムではこの特性を大いに利用する。

でこの性質をどうやって利用するの?


とりあえず、単純なべき乗の計算の効率化はできた。
しかし、この計算を行うには、べき乗の値に4乗が含まれているか?
8乗が含まれているか?と分析しなければならない。
どういうことかというと、wikiと同じ、a43について考えてみる。
a43 = a32+8+2+1 = a32×a8×a2×a1
と、43乗には32乗、8乗、2乗、1乗が含まれていることになる。
これをどうやって知るの?ということである。

ここで2進数登場


べき乗を分析するのには2進数を使う。
wikiにもあるけど、とりあえず、1,2,4,8,16,32を2進数にしてみる。
10進→2進
1    →1
2    →10
4    →100
8    →1000
16   →10000
32   →100000
で、43を2進数にしてみる
43 → 101011
43の2進数の値をよく見ると、1,2,8,32が含まれていることが分かる。
まず、101011の一桁目が1、を表す、で二桁目が2を表す、で三桁目が4を表すが0であるので、
43には4は含まれていないことになる。で同様に、四桁目が8で、5桁目が16で0なので含まれず、
最後の五桁目が32にとなる。
そうつまり、2進数にすると、何が含まれているのかが分かるのである。
何が含まれているのかが分かれば効率的な計算方法を利用することができる。

でようやくここからプログラムの説明に戻る


public long beki(long p, int n) {
long v = 1;
for(; n > 0; n >>>= 1){
if((n & 1)==1){
v*=p;
}
p*=p;
}
return v;
}
まず、for文の説明から。
for(; n > 0; n >>>= 1){
これはべき乗nを右にシフトしていってnが0以下になるまで回り続けろということである。
例えば、べき乗が43の場合、2進数は101011となる。
この101011を右に1シフトすると、10101となる。さらにシフトすると、1010となり、次に101、10、1、そして最後に0となりfor文は終了する。
なぜ、このようなfor文にするかというと、先ほどのべき乗の分析が関係してくる。
べき乗の分析は2進数にして、ある桁が1かどうかで含まれているかどうかを判断している。
なのでfor文で一つずつ右にシフトし、一桁目が1かどうか、次のifで判断しているのである。
で1の場合は、べき乗の元の値を結果値に掛ける。
v*=p;
ただし、元の値pは元の値のままでなく、for文が回る度にべき乗となる。
p*=p
例えば、元の値が2で1回まわったら2×2で4になり、2回まわったら4×4で16になる。
何でこんなことをしているかというと、べき乗の性質と効率的計算を思い出して欲しい。
(ax)2 = a2x
である。
つまり、べき乗を2進数にして一桁目から分析していって、1だったら、その桁にふさわしい値を
結果に掛けていってるのである。
例えば元の値が2で3桁目が1の場合、3桁目にはfor文は2回まわっているので、
2×2で4、4×4で16となり、結果値に16を掛けるのである。

以上、最後らへんはちょっと無理やりだったけど、眠いのでこれで終了。
てか、たったこれだけのプログラムを理解してまとめるのに半日もかかっちまったぜ。。。ふっ。
スポンサーサイト


アルゴリズム | 【2009-02-02(Mon) 02:53:12】 | Trackback:(0) | Comments:(0)
コメントの投稿
管理者にだけ表示を許可する

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。