ミドルスクエア法

数学とコンピュータサイエンスにおいて、中間二乗法は疑似乱数を生成する方法です。実際には、周期が通常非常に短く、いくつかの重大な弱点があるため、多くの実用的な目的にとって非常に欠陥のある方法です。中間二乗法は、十分な回数繰り返されると、同じ数字を繰り返し生成し始めるか、シーケンス内の前の数字に戻って無限にループします。

この方法はジョン・フォン・ノイマンによって発明され、1949年の会議で彼によって説明されました。^[1]

1949 年の講演で、フォン・ノイマンは「乱数を生成する算術的手法を考える人は、もちろん罪深い状態にある」と皮肉を言った。彼が言いたかったのは、真の「乱数」は存在せず、それを生成する手段があるだけで、「中二乗法のような厳密な算術的手順は、そのような方法ではない」ということであると彼は詳しく述べた。それでも、彼はこれらの方法が、パンチ カードから「真の」乱数を読み取るよりも何百倍も速いことを発見した。これは彼のENIAC研究にとって実用的な重要性を持っていた。彼は中二乗シーケンスの「破壊」が、簡単に検出できるため、中二乗シーケンスの有利な要因であると判断した。「検出されない短いサイクルの出現を常に恐れている」。^[1] ニコラス・メトロポリスは、「中二乗法」で 38 ビットの数値を使用することで、「破壊」される前の 750,000 桁のシーケンスを報告した。^[2]

イヴァル・エケランドの著書『壊れたサイコロ』には、1240年から1250年の間に、エドヴィン兄弟という名で知られるフランシスコ会の修道士によってこの方法が発明された経緯が詳しく記されている。 ^[3]おそらく、その写本は現在は失われているが、ホルヘ・ルイス・ボルヘスがバチカン図書館で作成した写本をエケランドに送った。

ミドルスクエアアルゴリズムをワイルシーケンスで修正すると、周期とランダム性が向上します。^{[4] [5]}

n桁の疑似乱数列を生成するには、 n桁の開始値を作成してそれを二乗し、2 n桁の数値を生成します。結果が 2 n桁未満の場合、補正のために先頭にゼロが追加されます。結果の中央のn桁がシーケンスの次の数値となり、結果として返されます。このプロセスを繰り返して、さらに多くの数値を生成します。

この方法が機能するには、nの値が偶数である必要があります。nの値が奇数の場合、選択できる一意に定義された「中間のn桁」が必ずしも存在するとは限りません。次の点を考慮してください。3 桁の数字を 2 乗すると、6 桁の数字になります (例: 540 ² = 291600)。中間の 3 桁がある場合、6 − 3 = 3 桁が中央の左側と右側に分配されます。これらの数字を中央の数字の両側に均等に分配することは不可能であるため、「中間の数字」は存在しません。偶数値の n 桁の数字を作成するために、シード値の左側にゼロを埋め込むことは許容されます(例: 540 → 0540)。

n桁の数字を生成するジェネレータの場合、周期は 8 ⁿより長くすることはできません。中間のn桁がすべてゼロの場合、ジェネレータは永遠にゼロを出力します。シーケンス内の数字の最初の半分がゼロの場合、後続の数字はゼロに向かって減少します。このようなゼロの連続は簡単に検出できますが、この方法が実用的であるには頻度が高すぎます。中間の 2 乗法は、ゼロ以外の数字で止まることもあります。n = 4の場合 、これは 0100、2500、3792、および 7600 の値で発生します。他のシード値は非常に短い繰り返しサイクルを形成します (例: 0540 → 2916 → 5030 → 3009)。これらの現象はn  = 2 の場合にさらに顕著になり、100 個の可能なシードのいずれも、0、10、50、60、または 24 ↔ 57 ループに戻らずに 14 回を超える反復を生成しません。

ここでは、アルゴリズムはPython 3.12でレンダリングされています。

seed_number  =  int ( input ( "4桁の数字を入力してください: \n [####] " )) 
number  =  seed_number 
already_seen  =  set () 
counter  =  0

 number が already_seenに含まれていない 場合: counter += 1 already_seen . add ( number ) number = int ( str ( number * number ) . zfill ( 8 )[ 2 : 6 ]) # zfill はゼロを埋め込みますprint ( f "# { counter } : { number } " ) 
      
    
          
    

print ( f " { seed_number }から開始し、" f " { counter }ステップ後に " f " { number }で繰り返しました。" )
      
      

• 線形合同ジェネレータ
• ブルーム・ブルーム・シュブ
• 中間平方ハッシュ関数