ホーナーの方法 普及委員会

情報科教育法の授業の中で、「二進法←→十進法」の変換のことが話題になった。学生が作ってきた教材を見て、その変換方法について質問したところ、ちゃんと説明ができていなかったので、いろいろ調べてみたところ、webに、これをちゃんと説明したものが見当たらなかった。

ということで、ここに書いておこうかと思う。

●十進から十進への変換（その１）

このように書くと何か変な気がする。正確には「十進法で表された数 x から、十進法の各桁の数字を求める」方法である。方法は簡単。xを10で割って余りをみると、それが一番右の数字だ。そのときの商をさらに10で割れば、その余りは右から2番目の数字だ。例えば、

813 = 81 * 10 + 3
81 = 8 * 10 + 1

このようにすれば、813から 3, 1, 8 の数字を見つけることができる。

●十進から十進への変換（その２）

では逆に 8, 1, 3 から 813 を組み立ててみよう。これは

8 に 10をかけて1を加えると 81
81 に 10をかけて3を加えると 813

というようになる。

●十進から二進への変換

上記の（その1）を、2で割るように作ればよい。

●二進から十進への変換

上記の（その2）を、2をかけるように作ればよい。

●組み立て除法

数学の授業で「因数定理」というものを教えることがある。というか、普通はこれを教える。「整式 f(x) を (x-α)で割ったときの余りはf(α)である」というものだ。

そして、f(α)を求めるときによく使われるのが「組み立て除法」である。例えば、f(x)= 3*x^4 -2 * x^3 + x^2 -5*x +1 で f(2) を求めるときは、

2　|　　3　　-2　　1　　-5　　　1
---+

----------------------------------

こんな表を書いてから、

2　|　　3　　-2　　1　　-5　　　1
---+
　　　　　　　6　　8　　18　　26
----------------------------------
　　　　3　　4　　9　　13　　27

と計算して　f(2)　= 27 と求める。計算量理論を学ぶと「ホーナーの方法」という名前で出てくることもある。

●二進→十進の再論

ってことは、

101011 を十進法で表すのは、 f(x) = x^5 + x^3 + x + 1 で f(2) を求めることと同じで、

2　|　　1　　0　　1　　0　　1　　1
---+

------------------------------------

と書いて組み立て除法を計算すればいいのです。