Экстремальный пример: Монте-Карло (граница) метод для пи

Метод Монте-Карло для вычисления Пи является программой типичного примера, используемой в программах информатики. Большинство преподавателей CS не вынуждает своих студентов записать, что это с помощью сценария оболочки, однако, и делая так ставит много проблем.

Метод Монте-Карло является довольно прямым. Вы берете круг модуля и помещаете его в 2x2 квадрат и случайным образом бросаете стрелки в него. Для любой стрелки, совершающей нападки в кругу, Вы добавляете ту к «внутреннему» счетчику и «общему» счетчику. Для любой стрелки, совершающей нападки вне круга, Вы просто добавляете ту к «общему» счетчику. При делении числа хитов в кругу числом общих бросков Вы получаете число, которое (данный бесконечное число достаточно случайных бросков) будет сходиться к π/4 (одна четверть пи).

Общее упрощение Метода Монте-Карло (который используется в этом примере) должно сократить квадрат до единого блока в размере, и сокращать круг модуля до только круга четверти. Таким образом круг встречает два угла квадрата и имеет его центр в третьем углу..

Компьютерная версия этой проблемы, вместо того, чтобы бросить стрелки, использует генератор случайных чисел для генерации случайной точки в определенном наборе границ. В этом случае код использует целые числа от 0-65 535 для обоих координаты x и y точки. Это тогда вычисляет расстояние от точки (0,0) к (x, y) использование теоремы Пифагора (гипотенуза прямоугольного треугольника с краями x и y длин). Если это расстояние больше, чем круг модуля (65,535, в этом случае), точка выходит за пределы «круга». Иначе, это падает в «кругу».

Получение случайных чисел

Для получения случайных чисел этот пример кода использует dd команда для чтения одного байта за один раз из /dev/random. Затем это должно вычислить числовой эквивалент этих чисел. Тот процесс описан в Нахождении Порядкового Разряда Символа.

Следующий пример показывает, как считать использование байта dd:

# Read four random bytes.
RAWVAL1="$(dd if=/dev/random bs=1 count=1 2> /dev/null)"
RAWVAL2="$(dd if=/dev/random bs=1 count=1 2> /dev/null)"
RAWVAL3="$(dd if=/dev/random bs=1 count=1 2> /dev/null)"
RAWVAL4="$(dd if=/dev/random bs=1 count=1 2> /dev/null)"
 
# Calculate the ordinality of the bytes.
XVAL0=$(ord "$RAWVAL1") # more on this subroutine later
XVAL1=$(ord "$RAWVAL2") # more on this subroutine later
YVAL0=$(ord "$RAWVAL3") # more on this subroutine later
YVAL1=$(ord "$RAWVAL4") # more on this subroutine later
 
# We basically want to get an unsigned 16-bit number out of
# two raw bytes.  Earlier, we got the ord() of each byte.
# Now, we figure out what that unsigned value would be by
# multiplying the high order byte by 256 and adding the
# low order byte.  We don't really care which byte is which,
# since they're just random numbers.
XVAL=$(( ($XVAL0 * 256) + $XVAL1 ))   # use expr for older shells.
YVAL=$(( ($YVAL0 * 256) + $YVAL1 ))   # use expr for older shells.

Нахождение порядкового разряда символа

Существует много способов вычислить порядковый разряд символа. Этот пример представляет трех из тех: встроенный Perl, встроенный AWK и более пуристское («медленное» чтение) версия с помощью только sed и tr.

Нахождение порядкового разряда Используя Perl

Самый простой способ найти порядковый разряд символа в сценарии оболочки при помощи встроенного кода Perl. В следующем примере необработанный символ отражен к perl стандартный ввод интерпретатора. (См. perl страница руководства для получения дополнительной информации о Perl.)

Короткий сценарий Perl устанавливает разделитель записей в неопределенный, затем считывает данные до EOF, наконец распечатывая порядковый номер символа, что это получает использование ord подпрограмма.

