the art of computer programming 1.2.2 を読む

対数を使う場合コンピュータの分野では2進対数が用いられるが、

その最大の理由は、コンピュータアルゴリズムが2方向の分岐を多用するから。

if-elseに代表されるように大なり小なりの判定や、ある文字列sとtが同じ文字列かどうかの判定などはyesかnoの2方向の分岐だから。

 

log_{10}xの答えを2進表現で表現する方法の例

ここではx=27とする。

1 \le \frac{27}{10^1} \lt 10

    x_0 = 2.7      b_0=1     b_0は上記式の\frac{x}{10^n}n

2.7^2 \lt 10なので

    x_1=2.7^2=7.29    b_1=0

7.29^2 \ge 10なので

    x_2=5.314    b_2=1

5.314^2 \ge 10なので

    x_3=2.8238    b_3=1

 

これを⑧まで続けた結果、{b_0,b_1,...,b_7} = {1,0,1,1,0,1,1,1}となった。

これを10進数に変換すると1.4296875となり、

log_{10}27 = 1.43136なので、0.0016...の誤差となった。

 

回数を増やしたり、6桁で丸めるなどの工夫を行えばより正確な値をだせる。

 

演習問題

解いたもので回答がなかったものを書く。

 

5.[05]

    n=a_k*2^k+...a_2*2^2+a_1*2^1+a_0*2^0, m=b_k+2^k+...b_2*2^2+b_1*2^1+b_0*2^0とする。

    ただし、a_i, b_iは0か1である。

    2進数での有理数\frac{n}{m}である。

    整数は\frac{n}{2^0}で表現でき、小数は\frac{2^0}{m}で表現できる。

    ただし、\frac{n}{m}で表現できない値(0.1など)は2進数で表現できない。

    また、数字の列の末尾が無限に続く1にならないもの。

    (2)に変わる表現は

    n+\frac{d_1}{2}+\frac{d_2}{4}+...+\frac{d_k}{2^k} \le x \lt n+\frac{d_1}{2}+\frac{d_2}{4}+...+\frac{d_k}{2^k}+\frac{1}{2^k}