問題タブ [taocp]

私はMMIXを学んでいるので、それ自体に1を追加して結果を出力する簡単なプログラムを作成してみました。残念ながら、何も印刷されません。これが私のプログラムです：

私は何を間違っていますか？

サー・ドナルド・クヌースによる「The Art Of Computer Programming」シリーズを読むことにしました。

あなたの経験に基づいて、どの巻から始めるのが良いか、 (他の巻と比較して)より簡単なものを提案してください。

私は急いですべてを学びたいわけではないので、どのタイプのボリュームから始めても問題ありません。

区間[0,1]にガウス分布の乱数ジェネレーターを実装しようとしています。

これは、クヌースのTAOCP第3版122ページの第2巻にあるアルゴリズムの非常に単純な実装です。

問題は、rand_gauss（）が間隔[0,1]外の値を返すことがあることです。

古典的なアルゴリズムの本 (TAOCP、CLR) (およびfxtbookなどのそれほど古典的ではない本) は、命令型アルゴリズムでいっぱいです。これは、組み合わせ生成 (アルゴリズムで配列インデックスと配列値の両方が使用される) や共用体検索アルゴリズムなど、実装が配列に大きく基づいているアルゴリズムで最も明白です。

これらのアルゴリズムの最悪の場合の複雑さの分析は、O(1) である配列アクセスに依存します。Clojure のように、配列を配列っぽい永続構造に置き換えると、配列アクセスは O(1) ではなくなり、それらのアルゴリズムの複雑さの分析は有効ではなくなります。

これは私に次の質問をもたらします: 純粋な関数型プログラミングは古典的なアルゴリズムの文献と互換性がありませんか?

Art of Computer Programmingの、485ページの下部にあります。

次数mのBツリーがあり、N個のキーがあるとすると、N+1の葉がレベルlに表示されます。

レベル1、2、3 ...のノード数は、少なくとも2,2 [m / 2]、2 [m / 2] ^2..です。

（ここで[]は上限を示します）

そしてKnuthは与える

N + 1> = 2 [m / 2] ^（l-1）

私の質問は：

これはN+1> = 2 + 2 [m / 2] +2 [m / 2] ^ 2 + ... + 2 [m / 2] ^（l-1）ではありませんか？

（l-1）レベルのノードのみを考慮に入れることのポイントは何ですか？

わかりました、私は困惑しています。TAOCP vol1、第 3 版、セクション 1.3.2「The MIX Assembly language」は、配列の最大値を見つけるための簡単なアセンブリ プログラムを提供します。プログラムは、145 ページに、各命令が実行されると思われる回数と共に示されています。次のページには、「[...] サブルーチンを実行する時間の長さ; それは (5+5n+3A)u [...] です」と書かれています。

しかし: リストに示されているカウントを実際に合計すると、係数 (4+4n+2A) になります。このような不一致は、他のアルゴリズムでも発生します。たとえば、セクション 1.3.3 のプログラム A の分析では、Knuth は「単純な加算によって [..] (7+5A+...)」と書いています。実際に「単純足し算」をすると、(5+3A+…)

ここで何が起こっているのですか？

これは、括弧内のテキストからのカウントを横に並べた MIX コードです。入力しやすいように、ラベル名を 2 文字に短縮しました

クヌースの本TAOCPを読んでいます。そして、レジスタを使った簡単な数学演算を学んでいます。そして、減算操作の例があります：

-1234-(-2000) = 766 であることは理解していますが、どのように (0 | 0) - 150 = 149 ??

なぜ 9 - 0 = ?

これらは「詰め込まれた」言葉です。そして多分私はそれらについてもっと読む必要があります. または、誰でも説明できますか？

1.2.1数学的帰納法のセクションでは、Knuthは、P（n）がすべての正の整数nに対して真であることを証明するために、2段階のプロセスとして数学的帰納法を示しています。

a）P（1）が真であることを証明します。

b）「すべてのP（1）、P（2）、...、P（n）が真である場合、P（n + 1）も真である」という証明を与える。