YVAL1=$(echo $RAWVAL4 | perl -e '$/ = undef; my $val = <STDIN>; print ord($val);')

Нахождение порядкового разряда Используя AWK

Второй метод для получения порядкового разряда символа немного более сложен, но все еще относительно быстро. Производительность только немного медленнее, чем пример Perl.

            YVAL0=$(echo $RAWVAL3 | awk '{
                RS="\n"; ch=$0;
                # print "CH IS ";
                # print ch;
                if (!length(ch)) { # must be the record separator.
                        ch="\n"
                };
                s="";
                for (i=1; i<256; i++) {
                        l=sprintf("%c", i);
                        ns = (s l); s = ns;
                };
                pos = index(s, ch); printf("%d", pos)
            }')

В этом примере необработанный символ отражен к сценарию AWK. (См. awk страница руководства и Как Неловкий для получения дополнительной информации о AWK.), Что сценарий выполняет итерации через номера 1-255, связывая символ (l) чье значение ASCII является тем числом (i) на строку (ns). Это тогда просит расположение того символа в строке. Если никакое значение не будет найдено, то индекс возвратит нуль (0), который удобен, как NULL (символ 0), исключен из строки.

Удивительная вещь состоит в том, что этот код, в то время как на вид намного более сложный, чем эквивалентный Perl, выполняет почти также (меньше чем половина секунды медленнее на 100 итераций).

Нахождение Порядкового Разряда Используя TR И sed

Этот пример был записан меньше из желания фактически использовать такой метод и больше из желания доказать, что такой код возможен. Это - безусловно, самый окольный способ вычислить порядковый разряд символа, с которым Вы, вероятно, будете когда-либо встречаться. Это ведет себя во многом как awk программа, описанная в Нахождении Порядкового Разряда Используя AWK, но не используя никакие другие языки программирования кроме сценариев Оболочки Bourne.

Первая часть этого примера является маленьким фрагментом кода для преобразования целого числа в его восьмеричный эквивалент. Это будет важно позже.

Перечисление e-1  Целое число к Восьмеричной подпрограмме Преобразования

# Convert an int to an octal value.
inttooct()
{
        echo $(echo "obase=8; $1" | bc)
}

Этот код является относительно прямым. Это говорит основной калькулятор, bc, распечатать конкретное количество, преобразовывая вывод для базирования 8 (восьмеричный).

Следующая часть этого примера является кодом для инициализации строки, содержащей список всех возможных символов ASCII кроме NULL (символ 0) в порядке. Эту подпрограмму вызывают только один раз в инициализации программы; версия оболочки этого кода является очень медленной, как это, и вызывающий эту подпрограмму каждый раз, когда Вы пытаетесь найти, что порядковый разряд символа сделал бы этот код абсолютно неприменимым.

# Initializer for the scary shell ord subroutine.
ord_init()
{
    I=1
    ORDSTRING=""
    while [ $I -lt 256 ] ; do
        # local HEX=$(inttohex $I);
        local OCT=$(inttooct $I);
        # The following should work with GNU sed, but
        # OS X's sed doesn't support \x.
        # local CH=$(echo ' ' | sed "s/ /\\x$HEX/")
        # How about this?
        # local CH=$(perl -e  "\$/=undef; \$x = ' '; \$x =~ s/ /\x$HEX/g; print \$x;")
        # Yes, that works, but it's cheating.  Here's a better one.
        local CH=$(echo ' ' | tr ' ' "\\$OCT");
        ORDSTRING=$ORDSTRING$CH
        I=$(($I + 1)) # or I=$(expr $I '+' 1)
        # echo "ORDSTRING: $ORDSTRING"
    done
}

Эта версия показывает три возможных способа генерировать необработанный символ от числового эквивалента. Первый путь работает в Perl и работах с GNU sed, но не работает с sed реализация в OS X. Второй путь использует perl интерпретатор. В то время как этот путь работает, намерение состояло в том, чтобы избегать использования других языков сценариев, если это возможно.

