全文

(1)

算法の設計と解析

講義日:11 月 15 日

計算回数

計算する際,計算時間の短縮のため,より計算回数が少なくなる計算方法を考える必要がある.ここでは計算 機で計算するための効率的な計算方法について述べる.

1

352 × 631

の計算

¶ ³

352 × 631

を考える.

R := 10(Radix

基数)とし,この式を以下のように考える.

(3R 2 + 5R + 2) × (6R 2 + 3R + 1)

また,10進数は以下のように表す.

(a n , a n−1 , · · · , a 0 ) R

R == 10, 0 a i 9, a n 6= 0

このとき,

352 :=

X n i=0

a i R i , 631 :=

X m j=0

b j R j , r :=

X N

k=0

c k R k

と表すことができる.

352

˜

631 R == 10 R 1 2 2 2R R 5 1 + 3 2 11 1R + 1R R 6 2 + 5 3 + 3 1 30 0R + 3R R 3 3 + 5 6 39 9R + 3R R 3 6 18 8R + 1R R

0

5

4 3

2 1

˜

˜ ˜

˜

˜

˜ ˜

˜

˜

0

1 2

2 3

3

4 4 5

(a)

2 2 11 11 1 30 30 + 1 = 31 1 39 39 + 3 = 42 2 18 18 + 4 = 22 2

2 (b)

1:

計算の仕方

よって

352 × 631

の計算結果は

2 + R + R 2 + 2R 3 + 2R 4 + 2R 5 = (222112) R , R := 10

となる.

µ ´

1

(2)

Radix 変換

10

進数から

2

進数,2進数から

16

進数のように,Radix(基数)を変換することである.

R ←→ R 0

に変換する場合

(a n , a n−1 , · · · , a 0 ) R , 0 a i R 1, a n 6= 0

←→ (b m , b m−1 , · · · , b 0 ) 0 R , 0 b i R 0 1, b m 6= 0

となるような

a n , · · · , b m , · · ·

を求める.

2

R := 2 8

から

R := 2

への

Radix

変換

¶ ³

R := 2 8

における

255

は,2進数で表すと

11111111

となる.

µ ´

いま

R 6= 0

とし,(a

n , a n−1 , · · · , a 0 ) R

(b m , b m−1 , · · · , b 0 ) R

との積

(c k , c k−1 , · · · , c 0 ) R

を考える.ここでは

c r = X

i+j=r

a i b j

= X r i=0

a i b r−i

を計算する.これを重畳和

(convolution)

という.また,

c r = F (f(a 0 , · · · , a n ) · g(b 0 , · · · , b m )) f : a 0 , · · · , a n

を変数とする関数

g : b 0 , · · · , b n

を変数とする関数

と表すと,c

r

f

の値,gの値の積を引数をする関数

F

の値とすることができる.

Fourier 変換

x R

の関数に対して

F(w) = Z

−∞

f (x)e −ixw dx

とする.

h(x) = Z

−∞

f (y)g(x y)dy H (w) =

Z

−∞

h(x)e −ixw dx

とすると,

H (w) = F (w)G(w)

2

(3)

となる.積分

R

P

に置き換えて

F m = X

f n w mn (1)

h g = X

k

f k g r−k

とする.同様に

H r = F r G r (2)

h n = X

h m κ mn (3)

となる.

(1)

f

g

とに対応

(2)

f × g

に対応

(3)

F

に対応

係数が実数のとき

w : w = e −i

mn2N

κ : k = w = e i

mn2N

ただし

N max(m, n), N = 2 k

である.

係数が整数のとき

重畳和の

DFT

による計算法を用いる.

w : w =

素数

κ : k = 1

w = w −1

とする.

3

Updating...

参照

Updating...

関連した話題 :