問題タブ [knuth]

Knuth の「The Art of Computer Programming」のレビューで、以下を読みました。

「非常に『実用的』ということは、将来の CS 専攻者が、C を設計する際のカーニハンの過ちを学ばなければならないことを意味します。特に、for ループが for 条件を繰り返し評価し、while を複製し、他のほとんどの言語の動作と一致しないという悪名高い事実です。 for ループを実装します。」

( http://www.amazon.com/review/R9OVJAJQCP78N/ref=cm_cr_pr_viewpnt#R9OVJAJQCP78N )

この男は何について話しているのですか？while ループの単なるシンタックス シュガーではない for ループをどのように実装できますか?

DonaldKnuthのLiterateProgrammingには、TeXのバグ数の経時変化を示すグラフを正しく覚えていればありました。このグラフは過去10年ほどフラットのままであり、TeXにバグがない可能性があることを示しています。

このグラフを使用して、バグ追跡ソフトウェアの重要性を説明したいと思います。どこかからダウンロードできますか？

TAOCP Volume 1 Edition 3 の演習を行っていますが、次の演習の回答で使用されている構文を理解するのに苦労しています。

第 1 章 演習 8

_{T j} ,s _j ,a _j ,b _jを指定して、正の整数 m & n の最大公約数を計算する

入力を文字列 a ^m b ⁿ (m a の後に n b が続く)で表します。

答え：

A = {a,b,c}、N=5 とします。アルゴリズムは文字列 a ^{gcd(m,n) で終了します}

私が理解に苦しむ部分は、この表をどう解釈するかということです。また、Knuth がこれが文字列 a ^{gcd(m,n) で}終了すると言うとき、 なぜ gcd(m,n) の上付き文字なのですか?

助けてくれてありがとう！

より多くの質問で編集：

T _jとは何ですか -- T = シータであることに注意してください

s _jとは何ですか -- s = phi であることに注意してください

_{列 b j}とa _jをどのように解釈しますか?

なぜクヌースは、ソリューションの新しい表記法を、テキストで説明していない例に切り替えたのですか? ただイライラします。ありがとう！！！

5 ページの下部に「 kをk ⊕ (1 ^{j +1} ) ₂に変更する」というフレーズがあります。2進数でも1の何乗でも1じゃないの？これはタイプミスに違いないと思います。これを報告するためにクヌース博士に電子メールを送信しましたが、何ヶ月も返信が来るとは思っていません。その間、私はこれがどうあるべきかを理解しようとしています。

32 ビット整数演算では、加算と乗算の基本的な演算は暗黙的に mod 2^32 で計算されます。つまり、結果は加算または乗算の最下位ビットになります。

異なるモジュラスで結果を計算したい場合は、異なる言語で任意の数の BigInt クラスを使用できます。値 a,b,c < 2^32 の場合、中間値を 64 ビット long int で計算し、組み込みの % 演算子を使用して正しい答えに減らすことができます。

しかし、C が (2^N)-1 または (2^N)+1 の形式の場合に a*b mod C を効率的に計算するための特別なトリックがあり、64 ビット演算またはBigInt ライブラリであり、任意のモジュラス評価よりも非常に効率的であり、中間乗算を含めた場合に通常 32 ビット int をオーバーフローするケースも適切に計算します。

残念ながら、そのような特殊なケースには迅速な評価方法があると聞いていますが、実際には方法の説明を見つけていません。「それはクヌースにありませんか？」「それはウィキペディアのどこかにありませんか？」私が聞いたつぶやきです。

2147483647 は 2^31 -1 に等しい素数であるため、これは a*b mod 2147483647 の乗算を行う乱数発生器では明らかに一般的な手法です。

そこで専門家に聞いてみます。私が議論を見つけることができないこの巧妙な特殊なケースの乗算と mod の方法は何ですか?

MIXの除算（TAOCP by Knuth）がバイト単位でどのように機能するかを誰かに説明してもらえますか？

メモリ位置1000には。が含まれます|-|0|0|0|2|0|。

操作を実行するとき

レジスタは

rAこれで、との記号がわかりましたが、塗りつぶされrXたバイトはどのような順序で、rAXどの分割が実行されますか？

DIV 1000がすべてのビットを2で割った値になる場合、私は期待します

ここrAには、除算の結果とrX余り（右側から入力）が含まれています。

私はおそらくここで何かが足りないので、Knuthは私がそれを自分で理解できるはずだと思っているようです（したがって、レベル10の質問ですが、私も得られません）が、誰かがここで私を助けてくれますか？

文字列の文字から形成できるすべての英語の単語を見つける必要があります

私は文字の配列を作ることができます

Rubyの文章から4500以上の英語の単語を作るにはどうすればよいですか？

[編集]

問題をいくつかの部分に分割するのが最善かもしれません：

1. 10文字以下の単語の配列のみを作成する
2. 長い単語は個別に検索できます

Donald Knuth には、彼のページで読むべき多数のプログラムがあります。しかし、それらはほとんど「奇妙な」CWEB形式です...

それらを Windows で適切に読めるようにする最善の方法は何でしょうか?

私が取り組んでいる C++ プロジェクトにKnuth シャッフルを実装しています。私はシャッフルから最も偏りのない結果を得ようとしています (そして、私は (疑似) 乱数生成の専門家ではありません)。これが最も偏りのないシャッフルの実装であることを確認したいだけです。

draw_tはバイト型です ( typedef'd to unsigned char)。itemsリスト内のアイテムの数です。以下のコードを含めましたrandom::get( draw_t max )。

私が使用しているランダム関数は、モジュロ バイアスを排除するように変更されています。RAND_MAXに割り当てられrandom::_internal_maxます。

の順列を生成したいのですが、などarray aの効用関数を使用したくありませんjava.util.Collections()。
順列はランダム化する必要があり、すべての順列が発生する可能性がありますが、均等に分散された確率は必要ありません。

次のコードはこれを実現しますが、パフォーマンスは低下します。

質問：
順列の生成に使用される乱数の総数を減らす可能性はありますか？