Третьим путем является интересный прием. Строка, содержащая одиночный пробел, передается tr. tr команда, в ее нормальной эксплуатации, заменяет всеми экземплярами определенного символа с другим. Это также распознает коды символов в форме наклонной черты влево, сопровождаемой тремя восьмеричными цифрами. Таким образом, в этом случае, его параметры говорят ему заменять каждый экземпляр пространства во вводе (который состоит из одиночного пробела) с эквивалентом символов восьмеричного числа $OCT. Это восьмеричное число, в свою очередь, был вычислен от индекса цикла (I) использование восьмеричной подпрограммы преобразования, показанной в Перечислении e-1.

Когда эта подпрограмма возвращается, глобальная переменная $ORDSTRING содержит каждое начало символа ASCII с символа 1 и окончание символом 255.

Заключительная часть этого кода является подпрограммой, чтобы определить местоположение символа в строке и возвратить ее индекс. Снова, это может быть сделано легко со встроенным кодом Perl, но цель этого кода состоит в том, чтобы сделать это, не используя никакой другой язык программирования.

ord()
{
    local CH="$1"
    local STRING=""
    local OCCOPY=$ORDSTRING
    local COUNT=0;
 
    # Some shells can't handle NULL characters,
    # so this code gets an empty argument.
    if [ "x$CH" = "x" ] ; then
        echo 0
        return
    fi
 
    # Delete the first character from a copy of ORDSTRING if that
    # character doesn't match the one we're looking for.  Loop
    # until we don't have any more leading characters to delete.
    # The count will be the ASCII character code for the letter.
    CONT=1;
    while [ $CONT = 1 ]; do
        # Copy the string so we know if we've stopped finding
        # nonmatching characters.
        OCTEMP="$OCCOPY"
 
        # echo "CH WAS $CH"
        # echo "ORDSTRING: $ORDSTRING"
 
        # Delete a character if possible.
        OCCOPY=$(echo "$OCCOPY" | sed "s/^[^$CH]//");
 
        # On error, we're done.
        if [ $? != 0 ] ; then CONT=0 ; fi
 
        # If the string didn't change, we're done.
        if [ "x$OCTEMP" = "x$OCCOPY" ] ; then CONT=0 ; fi
 
        # Increment the counter so we know where we are.
        COUNT=$((COUNT + 1)) # or COUNT=$(expr $COUNT '+' 1)
        # echo "COUNT: $COUNT"
    done
 
    COUNT=$(($COUNT + 1)) # or COUNT=$(expr $COUNT '+' 1)
    # If we ran out of characters, it's a null (character 0).
    if [ "x$OCTEMP" = "x" ] ; then COUNT=0; fi
 
    # echo "ORD IS $COUNT";
 
    # Return the ord of the character in question....
    echo $COUNT
    # exit 0
}

В основном этот код неоднократно удаляет первый символ из копии строки, сгенерированной ord_init подпрограмма, если тот символ не соответствует образец. Как только этому не удается удалить символ, число удаленных символов (перед нахождением соответствующего символа) равно меньше, чем значение ASCII вводимого символа. Если код исчерпывает символы, вводимый символ, должно быть, был одним символом, опущенным от строки поиска ASCII: NULL (символ 0).

Полный пример кода

#!/bin/sh
 
ITERATIONS=1000
SCALE=6
 
# Prevent sed from caring about high ASCII characters not
# being valid UTF-8 sequences
export LANG="C"
 
# Set FAST to "slow", "medium", or "fast".  This controls
# which ord() subroutine to use.
#
# slow-use a combination of Perl, AWK, and shell methods
# medium-use only Perl and AWK methods.
# fast-use only Perl
 
# FAST="slow"
# FAST="medium"
FAST="fast"
 
# 100 iterations - FAST
# real    0m9.850s
# user    0m2.162s
# sys     0m8.388s
 
# 100 iterations - MEDIUM
# real    0m10.362s
# user    0m2.375s
# sys     0m8.726s
 
