チャレンジ 4を楽しんでいただけたと思います。今後、何か良いチャレンジのアイデアがありましたら、ぜひ教えてください。私は常に良い素材を探しています。
おめでとうございます、 @landon さん！1,000 桁の数字 100 組（9.88 秒）と最長の数字（7,150）のチャレンジの両方で、最速（スタッフ以外）のエントリーでした。これは、1,000 桁の数字 100 組すべてを 10 秒未満で読み取ることができる唯一のスクリプトであるだけでなく（次に近いのは 10 秒しか読み取れませんでした）、次に近いエントリの 3.5 倍の 2 つの数字を掛け合わせることもできました！さらに、これはすべてのスクリプト（スタッフおよびスタッフ以外）の中で最も短く、文字数は 1,000 文字強でした。以下のスクリプトに含めました。4 つのチャレンジ後のポイント合計は次のとおりです。
大きな数字の乗算について話す前に、数字の文字列をアンパックまたはベクトル化する、つまり数字の文字列を数字のベクトルに変換することについて説明しましょう。先月見たように、ループ内でサブストリングを使用して数字の文字列を 1 つずつ解析すると、非常に時間がかかります。この場合、2 つの一般的な代替手段が残ります。1) 文字列を個々の単位に分解し、それらをベクトルに変換できる形式にまとめ直す (たとえば、 解析するを使用)、または 2) パターン マッチングを使用する。私としては、最初はアプローチ 1 を使用するつもりです。何年もの間、私は JSL パターン マッチング関数について学ぶことに抵抗してきました。労力が大きすぎるし、情報や例が少なすぎるし、私は怠け者でした。Regex 関数があれば必要なものはすべて手に入ると考えていました。Regex関数はよく知っているからです。もうそうではありません。
これらのチャレンジで、パターン マッチングの速度と効率に目覚めました。これらの関数の開発者であり、チャレンジの常連でもあるクレイグ・ヘイルズから説明を受けたように、JSL のパターン マッチング ルーチンは正規表現の基礎となっています。その効率性を実証するには、4 つの異なるベクトル化方法を比較するベクトル化の例.JSLのコードを実行してください。また、スクリプトには、長い乱数列を生成する短い関数も含めました。10,000 個の数字の文字列の場合、ループで数字を 1 つずつ解析する方法が最も遅く、私のマシンでは約 11 秒かかります。Wordsと連結リストを使用して数字を分解して再構築し、ベクトルに解析できる文字列にすると、はるかに速くなります (0.0965 秒)。
Doing the same thing using 正規表現 and 解析する is slightly better than that (0.08543). Pattern matching reduces this time by an amazing 4X (0.02179)! While the time differences are minuscule for 50,000 digits, if we consider 5,000,000 digits, both parsing approaches take about 10 minutes whereas pattern matching takes 2 seconds, scaling nearly linearly, unlike the other methods! If you want to learn more about pattern matching in JSL, take a look at the scripts written by クレイグ・ヘイルズ or デイビッド・バーナム (who has 彼自身のブログ投稿には、より多くの情報と例がいくつか掲載されています。.)
乗算ルーチンに進みます。すべてのベクトル化にパターン マッチングが使用されます。さらに、最後のチャレンジの最速の加算アルゴリズムが最初の例で使用されます。最初のアプローチ ( 乗算ビッグスロー.JSL ) では、これまでのチャレンジで学習したもの以外は何も使用しません。一度に 2 つの数字を乗算し、被乗数と乗数の位置に応じてゼロを追加します (たとえば、100 の位の数字を 10 の位の数字で乗算すると、5 つのゼロが追加されます)。関数は最初の数字が大きくなるように入力を順序付けますが、これには利点がありません。実行される操作の数は同じです。ただし、最後の例ではこれが変わります。関数は遅く、100 桁の数字 100 個を処理するのに 30 秒近くかかります。
乗算大きく速く.JSLでは、レジスタの桁数が 1 から 7 に増えます。これは、JSL がオーバーフローせずに表現できる桁数の約半分です。この選択の理由は、結果が 14 桁になる可能性がある 2 つの大きな 7 桁の数字を乗算するときに明らかになります。7 桁のレジスタには 14 桁が含まれる可能性があるため、最後の例で使用した加算ルーチンを変更して、7 桁目を超える数字が次のレジスタに繰り越されるようにする必要があります。それにもかかわらず、正の数だけを考慮すればよいため、結果のコードはかなり短くなります。さらに、100 桁の数字のペア 100 個を乗算すると、結果が大幅に改善されます (0.04375 秒)。この実装では、1000 桁の数字のペア 100 個を乗算する場合も、妥当な結果が得られます (1.54 秒)。
1 つの簡単な変更で、さらに高速化できます。一度に 1 つのレジスタを乗算するのではなく、 乗算ビッグ最速.JSLは JSL マトリックス演算を使用して、短い数値の各レジスタを大きい数値全体で乗算します。このアプローチは以前のものより高速で、1,000 桁のペア 100 個で 0.3015 秒となり、5 倍の改善になります。
さらに高速化することもできます。ファイルマルチプライビッグ – Brady.JSLは、1,000 桁の数値の乗算では若干遅いものの、数値のサイズが約 2,000 桁以上になるとパフォーマンスが向上しました。これは、乗算と加算を同じループで実行できるように演算の順序を変更することで実現しました。この詳細についてはここでは説明しません。しかし、 @brady_brady は、興味があればこの投稿に追加できる短い記事を喜んで書くと言っています。高速化? おそらく。暗号学で一般的に使用される 2 つの注目すべき乗算アルゴリズムにより、乗算演算の回数が O(n 2 ) からO(n 1.58 ) 以下に削減されます。これらは大きな数値に対してより多くの加算演算を必要とするため、JSL で高速化できるかどうかはわかりません。この記事の時点では、これらのアルゴリズムのどちらも高速な JSL バージョンを実装しようとしましたが、できませんでした。
2020年8月1日: Thanks to クレイグ・ヘイルズ for catching a bug in 乗算ビッグ最速.JSL. I have corrected the problem. I have also added Craige's multiplyBig script, which I intended to do but forgot. He uses lookup tables as a way to speed the algorithm (with a few caveats). His script is thoroughly comment, as usual.
