Comments 22
Сначала автор
Я наивно рассудил, что если просто взять нулевой бит этого числа, то должно получиться что-то вполне случайное.
генерирует 32 бита рандома и выкидывает 31 из них, потом начинает кешировать(?) биты чтобы было не так медленно потом при переходе к simd начинает использовать ГПСЧ нормально, а дальше даже берет нормальный для данной ситуации LCG (кстати константа совпадает с используемой в PCG32, а "шифрующая" функция оттуда в данном случае и не нужна).
Так что начинал читать с рукой прижатой к лицу но дальше все оказалось не так плохо.
Когда я научусь писать compute shaders, я стану жечь GPU вместо CPU, и тоже надеюсь на прорывные результаты
Да CUDA просто возьмите. :)
дальше только монте карло. взять багосорт и стохастически вероятностно предсказать сортировку :) интересно такое бывает? для меня пока это фантастика
Интересно а какая у вас вероятность того что Heads < Tails ? Почему у вас постоянно Tails доминируют?
Это ценное замечание, спасибо - я не замечал, пока вы не обратили внимание. Это стоит проверить. Особенно интересно, что это проявляется и на стандартном библиотечном генераторе. По крайней мере те примеры, что приведены в статье
Возможно, потому, что где-то отбрасываются младшие разряды чисел?... Я пока не знаю, не копал так глубоко.
Вероятность 50/50 предсказана для неких абстрактных «идеально‑случайных» значений. А подкидывание монетки и то, что описано в статье — это псевдослучайные числа, лишь некоторая приближённая модель случайных чисел. Вы как раз об этом и пишете.
На то же «подкидывание монетки» влияет психоэмоциональная сфера, время и длительность серии подкидываний, когнитивные искажения человека, форма ногтей, состояние суставов, процент ошибок при фиксации значений, концентрация молочной кислоты в мышце и прочие взаимосвязанные факторы. Про фишки из C и манипуляциями с SIMD я вообще молчу.
Поэтому и отличие наблюдаемого результата от ожидаемых 50/50 складывается далеко не только от »недостаточно большого количества итераций». Это как отличие идеальной абстрактной окружности из геометрии и реального колеса автомобиля. Модель работает лишь в каком‑то приближении.
Кстати, вопрос к математикам: а какова вероятность получить такую вероятность? :) Я в короткий промежуток времени получил 128 орлов против 128 решек целых два раза!
Примерно 0.05
По теории, отклонение где-то 
. То есть для точности, например, 
десятичных знака необходимо подбросить 
раз. Но тут могут быть коэффициенты, связанные с вероятностью события (в данном случае 
). Можно почитать про биномиальное распределение и его дисперсию, которая и позволяет оценить отклонение.
Мне тоже было интересно, и местами весело, следить за ходом этой работы. Она напомнила мне весь цикл разработки какой-либо программы. Что-то из этого было даже поучительным.
Вот только вопрос оптимизации не затронул такое оборудование: память RAM, HDD/SSD; отрисовка графики; сеть... В целом неплохо и полезно.
Подскажите пожалуйста, на чем Вы писали калькулятор ieee754?
Это JS + Wasm. Wasm-бекенд написан на Rust. Вышла очень интересная связка. Вот репо
Да, хотел бы еще мотивировать выбор стека, ибо это примечательный момент. Я был не прочь написать все на голом vanila-JS, но числа у JS совершенно не прозрачны и не хороши для манипуляций с битами. К тому же вы не получите разное представление бит для целочисленного и для числа с плавающей точкой, потому что у JS с этим разделением тяжко.
Я не стал эмулировать битовую математику в самом JS (хотя из этого могла бы и статья получиться..), а пошел в строго-типизированный язык, у которого обширная линейка целочисленных и float типов, и который умеет в WASM-компиляцию.
Я частенько пользуюсь этим https://www.h-schmidt.net/FloatConverter/IEEE754.html, но теперь, вероятно, перейду на Ваш), если вдруг опять буду работать с float.
Спасибо за интересную статью. Мои 5 копеек для дальнейшего улучшения:
Для итерации по всему диапазону числа используют обычно трюк с постусловием, do {...} while(). А для отображения таких ускорений удобно использовать логарифмическую шкалу.
Да. Но можно ещё стартануть с минус единицы и идти - хоть инкрементом, хоть декрементом - до тех пор пока счётчик опять не станет равным минус одному.
я ксати пробовал логарифмическую шкалу, и она действительно отлично отобразила весь диапазон Y. но я тут уперся в чисто технические заморочки - инструмент, которым я рисовал график не поддерживает лог-шкалу, поэтому я ее "сэмулировал", прологарифмировав все значения. но без верных цифр по оси Y график стал совершенно дезориентирующим, и я забил, и выкручивался с тем, что есть. а новый инструмент было лень искать
свое ноу-хау — график с вложенными диапазонами
А чем автору не угодила логарифмическая шкала?
да тут уже чисто частные замарочки: https://habr.com/ru/articles/950046/comments/#comment_28892724
так-то лог-шкала хорошее решение. у него правда один недостаток - не так шокирует резкостю изменений)
precision: 1
Tossed: 33 552 384
Heads: 15 724 557, 0.4686569216661325765
Tails: 17 827 827, 0.5313430783338674235
Time: 18ms 222us 700ns
Слишком большое отклонение при таком колве экспериментов. И стабильно большое, если посмотреть на другие результаты.
Орел или решка. C++ Edition