問題タブ [knuth]

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

次に例を示します。

1. [00] 2009 年のバイナリ形式...
2. [05] どの文字が...
3. [10] 4 ビット量 -- 半バイト、または 16 進数...
4. [15] キロバイト...
5. [M13] x が 0 と 1 の任意の文字列の場合...
6. [M20] 証明するか反証するか…

[00]、[05]、[10]、[15]、[M13]、[M20] の意味は何ですか?

私が試してみました：

• グーグルtaocp exercises square brackets
• 角かっこで囲まれた数字のパターンを探します。
  • それらは両方とも増加および減少します
  • ほとんどが 5 の倍数ですが、すべてではありません。
  • Mが付いているものは時々現れます
  • M は唯一のプレフィックスです
  • コードは一意ではありません
• グーグル"the art of computer programming" exercises brackets
• グーグル"the art of computer programming" M13
  • M がマイルストーンを意味することを示すhttp://dl.acm.org/citation.cfm?id=1312683を表示します。
• グーグル"the art of computer programming" [00]
• 説明している本の付録を探す
• いくつかの質問の横にある>も考慮してください

運が悪い！

この質問を行った後、正確なカバーの問題のみを解決するために Dancing Links を実装しようとしました。以下はhereから取得して変更したコードです (これは列 - 行構造であり、行 - 列構造が必要でした)。関数の成功した終了ブロックに到達しないことを除いて、正常に動作しますSearch。トレースを試みたところ、これが見つかりました

引き起こしています。例: 次のマトリックスの場合

私のコードcoverは最後の列に失敗しますHeader=4

どうすればこれを克服できますか？ここに完全なコードがあります

アセンブリ言語として MIX が使用されている Donald Knuth の The Art of Programming, Volume 1 を読んでいます。Knuth が MIX の算術演算について説明しているセクションで、減算、乗算、および除算の演算がどのように実行されるかを理解していませんでした。

たとえば、教科書には次のように書かれています。

レジスタ A は次のワード コード-| 1234 | 0 | 0 | 9を持ち、たとえば M というメモリ セルは次のワード コードを持ちます-| 2000 | 150 | 0。

この本は、AMを実行すると結果が次のようになると述べています+| 766 | 149|?。

MIXでは、記憶は単語に分割されます。各ワードには次のものがあります。 最初のフィールドは符号 (+ または -) を表し
ます。次の 2 バイトはアドレスを保持します。
次のバイトはインデックスを表し、5 番目のバイトはフィールド指定用です。
最後のバイトはオペコード用です。
この本は、AMを実行すると結果が次のようになると述べています+| 766 | 149|?。

誰でもこれで私を助けることができますか？

簡単に言えば、1986 年にあるインタビュアーが Donald Knuth に、入力にテキストと数字 N を取り、最もよく使われる N 個の単語を頻度順に並べてリストするプログラムを書くように依頼しました。Knuth は 10 ページの Pascal プログラムを作成し、Douglas McIlroy は次の 6 行のシェル スクリプトで応答しました。

全文はhttp://www.leancrew.com/all-this/2011/12/more-shell-less-egg/でお読みください。

もちろん、両者の目標は大きく異なっていました。Knuth は、読み書きのできるプログラミングの概念を示し、すべてをゼロから作成しました。一方、McIlroy は、いくつかの一般的な UNIX ユーティリティを使用して、最短のソース コードを作成しました。

私の質問は：それはどれほど悪いですか？
(純粋にランタイム速度の観点から言えば、6 行のコードは 10 ページよりも理解しやすく維持しやすいという点で、私たち全員が同意していると確信しているため、プログラミングの知識があるかどうかは関係ありません。)

sort -rn | sed ${1}q一般的な単語を抽出する最も効率的な方法ではないことは理解できますが、何が問題なのtr -sc A-za-z '\n' | tr A-Z a-zですか? 私にはかなり良さそうです。についてsort | uniq -c、それは周波数を決定するのに非常に遅い方法ですか?

いくつかの考慮事項:

• tr線形時間にする必要があります (?)
• sort確信は持てませんが、それほど悪くはないと思います
• uniq線形時間も必要です
• 生成プロセスは線形時間 (プロセス数) である必要があります

Fascicle 1 の Knuth のプログラム P を再実装しています: 最初の 500 個の素数を生成します。プログラムは最初の 25 個の素数を問題なく生成します。そのコードは以下のとおりです。

Mthree の比較を 25 に減らすと、プログラムは問題ありません。それ以上の場合、プログラムは失敗するか、printf でハングします。

私はそれを組み立てています：

また、printf を呼び出さなくても、gdb の "end" にブレークポイントを設定するとわかるように、最初の 500 個の素数が正常に生成されることも付け加えることができます。

printf を呼び出そうとするとすぐに失敗するので、スタックで何かばかげたことをしていると思います。

元のMIX アーキテクチャは 6 ビット バイトを特徴とし、メモリは 31 ビット ワード (5 バイトと符号ビット) としてアドレス指定されます。思考練習として、C 言語がこの環境でどのように機能するのか疑問に思っています。

• char には少なくとも 8 ビットがあります (C99 仕様の附属書 E)
• C99 仕様セクション 6.3.2.3 (「ポインター」) パラグラフ 8 には、「オブジェクトへのポインターが文字型へのポインターに変換されると、結果はオブジェクトのアドレス指定された最下位バイトを指します。結果の連続的なインクリメント、アップオブジェクトのサイズに、オブジェクトの残りのバイトへのポインターを生成します。」この要件についての私の解釈は、「memcpy(&dst_obj, &src_obj, sizeof(src_obj))」を支えているというものです。

私が考えることができるアプローチ：

1. char を 31 ビットにするため、"char*" による間接参照は単純なメモリ アクセスです。しかし、これは文字列を無駄にします（明らかに8ビット文字が必要なため、POSIXに準拠していないことを意味します）
2. 3 つの 8 ビット文字を 1 つのワードにパックし、7 ビットを無視します。「char*」は、ワード アドレスとその中の文字インデックスで構成される場合があります。ただし、これは 6.3.2.3 に違反しているようです。つまり、memcpy() は無視されたビットをスキップする必要があります (実際のオブジェクト タイプではおそらく意味がある)。
3. char を単語に完全にパックします。たとえば、4 番目の 8 ビット char は、word 0 に 7 ビット、word 1 に 1 ビットを持ちます。これにも memcpy() 問題があるため、ワード長に一致するように宣言されています。

したがって、すべてのオブジェクトのサイズが char の倍数である 31 ビット char を使用するという最初の (無駄な) オプションが残っているようです。このように読むのは正しいですか?