Расчет π с использованием ограничений моделирования Монте-Карло

Я задал вопрос, очень похожий на этот, поэтому я упомяну предыдущие решения в конце, у меня есть Веб-сайт, который вычисляет π с процессором клиента при сохранении его на сервере, пока что у меня есть:

'701.766.448.388' указывает внутри круга, и всего '893.547.800.000', эти числа вычисляются с использованием этого кода. (рабочий пример: https://jsfiddle.net/d47zwvh5/2/)

let inside = 0;
let size = 500;

for (let i = 0; i < iterations; i++) {
  var Xpos = Math.random() * size;
  var Ypos = Math.random() * size;

  var dist = Math.hypot(Xpos - size / 2, Ypos - size / 2);

  if (dist < size / 2) {
    inside++;
  }
}

Эта проблема

(4 * 701.766.448.388) / 893.547.800.000 = 3,141483638

Это результат, который мы получаем, который верен до четвертой цифры, 4 должно быть 5.

Предыдущие проблемы:

  1. Я испортил расчет расстояния.
  2. Я разместил круг от 0 ... 499, который должен быть 0 ... 500
  3. Я не использовал float, что уменьшило "разрешение"

Заявитель

Возможно, я достиг предела, но эта демонстрация использовала 1 миллион баллов и получила 3,16. учитывая, что у меня около 900 миллиардов, думаю, можно было бы точнее.

Я понимаю, что если я хочу вычислить π, это неправильный способ, но я просто хочу убедиться, что все правильно, поэтому я надеялся, что кто-то может заметить что-то не так, или мне просто нужно больше точек '.

Обновлено: Есть довольно много упоминаний о том, насколько нереалистичны числа, где эти упоминания являются правильными, и теперь я обновил их, чтобы они были правильными.

1) Эти числа невероятно большие (особенно для Javascript) ... 2) Они также подозрительно округлены до ближайшего миллиона ... 3) Math.random() может быть не лучшим генератором случайных чисел.

meowgoesthedog 12.09.2018 15:18

