Re: Problems when RANDOM without $ is used as an array index

[Chet Ramey]

On 1/11/10 9:26 AM, Stephane CHAZELAS wrote:
> 2010-01-9, 06:23(-06), dennis@netstrata.com:
> [...]
>> This produces the correct distribution of dice values for two six-sided dice:
>>
>>  $ unset dice; for i in {1..10000}; do ((dice[$RANDOM%6+1 + 
>> $RANDOM%6+1]++)); done; echo "${dice[@]}"
>>  290 582 837 1130 1375 1635 1315 1126 845 574 291
>>
>> The total is correct:
>>
>>  $ unset t; for i in ${dice[@]}; do ((t+=i)); done; echo $t
>>  10000
>>  
>> This creates an even distribution which is incorrect:
>>  
>>  $ unset dice; for i in {1..10000}; do ((dice[RANDOM%6+1 + RANDOM%6+1]++)); 
>> done; echo "${dice[@]}"
>>  886 884 887 882 885 879 886 887 881 879 883
>>
>> And the total is incorrect (may be larger or smaller):
>>
>>  $ unset t; for i in ${dice[@]}; do ((t+=i)); done; echo $t
>>  10047
> [...]
> 
> I've been scratching my head for some time, but can't figure out
> what's going on. I get the exact same behavior with ksh93 and
> zsh. Again there, replacing RANDOM with $RANDOM fixes the
> problem. Strange that all 3 shells would have the exact same
> bug. Are we missing the obvious here?

It wasn't really obvious, but it was straightforward in retrospect.
The variant with RANDOM (instead of $RANDOM) generates four random
numbers each time through the loop.  With double the number generated,
the distribution is more even, and you get some duplicates.

The expression (( dice[RANDOM%6+1 + RANDOM%6+1]++ )) evaluates the array
subscript twice:  once to generate the initial value to be incremented
and once more to generate the index on which to perform the assignment.
Think of it as

x = $(( RANDOM%6+1 + RANDOM%6+1 ))
y = dice[x]
dice[RANDOM%6+1 + RANDOM%6+1] = y + 1
return y

instead of (what I think the OP assumed)

x=$(( RANDOM%6+1 + RANDOM%6+1 ))
y = dice[x]
dice[x] = y + 1
return y

The variant with $RANDOM has the variable expansion performed before the
arithmetic evaluation, so it generates only two random numbers as part of
the word expansion.

Chet
-- 
``The lyf so short, the craft so long to lerne.'' - Chaucer
                 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, ITS, CWRU    chet@case.edu    http://cnswww.cns.cwru.edu/~chet/