# 100 iterations - SLOW
# real    2m25.556s
# user    0m32.545s
# sys     2m12.802s
 
# Calculate the distance from point 0,0 to point X,Y.
# In other words, calculate the hypotenuse of a right
# triangle whose legs are of length X and Y.
distance()
{
    local X=$1
    local Y=$2
 
    DISTANCE=$(echo "sqrt(($X ^ 2) + ($Y ^ 2))" | bc)
 
    echo $DISTANCE
}
 
# Convert an int to a hex value.  (Not used.)
inttohex()
{
    echo $(echo "obase=16; $1" | bc)
}
 
# Convert an int to an octal value.
inttooct()
{
    echo $(echo "obase=8; $1" | bc)
}
 
# Initializer for the scary shell ord subroutine.
ord_init()
{
    I=1
    ORDSTRING=""
    while [ $I -lt 256 ] ; do
    # local HEX=$(inttohex $I);
    local OCT=$(inttooct $I);
    # The following should work with GNU sed, but
    # OS X's sed doesn't support \x.
    # local CH=$(echo ' ' | sed "s/ /\\x$HEX/")
    # How about this?
    # local CH=$(perl -e  "\$/=undef; \$x = ' '; \$x =~ s/ /\x$HEX/g; print \$x;")
    # Yes, that works, but it's cheating.  Here's a better one.
    local CH=$(echo ' ' | tr ' ' "\\$OCT");
    ORDSTRING=$ORDSTRING$CH
    I=$(($I + 1)) # or I=$(expr $I '+' 1)
    # echo "ORDSTRING: $ORDSTRING"
    done
}
 
# This is a scary little lovely piece of shell script.
# It finds the ord of a character using only the shell,
# tr, and sed.  The variable ORDSTRING must be initialized
# prior to first use with a call to ord_init.  This string
# is not modified.
ord()
{
    local CH="$1"
    local STRING=""
    local OCCOPY=$ORDSTRING
    local COUNT=0;
 
 
    # Some shells can't handle NULL characters,
    # so this code gets an empty argument.
    if [ "x$CH" = "x" ] ; then
        echo 0
        return
    fi
 
    # Delete the first character from a copy of ORDSTRING if that
    # character doesn't match the one we're looking for.  Loop
    # until we don't have any more leading characters to delete.
    # The count will be the ASCII character code for the letter.
    CONT=1;
    while [ $CONT = 1 ]; do
    # Copy the string so we know if we've stopped finding
    # nonmatching characters.
    OCTEMP="$OCCOPY"
 
    # echo "CH WAS $CH"
    # echo "ORDSTRING: $ORDSTRING"
 
    # Delete a character if possible.
    OCCOPY=$(echo "$OCCOPY" | sed "s/^[^$CH]//");
 
    # On error, we're done.
    if [ $? != 0 ] ; then CONT=0 ; fi
 
    # If the string didn't change, we're done.
    if [ "x$OCTEMP" = "x$OCCOPY" ] ; then CONT=0 ; fi
 
    # Increment the counter so we know where we are.
    COUNT=$((COUNT + 1)) # or COUNT=$(expr $COUNT '+' 1)
    # echo "COUNT: $COUNT"
    done
 
    COUNT=$(($COUNT + 1)) # or COUNT=$(expr $COUNT '+' 1)
    # If we ran out of characters, it's a null (character 0).
    if [ "x$OCTEMP" = "x" ] ; then COUNT=0; fi
 
    # echo "ORD IS $COUNT";
 
    # Return the ord of the character in question....
    echo $COUNT
    # exit 0
}
 
# If we're using the shell ord subroutine, we need to
# initialize it on launch.  We also do a quick sanity
# check just to make sure it is working.
if [ "x$FAST" = "xslow" ] ; then
    echo "Initializing Bourne ord subroutine."
    ord_init
 
    # Test our ord subroutine
    echo "Testing ord subroutine"
    ORDOFA=$(ord "a")
    # That better be 97.
    if [ "$ORDOFA" != "97" ] ; then
        echo "Shell ord subroutine broken.  Try fast mode."
    fi
 
    echo "ord_init done"