私はそれについて深刻な疑いを持っています。確かに、私はポイントb）が次のようになるべきだと信じています。

b）「P（n）が真の場合、P（n + 1）も真である」という証明を与える。ここでの主な違いは、P（n-1）などではなく、P（n）が真であると想定しているだけであるということです。

しかし、これらの本は古く、多くの人に読まれています（ほとんどの本は私よりずっと賢いです^^）。

それで、ここでの私の混乱は何ですか？

Donald Knuth の Art of Computer Programming の第 1 巻を読んでいます。今、すべての数学が説明されている最初の部分を読み終えました。とても楽しかったです。残念ながら、p。MIX121彼は、実際の機械語に基づいて呼び出されたこの架空の機械語の説明を開始し、その後、すべてのアルゴリズムを説明します.クヌース氏は私を完全に失いました.

MIXここに誰かが「話し」、それを理解するのを手伝ってくれることを願っています. 具体的には、彼はさまざまな操作を説明し、例を示し始めたところで私を失いました (p. 125 以降)。

Knuth は、こ​​の「命令形式」を次の形式で使用します。

彼はまた、異なるバイトが何を意味するのかを説明しています:

したがって、右側のバイトは実行される操作です (たとえば、LDA「レジスタ A のロード」)。F バイトは、8L + R を使用したフィールド指定 (L:R) を持つ操作コードの変更です (たとえば、C=8 および F=11 は、「(1:3) フィールドでレジスタをロードします)。その後、+/- AA はアドレスで、I はアドレスを変更するためのインデックス指定です。

まあ、これは私にとってある種の意味があります。しかし、Knuth はいくつかの例を示しています。最初の例はいくつかのビットを除いて理解できますが、2 番目の例の最後の 3 つについて頭を悩ませることはできず、以下の例 3 のより難しい操作からは何もわかりません。

最初の例を次に示します。

LDA 2000完全な単語をロードするだけで、レジスタ A に完全に表示されrAます。2 番目のLDA 2000(1:5)ものは、2 番目のビット (インデックス 1 ) から最後 (インデックス 5) までのすべてをロードします。これが、プラス記号を除くすべてがロードされる理由です。3 つ目はLDA 2000(3:5)、3 番目のバイトから最後のバイトまですべてをロードするだけです。またLDA 2000(0:3)、（4番目の例）意味があります。-803 をコピーして - を取り、80 と 3 を最後に配置します。

これまでのところ、番号 5 では、同じロジックに従うとLDA2000(4:4)、4 番目のバイトのみが転送されます。それは確かに最後の位置にしました。ただしLDA 2000(1:1)、最初のバイト (符号) のみをコピーする必要があります。これは奇妙です。最初の値が - ではなく + なのはなぜですか (私は - だけがコピーされると思っていました)。他の値がすべて 0 で、最後の値が疑問符なのはなぜですか?

次に、彼は操作STA(ストア A)で 2 番目の例を示します。

繰り返しますがSTA 2000、STA 2000(1:5)とSTA 2000(5:5)は同じロジックで意味をなします。ただし、Knuth はSTA 2000(2:2). レジスタ A の 7 に相当する 2 番目のバイトがコピーされることを期待するでしょう- 1 0 3 4 5。私はこれらを何時間も見てきましたが、これがどのようにして、またはこの 1 つに続く 2 つの例 (STA 2000(2:3)およびSTA 2000(0:1)) が表示されている場所の内容になるのかわかりません。

ここにいる誰かが、これらの最後の 3 つに光を当ててくれることを願っています。

ADDさらに、 、 、 、 、SUB、MUL、の操作を説明するページにも大きな問題がありますDIV。3 番目の例を参照してください。

この 3 番目の例は、理解するための私の最終的な目標であり、現時点ではまったく意味がありません。彼のアルゴリズムを引き続き使用したいので、これは非常にイライラしますが、理解できなければMIX残りの部分を理解することはできません!

ここにいる誰かがMIX、私が見ていない何かについてのコースを受講したり、見たりして、彼または彼女の知識と洞察を喜んで共有してくれることを願っています!