@meowgoesthedog Вы были правы, они отображаются неправильно (по этой же причине мы их округлили). Я обновил его точными числами из базы данных. Я постараюсь использовать более безопасный генератор случайных чисел, хотя это повлияет на скорость :(

Schotsl 12.09.2018 16:02

Ошибка составляет -0,00011, но каково стандартное отклонение оценщика?

Yves Daoust 12.09.2018 17:11

Что такое size? В любом случае ошибка оценки примерно пропорциональна величине, обратной квадратному корню из размера выборки. Когда вы переходите от 1 миллиона до 1 триллиона, это означает увеличение размера выборки в миллион раз, но только в тысячу раз увеличение квадратного корня из размера выборки. Который - должен дать вам еще 2 или 3 десятичных знака точности. Это не означает, что в коде нет ошибки, но то, что вы видите, может быть не так удивительно, как вы думаете.

John Coleman 13.09.2018 03:29

@JohnColeman size - это переменная, которая определяет размер круга и квадрата, а также предел случайных чисел. Тем не менее, спасибо за объяснение, возможно, я достиг практического предела вычислительной мощности, имеющейся в моем распоряжении.

Schotsl 14.09.2018 10:19

@YvesDaoust Я лично не знаю, как я могу вычислить стандартное отклонение, но ответ Северина Паппадё, кажется, дает некоторое представление об этом.

Schotsl 14.09.2018 10:26
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...
Безумие обратных вызовов в javascript [JS]
Безумие обратных вызовов в javascript [JS]
Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...
Система управления парковками с использованием HTML, CSS и JavaScript
Система управления парковками с использованием HTML, CSS и JavaScript
Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...
JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...
2
6
755
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

любая операция FPU снизит вашу точность. Почему бы не сделать что-то вроде этого:

let inside = 0;
for (let i = 0; i < iterations; i++)
  {
  var X = Math.random();
  var Y = Math.random();
  if ( X*X + Y*Y <= 1.0 ) inside+=4;
  }

Если мы исследуем первый квадрант единичного круга, нам не нужно изменять динамический диапазон с помощью size, а также мы можем протестировать расстояния в форме с питанием от 2, которая избавится от sqrt. Эти изменения должны повысить точность, а также скорость.

Не кодировщик JAVASCRIPT, поэтому я не знаю, какие типы данных вы используете, но вы должны быть уверены, что не нарушаете его точность. В таком случае вам нужно добавить больше переменных счетчика, чтобы уменьшить нагрузку на него. Подробнее см .: [edit1] точность интеграции.

Поскольку ваши числа довольно большие, держу пари, вы уже пересекли границу (дробной части быть не должно, а конечные нули также подозрительны). Например, 32-битный float может хранить только целые числа до

2^23 = 8388608

и ваш 698,565,481,000,000 намного выше этого, поэтому даже операция ++ с такой переменной приведет к потере точности, а когда показатель степени слишком велик, он даже перестанет добавлять ...

Для целых чисел это не проблема, но как только вы пересекаете границу, в зависимости от внутреннего формата, значение оборачивается вокруг нуля или отрицает ... Но я сомневался, что это так, поскольку тогда результат будет далеко от PI.

При изменении Javascript с помощью вашего нового фрагмента я понимаю, почему вычисление расстояния - это улучшение скорости, но единственное преимущество добавления 4 к 1 - это когда вы правильно рассчитываете π? Поскольку в этот момент вы можете просто разделить внутренние и внешние числа. Ваш код действительно сильно увеличивает скорость, просто взглянув на него, кажется, что он увеличился в три раза! и ранее я давал неправильные числа (см. редактирование), но текущие числа должны нормально работать в Javascript.

Schotsl 14.09.2018 10:40

@Schotsl Да, вы можете разделить на 4 в конечном делении вместо +=4, что также может сэкономить вам 2 бита в счетчике, если вы находитесь рядом с границей переменной разрядности. Поскольку единичное деление не имеет значения с точки зрения производительности. Мне просто лень было написать еще одну строчку кода ... Но главное повышение точности заключается в том, чтобы избежать ненужных вычислений с плавающей запятой.

Spektre 14.09.2018 11:05
Ответ принят как подходящий

Вы можете легко оценить, какую ошибку (планку погрешностей) вы должны получить, в этом вся прелесть Монте-Карло. Для этого вам необходимо вычислить второй импульс и оценить дисперсию и стандартное отклонение. Хорошо, что собранное значение будет таким же, как то, что вы собираете для среднего, потому что вы просто добавили 1 после 1 после 1.

Затем вы можете получить оценку сигмы моделирования и планки ошибок для желаемого значения. Извините, я недостаточно знаю Javascript, поэтому код здесь на C#:

using System;

namespace Pi
{
    class Program
    {
        static void Main(string[] args)
        {
            ulong N = 1_000_000_000UL; // number of samples
            var rng = new Random(312345); // RNG

            ulong v  = 0UL; // collecting mean values here
            ulong v2 = 0UL; // collecting squares, should be the same as mean
            for (ulong k = 0; k != N; ++k) {
                double x = rng.NextDouble();
                double y = rng.NextDouble();

                var r = (x * x + y * y < 1.0) ? 1UL : 0UL;

                v  += r;
                v2 += r * r;
            }

            var mean = (double)v / (double)N;
            var varc = ((double)v2 / (double)N - mean * mean ) * ((double)N/(N-1UL)); // variance
            var stdd = Math.Sqrt(varc); // std.dev, should be sqrt(Pi/4 (1-Pi/4))
            var errr = stdd / Math.Sqrt(N);

            Console.WriteLine($"Mean = {mean}, StdDev = {stdd}, Err = {errr}");

            mean *= 4.0;
            errr *= 4.0;

            Console.WriteLine($"PI (1 sigma) = {mean - 1.0 * errr}...{mean + 1.0 * errr}");
            Console.WriteLine($"PI (2 sigma) = {mean - 2.0 * errr}...{mean + 2.0 * errr}");
            Console.WriteLine($"PI (3 sigma) = {mean - 3.0 * errr}...{mean + 3.0 * errr}");
        }
    }
}

После 10 образцов 9 у меня получилось

Mean = 0.785405665, StdDev = 0.410540627166729, Err = 1.29824345388086E-05
PI (1 sigma) = 3.14157073026184...3.14167458973816
PI (2 sigma) = 3.14151880052369...3.14172651947631
PI (3 sigma) = 3.14146687078553...3.14177844921447

что выглядит примерно правильно. Легко видеть, что в идеальном случае дисперсия будет равна (Pi / 4) * (1-Pi / 4). На самом деле нет необходимости вычислять v2, просто установите его на v после моделирования.

Я, честно говоря, не знаю, почему вы получаете не то, что ожидаете. Ответом может быть потеря точности при суммировании, или, как я подозреваю, ваше моделирование не производит независимых выборок из-за заполнения и перекрытия последовательностей (так что фактическое N намного меньше 900 триллионов).

Но с помощью этого метода вы контролируете ошибку и проверяете, как идут вычисления.

ОБНОВИТЬ

Я добавил ваши цифры, чтобы показать, что вы явно недооцениваете ценность. Код

    N  = 893_547_800_000UL;
    v  = 701_766_448_388UL;
    v2 = v;

    var mean = (double)v / (double)N;
    var varc = ((double)v2 / (double)N - mean * mean ) * ((double)N/(N-1UL)); 
    var stdd = Math.Sqrt(varc); // should be sqrt(Pi/4 (1-Pi/4))
    var errr = stdd / Math.Sqrt(N);

    Console.WriteLine($"Mean = {mean}, StdDev = {stdd}, Err = {errr}");

    mean *= 4.0;
    errr *= 4.0;

    Console.WriteLine($"PI (1 sigma) = {mean - 1.0 * errr}...{mean + 1.0 * errr}");
    Console.WriteLine($"PI (2 sigma) = {mean - 2.0 * errr}...{mean + 2.0 * errr}");
    Console.WriteLine($"PI (3 sigma) = {mean - 3.0 * errr}...{mean + 3.0 * errr}");

И вывод

Mean = 0.785370909522692, StdDev = 0.410564786603016, Err = 4.34332975349809E-07
PI (1 sigma) = 3.14148190075886...3.14148537542267
PI (2 sigma) = 3.14148016342696...3.14148711275457
PI (3 sigma) = 3.14147842609506...3.14148885008647

Итак, очевидно, что у вас где-то есть проблема (код? Потеря точности в представлении? Потеря точности при суммировании? Повторная / не независимая выборка?)

Я не очень хорошо знаю C#, так что это грубо для нас обоих! В любом случае, данное число 900 триллионов было неправильным (см. Править), на самом деле это 900 миллиардов, что может объяснить разницу в ошибке?

Schotsl 14.09.2018 10:55

@Schotsl `так грубо с нами обоими!` Ага! По сравнению с 900 миллиардами, я вставил ваши числа в код оценки ошибок, пожалуйста, проверьте обновления. Нет, у вас где-то есть настоящая проблема.

Severin Pappadeux 14.09.2018 17:42

Просматривая его, я действительно не смог найти никаких проблем, я попробую использовать более безопасный генератор случайных чисел и посмотрю, к чему это меня приведет.

Schotsl 16.09.2018 17:38

@Schotsl, пожалуйста, держите нас в курсе - мне любопытно, в чем может быть проблема, потому что это не очевидно неправильно, но только немного.

Severin Pappadeux 17.09.2018 04:01

Прошло некоторое время, но я, наконец, обновил код, чтобы использовать случайное шифрование, так что теперь мы ждем!

Schotsl 08.10.2018 16:07

@Schotsl Отлично, ждем результатов

Severin Pappadeux 09.10.2018 16:24

Другие вопросы по теме