最初に、文字列を ASCII コードのベクトルとしてスタックにセットします。
1: [84, 101, 115, ..., 51]
.
"Testing, 1, 2, 3 RET
ちなみに " キーは $ のように、代数形式入力を開始するので、 アポストロフィーを打つ必要はありませんでした。 さらに、" で閉じるのも省略できます。 (式の最後での ) や ] のように、 閉じるデリミタ全てに同じ事が言えます。)
ここで2つの異なるアプローチをお見せします。 まず、入力ベクトルが [a, b, c, d] なら、 ハッシュコードは 3 (3 (3a + b) + c) + d = 27a + 9b + 3c + d です。 言換えれば、「3 の降べき」×「ASCII コード」の合計です。
2: [84, 101, 115, ..., 51] 2: [84, 101, 115, ..., 51]
1: 16 1: [15, 14, 13, ..., 0]
. .
RET v l v x 16 RET -
2: [84, 101, 115, ..., 51] 1: 1960915098 1: 121
1: [14348907, ..., 1] . .
.
3 TAB V M ^ * 511 %
またしても * は計算の大部分をエレガントに要約しています。 でも更にエレガントな方法があって、 それは式 3 $$ + $ をベクトル全体にまとめ作用させるのです。 この式が 第1引数 × 3 + 第2引数 を計算する 2引数の関数を表すことを 思い出してください。
1: [84, 101, 115, ..., 51] 1: 1960915098
. .
"Testing, 1, 2, 3 RET V R ' 3$$+$ RET
10進計算の練習をやれば慣れるでしょう。 基本的に、今われわれは基数3の桁ベクトルを整数に変換しています。 ただこの場合「桁」は現実の桁よりもずっと大きいです。
再度 511 % とタイプして結果を縮小する代りに、 もっと利口に考えることができて、 巨大な整数を計算して最後に剰余を計算するより 毎回剰余を計算しても結果に影響しないことに気付きます。 これは演算回数が増えることを意味しますが、 演算する数値が小さいままなので計算は速くなります。
1: [84, 101, 115, ..., 51] 1: 121
. .
"Testing, 1, 2, 3 RET V R ' (3$$+$)%511 RET
これでどうしてうまくいくのでしょうか? 2ステップの計算 3 (3a + b) + c を考えてください。 511 の剰余を取るということは、 511 を必要回数だけ減じて結果を望む範囲に入れるということです。 従って、毎回剰余を取ったときの結果は、 適当な整数 m と n に対して
3 (3 a + b - 511 m) + c - 511 n
分配法則によって展開すると、
9 a + 3 b + c - 511*3 m - 511 n
後の式の m の項は余計です。 なぜならどんな場合でも n の項にまとめる事ができます。 それで n' = 3m + n を使って式変形すると、
9 a + 3 b + c - 511 n'
これは計算の最後に 1度だけ剰余を取る式そのものです。 ゆえに、2つの方法は本質的に等しいのです。
この後のチュートリアルで、modulo forms を学びますが、
これは中間結果を毎回減量するアイデアを自動化します???。
(訳注: 原文は the idea of reducing every intermediate result modulo some value M.)
Go to the first, previous, next, last section, table of contents.
利用度数