Databases
StackOverflow2013
Postsdbo
PODifferent methods to generate binary choice
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PODifferent methods to generate binary choice
    primarykey
    data
    text
    <p>I'm currently reading through the Advanced Bash-Scripting Guide and found the following:</p> <pre><code> # Generate binary choice, that is, "true" or "false" value. BINARY=2 T=1 number=$RANDOM let "number %= $BINARY" # Note that let "number &gt;&gt;= 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 </code></pre> <p>Why is it recommended to take bit 15 instead of bit 1? A couple of runs with binary decisions revealed no significant difference between the two.</p> <p><strong>// UPDATE</strong> Since i was asked how i calculated the distribution, here we go. I generated a couple of $RANDOM numbers, took bit 15 and bit 1 of each number and created two binary sequences. Afterwards i looped through those sequences, checked for chains of 1 and 0 (runs), calculated how many of those runs a maximum length sequence would generate (for reference) and printed everything into a confusing table. Here's the code in all it's glory (sorry for the dirty code...): </p> <pre><code>#! /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 &gt;&gt;= 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&lt;length; i++ )); do currSym=${seq1:$i:1} if (( currSym==prevSym )); then currRun="${currRun}${currSym}" (( i!=length-1 )) &amp;&amp; continue (( runStat1[${#currRun}]++ )) #case: ends with run length &gt; 1 break fi (( runStat1[${#currRun}]++ )) (( prevSym=currSym )) (( i==length-1 )) &amp;&amp; (( runStat1[1]++ )) #case: ends with run length = 1 currRun="${currSym}" done length=${#seq2} prevSym=${seq2:0:1} currRun="${prevSym}" for (( i=1; i&lt;length; i++ )); do currSym=${seq2:$i:1} if (( currSym==prevSym )); then currRun="${currRun}${currSym}" (( i!=length-1 )) &amp;&amp; continue (( runStat2[${#currRun}]++ )) #case: ends with run length &gt; 1 break fi (( runStat2[${#currRun}]++ )) (( prevSym=currSym )) (( i==length-1 )) &amp;&amp; (( 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&lt;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 &gt;&gt;14 | # of runs with MLS (calculated)\n " echo -e "L\t|%2\t|&gt;&gt;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} )) &amp;&amp; (( 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 </code></pre> <p>Running it will print out something along those lines:</p> <pre><code>Length L of run | # of runs with %2 | # of runs with &gt;&gt;14 | # of runs with MLS (calculated) L |%2 |&gt;&gt;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 </code></pre> <p>Which leads me to the conclusion that, unsurprisingly and also mentioned in all bash references, $RANDOM is a terrible source for randomness... But also "number >>= 14" doesn't have a better random distribution than "number %=2" for a binary choice.</p> <p>... or i made huge mistake somewhere in this huge mess of silly calculations. You tell me.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USaraex
    1. USaraex
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. PODifferent methods to generate binary choice
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PODifferent methods to generate binary choice
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PODifferent methods to generate binary choice
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHow is this question off topic? An explanation was requested for # Note that let "number >>= 14" gives a better random distribution
      singulars
      1. PODifferent methods to generate binary choice
      1. USseeker
    2. COHow did you calculate/plot the random distribution?
      singulars
      1. PODifferent methods to generate binary choice
      1. USAdrian Frühwirth
    3. COUpdated the original post with my calculation
      singulars
      1. PODifferent methods to generate binary choice
      1. USaraex
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload