Рассчитайте PI, используя сумму обратных квадратов

Мне нужно рассчитать PI с заданной точностью, используя эту формулу:

введите описание изображения здесь

Итак, я остановился на этом решении.

private static double CalculatePIWithPrecision(int presicion)
{
    if (presicion == 0)
    {
        return PI_ZERO_PRECISION;
    }

    double sum = 0;

    double numberOfSumElements = Math.Pow(10, presicion + 2);

    for (double i = 1; i < numberOfSumElements; i++)
    {
        sum += 1 / (i * i);
    }

    double pi = Math.Sqrt(sum * 6);
    return pi;
}

Так что это работает правильно, но я столкнулся с проблемой эффективности. Очень медленно при значениях точности 8 и выше.

Есть ли лучший (и более быстрый!) Способ рассчитать PI по этой формуле?


c# math pi
person Pavlo Zin    schedule 28.09.2014    source источник
comment
Неужели он настолько медленный, что может стать проблематичным при однократном выполнении?   -  person Scott Hunter    schedule 28.09.2014
comment
Попробуйте использовать int в for предложении. Я подозреваю, что использование удвоения значительно замедляет работу.   -  person Sopuli    schedule 28.09.2014
comment
@ScottHunter Да, медленно. Посмотрите на переменную numberOfSumElements и на то, как она зависит от точности.   -  person Pavlo Zin    schedule 28.09.2014
comment
@GrantWinney Я должен :(   -  person Pavlo Zin    schedule 28.09.2014
comment
Предложение @ Sopuli о переменной цикла int хорошо, пока presicion не превышает 8 (иначе Pow(10, presicion + 2) переполнило бы int). Вам также нужно будет изменить 1 на 1.0 в строке sum +=, чтобы получить правильные результаты, и изменить numberOfSumElements на int (с соответствующим приведением к назначению), чтобы получить максимальную пользу.   -  person Joe White    schedule 28.09.2014
comment
концепция вычисления PI медленная, почему вы не рассчитываете один раз и не сохраняете его для следующего раза?   -  person Mehdi Khademloo    schedule 28.09.2014
comment
Это не будет быстрее, но вы получите лучшие (более точные) результаты, если измените направление цикла и сначала просуммируете меньшие члены. double может содержать только 15-16 цифр после (плавающей) десятичной запятой, поэтому, если вы возьмете что-то порядка 1 и добавите что-то порядка 1,23456789E-15, вы потеряете все, кроме 1,2 (или, может быть, просто 1) от малого числа, потому что 1 может содержать только 15-16 цифр после десятичной точки. Если вы начнете с маленьких чисел, вы не потеряете точность до конца, когда это не важно.   -  person Joe White    schedule 28.09.2014
comment
Кроме того, вы понимаете, что ваш цикл выполняет numberOfSumElements - 1 итерацию, верно? (for (double i = 1; i < numberOfSumElements; i++)) Таким образом, либо ваше сравнение цикла должно быть <= вместо <, либо ваша переменная имеет неверное имя.   -  person Joe White    schedule 28.09.2014
comment
Прочтите формулу и закодируйте всех. OP жалуется, что цикл работает медленно, когда precision ›= 8, для чего цикл выполняется 10 ^ 10 раз! Это 10 000 000 000 итераций. Конечно, это медленно.   -  person Pieter Geerkens    schedule 28.09.2014
comment
Если у вас есть свобода выбора алгоритма, проверьте это сообщение: stackoverflow.com/questions/14283270/   -  person Pieter Geerkens    schedule 28.09.2014

Ответы (1)


arrow_upward
9
arrow_downward 

   double numberOfSumElements = Math.Pow(10, presicion + 2);

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

Сначала обратите внимание на сложность вашего кода. Время выполнения строго определяется этим выражением. Вы написали экспоненциальный алгоритм, значение, которое вы вычисляете, очень быстро растет по мере увеличения предположения. Вы цитируете неудобное число, 8 дает 10 ^ 10 или цикл, который производит десять миллиардов вычислений. Да, вы заметили это, когда компьютерам нужны секунды, чтобы произвести результат, независимо от того, насколько они быстры.

Экспоненциальные алгоритмы плохие, они очень плохо работают. Вы можете сделать только хуже, если у вас факториальная сложность, O (n!), Которая растет еще быстрее. В противном случае сложность многих реальных проблем.

Итак, действительно ли это выражение верно? Вы можете сделать это с помощью «локтевого теста», используя практический пример обратной стороны конверта. Давайте выберем в качестве цели точность в 5 цифр и запишем ее:

 1.0000 + 0.2500 + 0.1111 + 0.0625 + 0.0400 + 0.0278 + ...  = 1.6433

Вы можете сказать, что добавлений быстро становится меньше, они быстро сходятся. Вы можете предположить, что, как только следующее число, которое вы добавляете, станет достаточно маленьким, оно очень мало сделает результат более точным. Допустим, когда следующее число меньше 0,00001, пора перестать пытаться улучшить результат.

Итак, вы остановитесь на 1 / (n * n) = 0,00001 => n * n = 100000 => n = sqrt (100000) => n ~ = 316

Ваше выражение говорит, что нужно остановиться на 10 ^ (5 + 2) = 10,000,000

Вы можете сказать, что вы далеко, слишком часто выполняете цикл и не улучшаете точность результата за последние 9,999 миллиона итераций.

Пора поговорить о реальной проблеме, жаль, что вы не объяснили, как вы пришли к такому совершенно неправильному алгоритму. Но наверняка вы обнаружили при тестировании своего кода, что он не очень хорошо рассчитывает более точное значение числа Пи. Итак, вы подумали, что, выполняя итерацию чаще, вы получите лучший результат.

Обратите внимание, что в этом локтевом тесте также очень важно, чтобы вы могли рассчитать добавки с достаточной точностью. Я намеренно округлил числа, как если бы они были рассчитаны на машине, способной выполнять сложение с точностью до 5 знаков. Что бы вы ни делали, результат никогда не может быть точнее, чем 5 цифр.

Вы используете в своем коде тип double. Непосредственно поддерживаемый процессором, он не обладает бесконечной точностью. Единственное правило, о котором нужно помнить, - это то, что вычисления с double никогда не могут быть точнее 15 цифр. Также запомните правило для float, оно никогда не бывает более точным, чем 7 цифр.

Поэтому независимо от того, какое значение вы передаете для presicion, результат никогда не может быть точнее 15 цифр. Это совершенно бесполезно, у вас уже есть значение Пи с точностью до 15 цифр. Это Math.Pi

Единственное, что вам нужно сделать, чтобы исправить это, - использовать тип с большей точностью, чем double. Фактически, это должен быть тип с произвольной точностью, он должен быть не менее точным, чем переданное вами значение presicion. Такой тип не существует в платформе .NET. Найти библиотеку, которая может вам ее предоставить, - это распространенный вопрос на ТАК.

person Hans Passant    schedule 28.09.2014