計算理論

計算理論的な何かのメモ。

a*c+b*cの計算回数は加算1回の乗算2回。
それに対し(a+b)*cの計算回数は加算1回の乗算1回で済む。

45*19を導くのに加算だけで行うと 45+45+・・・を19回繰り返す加算。
19*45を導くのに加算だけで行うと 19+19+・・・を45回繰り返す加算。
小学校の授業ではコレ。でも非効率だね!

ala russe法

コンピュータは0と1のみ扱っているのでシフト演算のほうがはるかに速い。
てことでこれを用いてみる。

45*19と19*45は可換であり、結果が同じ。

45を右シフト演算、19を左シフト演算して、右シフト演算側が1になるまで繰り返す。
(二進数表記での右シフトは数を1/2倍、左シフトは数を2倍にする。)

1 45*19
0 22*38
1 11*76
1 5*152
0 2*304
1 1*608

101101は45の二進数変換。
そしてあぶれた分を足せばok。
19+76+152+608=855

加算回数3回、シフト演算回数は||log2(45)||=6回

19を右シフト演算、45を左シフト演算して、右シフト演算側が1になるまで繰り返す。

1 19*45
1 9*90
0 4*180
0 2*360
1 1*720

10011は19の二進数変換。(下から読むのが正しい。)
そしてあふれた分を足せばok。
45+90+720=855

加算回数2回、シフト演算回数は||log2(19)||=5回

下の方が効率的といえる。
結果的に、1であふれている分を加算するので、
二進数変換で1が少ない数字をシフト演算対象にするのが望ましい。

シフト演算は加算に比べればゴミみたいなもので、無視できるほど小さい。

  by ddrer-yossi | 2010-07-30 10:10 | 日常生活

<< 近況 おつさま >>

SEM SKIN - DESIGN by SEM EXE