А>Есть числа a и b из интервала (-1, 1). d1=a-b. В цикле к числам a и b прибавляется случайно выбранное число из интервала (-1, 1). После этого считается d2=a2-b2. Вопрос заключается в следующем: будет ли с увеличением количества циклов постоянно расти расхождение между d1 и d2, или расхождение в любом случае не превзойдет определенную величину?
да, расти пропорционально квадратному корню из количества шагов.
http://en.wikipedia.org/wiki/Random_walk
Здравствуйте, dilmah, Вы писали:
D>да, расти пропорционально квадратному корню из количества шагов.
D>http://en.wikipedia.org/wiki/Random_walk
Отличные картинки в статье!
Ещё пара моментов:
1) Если вдруг потребуется моделирование, то надо учитывать, что многие стандартные генераторы ПСЧ обладают очень сильной корреляцией.
Вот классическая анимация из статьи про
линейные когруэнтные генераторы:
2) Стоит обратить внимание на режим округления — в большинстве современных языков программирования по умолчанию исползуется "банкирское округление": Round(2.5) = 2 но Round(3.5) = 4, с целью как раз минимизировать погрешности:
http://en.wikipedia.org/wiki/Rounding
Кстати, в этой же статье ещё упоминается два интересных типа округления: "Stochastic rounding" и "Dithering".
Здравствуйте, andy1618, Вы писали:
A>Вот классическая анимация
Упс, ссылка неточная была.
(На всяк. случай вот
оригинал этой анимации)
Здравствуйте, dilmah, Вы писали:
D>да, расти пропорционально квадратному корню из количества шагов.
D>http://en.wikipedia.org/wiki/Random_walk
Ясно. Если у меня переменные a и b имеют тип float (язык C++), какое будет фактически расхождение после n шагов (какой коэффициент в зависимости)?
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, dilmah, Вы писали:
D>>да, расти пропорционально квадратному корню из количества шагов.
D>>http://en.wikipedia.org/wiki/Random_walk
А>Ясно. Если у меня переменные a и b имеют тип float (язык C++), какое будет фактически расхождение после n шагов (какой коэффициент в зависимости)?
Это расхождение никак не связано с округлением, прочитайте статью все-таки.
Переубедить Вас, к сожалению, мне не удастся, поэтому сразу перейду к оскорблениям.
Эээээ... Складывается такое ощущение, то ли я не точно выразился, то ли не правильно поняли... На каждом цикле к a и b прибавляется одно и тоже число. По этому в идеале разность меняться не должна (a+x)-(b+x)=a+x-b-x=a-b. Меня интересует расхождение связанное именно с округлением чисел.
Здравствуйте, Аноним, Вы писали:
А> ... На каждом цикле к a и b прибавляется одно и тоже число. По этому в идеале разность меняться не должна (a+x)-(b+x)=a+x-b-x=a-b. Меня интересует расхождение связанное именно с округлением чисел.
Ага, теперь понятно. Тут всё будет довольно интересно.
1. В теории, по заданным a и b (при условии a != b) можно сконструировать такую последовательность якобы "случайных" шагов x1, x2, ..., что при их добавлении к числам a и b разность между ними будет неограниченно увеличиваться. Пределом тут будет только то, что, поскольку величина шага у нас ограничена значением 1, то найдётся некоторое пороговое значение MAX (для типа float это порядка 10^7..10^8), когда прибавление к нему максимально разрешённого шага 1 его не изменит из-за ограничений разрядной сетки.
Т.е. получается, что числа a,b не смогут "выбраться" из диапазона [-MAX, MAX], что и будет ограничивать "максимальное возможное расхождение".
Это теоретический ответ на поставленный вопрос
2. На практике всё будет по-другому: во-первых, округления будут происходить не на всех итерациях. Например, если для всех пяти float-чисел: a, b, x, a+x, b+x их порядок величины (с т.з. двоичного представления) одинаковый, то сложение будет абсолютно точным и расхождение не изменится.
А, во-вторых, поскольку в данном случае тоже получаем упомянутое в посте выше "случайное блуждание" (хотя и замедленное), то рано или поздно у нас расхождение достигнет нуля и
там и останется, поскольку получим a == b и все их дальнейшие изменения будут синхронными.
Таким образом, на практике получается, что расхождение будет случайно блуждать, пока не достигнет 0.
Вот пример одной из реализаций такого "блуждания":
Как видно, расхождение свелось к 0 примерно после 25 млрд. итераций.