RSS

 

RSS


8bitコンピュータで多倍長数の掛け算をする話題が出てた。

ちょっと考察

①基本
Uint8のレジスタ a b c0 c1があって
a x  b ->  c1  c0
掛け算の結果の上位がc1、下位がc0に入る。
これが基本の演算

②16bit数×8bit数
16bit長 に 8bit 長を掛けるには
筆算みたいにやってあげればいいので

  a1 a0
×    b0
―――――
    c1 c0
d2 d1
―――――
c2 c1 c0

a0 × b0  ->  c1 c0
a1 × b0  ->  d2 d1
c1 + d1  ->  carry + c1
carry + d2 -> c2

これで
a1 a0   ×  b0  -> c2 c1 c0
ができた。

③16bit数×16bit数
16bit長 どおしの掛け算は

     a1 a0
×     b1  b0
----------
    c1  c0      <- a0×b0
    d2 d1     <- a1×b1
    e2 e1           <- a0×b1
f3 f2                <- a1×b1 
----------
g3 g2 g1 g0

掛け算が4回。
足し算の回数が7くらいいる。

計算量は多いなぁw








  • コメント (0)
  • トラックバック (0)
トラックバックURL :
http://www.iwai-masaka.jp/tb.cgi/55527