マルチテープチューリングマシンでのベース変換の時間複雑度はどのくらいですか?

ベース変換は、2つの固定された基底で表現間の整数を変換する際の問題です。一般性を失うことなく、比較的プライムな基盤の場合を考慮する。ベースが固定されていてもすべてのケースを扱うことができる単一のタイプのマシンを想像する方が簡単だと思うので、ベース$
b $の数字は$ lceil log_2 {(b)} rceil $
-bitの単語を使用して、マルチテープチューリングマシンにバイナリの入力と出力のアルファベットを付けることができます。しかし、等価的に我々は入力と出力テープのアルファベットのサイズがソースとターゲットのベースと一致するマシンを構築することができます。

基本変換は本質的に2次の時間よりも計算可能であることが知られているか?

この質問は何度も聞かれましたが、私が見つけることができるすべての参考文献は実用的な文脈の中にあります。私はそれが準線形の時間に達成できるという主張を見てきましたが、モデルに関する仮定がそのような議論ではしばしば言い表されないので、これがどのように機能するのか理解できません。

ベストアンサー

ベース変換は時間$ O(M(n) log n)$で行うことができます。ここで、$ M(n)$は2つの$ n
$ビット整数の乗算の時間複雑度の範囲です。 ($ M(n)$は単調で、$ 2M(n) le M(2n)$です。

The standard divide-and-conquer algorithms are described e.g. in
Brent&Zimmermann, Modern computer arithmetic, and go
as follows:

  1. バイナリからベース$ b $への変換

Let $a$ be the input number, of length $n$. By repeated
squaring, compute the sequence $b$, $b^2$, $b^4$, $b^8$, …,
$b^{2^k}$, where $klelog n$ is such that $a

Using division with remainder, compute $a_0,a_1

That is, in the second stage, compute
$a_{00},a_{01},a_{10},a_{11}

($ a $は基底$ b ^ {2 ^ k} $における独自の展開です。最初の段階の後、$ a_1a_0 $は基底$ b
^ {2 ^ {k-1}} $での$ a $の展開です第2段階の後、基底$ b ^ {2 ^ {k-2}} $などに$ a
$を展開します。

実行時間は $$ O(M(n)+ log n)+ $ M(n)+ 2M(n/2)+ 4M

  1. ベース$ b $からバ​​イナリへの変換

上のプロセスを逆にする:最初の段階で、ベース$ b $拡張$ a_ma_ {m-1} dots a_0
$が与えられた場合、要素を$ a_ {2i + 1} b + a_ {2i} $ベース$ b ^ 2
$拡張を形成する。第2段階では、$ b ^ 2 $の乗算を使用してブロックをより大きなブロックに結合し、ベース$ b ^ 4
$拡張を取得します。 $ log n $ stagesの後に、1つの番号があります。実行時間は上記のとおりです。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です