fi
 
COUNT=0
IN=0
 
# For the Monte Carlo method, we check to see if a random point between
# 0,0 and 1,1 lies within a unit circle distance from 0,0.  This allows
# us to approximate pi.
while [ $COUNT -lt $ITERATIONS ] ; do
    # Read four random bytes.
    RAWVAL1="$(dd if=/dev/random bs=1 count=1 2> /dev/null)"
    RAWVAL2="$(dd if=/dev/random bs=1 count=1 2> /dev/null)"
    RAWVAL3="$(dd if=/dev/random bs=1 count=1 2> /dev/null)"
    RAWVAL4="$(dd if=/dev/random bs=1 count=1 2> /dev/null)"
 
    # ord "$RAWVAL4";
    # exit 0;
 
    # The easy method for doing an ord() of a character: use Perl.
    XVAL0=$(echo $RAWVAL1 | perl -e '$/ = undef; my $val = <STDIN>; print ord($val);')
    XVAL1=$(echo $RAWVAL2 | perl -e '$/ = undef; my $val = <STDIN>; print ord($val);')
 
    # The not-so-easy way using AWK (but still almost as fast as Perl)
    if [ "x$FAST" != "xfast" ] ; then
        # Run this for FAST = medium or slow.
        echo "AWK ord"
        # Fun little AWK program for calculating ord of a letter.
        YVAL0=$(echo $RAWVAL3 | awk '{
        RS="\n"; ch=$0;
        # print "CH IS ";
        # print ch;
        if (!length(ch)) { # must be the record separator.
            ch="\n"
        };
        s="";
        for (i=1; i<256; i++) {
            l=sprintf("%c", i);
            ns = (s l); s = ns;
        };
        pos = index(s, ch); printf("%d", pos)
        }')
        # Fun little shell script for calculating ord of a letter.
    else
        YVAL0=$(echo $RAWVAL3 | perl -e '$/ = undef; my $val = <STDIN>; print ord($val);')
    fi
 
    # The evil way---slightly faster than looking it up by hand....
    if [ "x$FAST" = "xslow" ] ; then
        # Run this ONLY for FAST = slow.  This is REALLY slow!
        YVAL1=$(ord "$RAWVAL4")
    else
        YVAL1=$(echo $RAWVAL4 | perl -e '$/ = undef; my $val = <STDIN>; print ord($val);')
    fi
 
    # echo "YV3: $VAL3"
    # YVAL1="0"
 
    # We basically want to get an unsigned 16-bit number out of
    # two raw bytes.  Earlier, we got the ord() of each byte.
    # Now, we figure out what that unsigned value would be by
    # multiplying the high order byte by 256 and adding the
    # low order byte.  We don't really care which byte is which,
    # since they're just random numbers.
    XVAL=$(( ($XVAL0 * 256) + $XVAL1 ))   # use expr for older shells.
    YVAL=$(( ($YVAL0 * 256) + $YVAL1 ))   # use expr for older shells.
 
    # This doesn't work well, since we can't seed AWK's PRNG
    # in any useful way.
    # YVAL=$(awk '{printf("%d", rand() * 65535)}')
 
    # Calculate the difference.
    DISTANCE=$(distance $XVAL $YVAL)
    echo "X: $XVAL, Y: $YVAL, DISTANCE: $DISTANCE"
 
    if [ $DISTANCE -le 65535 ] ; then # use expr for older shells
        echo "In circle.";
        IN=$(($IN + 1))
    else
        echo "Outside circle.";
    fi
 
    COUNT=$(($COUNT + 1))                # use expr for older shells.
done
 
# Calculate PI.
PI=$(echo "scale=$SCALE; ($IN / $ITERATIONS) * 4" | bc)
 
# Print the results.
echo "IN: $IN, ITERATIONS: $ITERATIONS"
echo "PI is about $PI"