ワレスの木 (Wallace Tree)について

質問

ワレスの木の加算段数についてです。

下のURLの21ページに、
＞並列度を最大にすると最短で（log3/2 n）段の全加算器を通すことに

とあるんですが、nは入力数でいいんでしょうか？

3入力→1段
4入力→2段
5、6入力→3段
7，8，9入力→4段

になると習ったんですが、(log3/2 n）段だと計算が合いません。
どのように考えればいいんでしょうか。

宜しくお願いします。

参考URL：
http://www.kochi-tech.ac.jp/library/ron/2000/ele/1010317.pdf

回答No.1

irija_bari · ベストアンサー

常用対数を log_(10)x のように記述することにします。
（ご質問の式は log_(3/2)n となります。）

前提条件の違いによるものです。

入力数を n、段数を x とすると、1 段ごとに入力数は 2/3 倍されていきます。
入力数が 1 つになるまでに必要な段数と考えると、
n * (2/3)^x = 1
から、ご質問の式が出てきます。

inaina5 さんの想定では、入力数が 2 つになるまでの段数と考えています。
この場合、式は、
n * (2/3)^x = 2
となります。ただし、この場合の式は最終的に、
x = log_(3/2)n - log_(3/2)2
となり、n が十分に大きいときは log_(3/2)2 を無視しても差し支えないので、
一般的に x = log_(3/2)n と書くのでしょうね。

お礼

ありがとうございます。大変よくわかりました。