4

現在、Advanced Bash-Scripting Guide を読んでいて、次のことがわかりました。

   # Generate binary choice, that is, "true" or "false" value.
   BINARY=2
   T=1
   number=$RANDOM

   let "number %= $BINARY"
   #  Note that    let "number >>= 14"    gives a better random distribution
   #+ (right shifts out everything except last binary digit).
   if [ "$number" -eq $T ]
   then
       echo "TRUE"
   else
       echo "FALSE"
   fi  

   echo

ビット 1 ではなくビット 15 を使用することが推奨されるのはなぜですか? 二項決定による数回の実行では、両者の間に有意差は見られませんでした。

// UPDATE 分布の計算方法を尋ねられたので、ここで説明します。いくつかの $RANDOM 数値を生成し、各数値のビット 15 とビット 1 を取得して、2 つのバイナリ シーケンスを作成しました。その後、これらのシーケンスをループし、1 と 0 のチェーン (実行) をチェックし、最大長のシーケンスが生成する実行数を計算し (参照用)、すべてをわかりにくい表に出力しました。これがすべての栄光のコードです（汚いコードで申し訳ありません...）：

#! /bin/bash
COUNT=10000
RUN=1

# generate 2 sequences based on the same $RANDOM numbers
# seq1 = modulo 2, seq2 = bitshift 14
while [ $RUN -le $COUNT ]
do
    number=$RANDOM 
    let 'var1=number%2'
    var2=$number 
    let 'var2 >>= 14'
    seq1="${seq1}${var1}"
    seq2="${seq2}${var2}"
    (( RUN+=1 ))
done

# loop through sequences and check for chains of 1 and 0 (runs)
length=${#seq1}
prevSym=${seq1:0:1}
currRun="${prevSym}"
for (( i=1; i<length; i++ )); do
    currSym=${seq1:$i:1}
    if (( currSym==prevSym )); then
        currRun="${currRun}${currSym}"
        (( i!=length-1 )) && continue
        (( runStat1[${#currRun}]++ ))               #case: ends with run length > 1
        break
    fi
    (( runStat1[${#currRun}]++ ))
    (( prevSym=currSym ))
    (( i==length-1 )) && (( runStat1[1]++ ))             #case: ends with run length = 1
    currRun="${currSym}"
done

length=${#seq2}
prevSym=${seq2:0:1}
currRun="${prevSym}"
for (( i=1; i<length; i++ )); do
    currSym=${seq2:$i:1}
    if (( currSym==prevSym )); then
        currRun="${currRun}${currSym}"
        (( i!=length-1 )) && continue
        (( runStat2[${#currRun}]++ ))               #case: ends with run length > 1
        break
    fi
    (( runStat2[${#currRun}]++ ))
    (( prevSym=currSym ))
    (( i==length-1 )) && (( runStat2[1]++ ))             #case: ends with run length = 1
    currRun="${currSym}"
done

# print results and expected frequency
# number of expected runs with runlength k:
# 1/2**k if k<n, 1/2**(k-1) if k=n  
# $RANDOM generates random numbers in the range 0 to 32768 thus n=15
n=15
echo -e "Length L of run | # of runs with %2 | # of runs with >>14 | # of runs with MLS (calculated)\n "
echo -e "L\t|%2\t|>>14\t|MLS"
echo -e "-----------------------------------\n"
sorted="${!runStat1[*]} ${!runStat2[*]}" 
sorted=$(echo $sorted | tr ' ' '\n' | sort -n | uniq)
for a in $sorted; do
    k=${a}
    (( ${a}==${n} )) && (( k=a-1 ))
    prob=$(awk -v k=${a} -v c=${COUNT} 'BEGIN { print (((1/2)**k)*c)/k}')
    echo -e "${a} \t| ${runStat1[$a]} \t| ${runStat2[$a]} \t| ${prob} "
done

それを実行すると、これらの行に沿って何かが出力されます。

Length L of run | # of runs with %2 | # of runs with >>14 | # of runs with MLS (calculated)
L   |%2 |>>14   |MLS
-----------------------------------

1   | 2495  | 2450  | 5000 
2   | 1219  | 1212  | 1250 
3   | 638   | 621   | 416.667 
4   | 300   | 329   | 156.25 
5   | 162   | 166   | 62.5 
6   | 75    | 81    | 26.0417 
7   | 46    | 34    | 11.1607 
8   | 23    | 26    | 4.88281 
9   | 13    | 7     | 2.17014 
10  | 2     | 6     | 0.976562 
11  | 1     | 1     | 0.443892 
13  | 3     |   | 0.0939002 
15  |   | 2     | 0.0203451 
21  |   | 1     | 0.000227065

当然のことながら、すべての bash リファレンスでも言及されているように、$RANDOM はランダム性のひどいソースです...しかし、「number >>= 14」には「number %=」よりも優れたランダム分布はありません。バイナリ選択の場合は 2"。

... または、このばかげた計算の巨大な混乱のどこかで大きな間違いを犯しました。教えてください。

4

1 に答える 1