Аппроксимирующие константы π2 в пределах погрешности


Эта функция принимает в качестве входных данных ошибка поплавка и равна постоянной π2 в пределах погрешности при вычислении этой суммы, почленно, пока разница между новой и предыдущей суммой меньше ошибок. Функция должна вернуть новую сумму.

$$ \пи^2 = 8 + \dfrac{8}{3^2} + \dfrac{8}{5^2} + \dfrac{8}{7^2} + \dfrac{8}{9^2} + \cdots $$

Пример:

approxPIsquared(0.0001)

Результат 9.855519952254232

Мое рабочее решение показано ниже:

def approxPIsquared(error):
    prev = 8
    new =0
    n = 3
    while (True):
        new = (prev + (8 / (n * n)))
        diff = new - prev
        if (diff <= error):
            break
        prev = new
        n = n + 2

    return new

Это хорошее решение, или есть ли лучший способ сделать это?



Комментарии
8 ответов

enter image description here

Вам не нужно сравнивать prev и new во время каждой итерации.

Разница между новой и предыдущей суммой является просто текущей перспективе : $$\фрац{8}{(2И+1)^2}$$

Если вы хотите, чтобы этот срок будет меньше errorвы можете решить:

$\$mathrm{ошибка} > \фрац{8}{(2И+1)^2}\\
\МКФ (2И+1)^2 > \фрац{8}{Ошибка}\\
\МКФ 2И+1 > такой: \sqrt{\фрац{8}{Ошибка}}\\
\МФЛ я > \фрац{\функция sqrt{\фрац{8}{Ошибка}} - 1}{2}\\
$$

Теперь, когда вы знаете, сколько сроков вашей серии должна иметь, вы можете вернуть результат напрямую:

def approx_pi_squared(error):
n = int(((8 / error)**0.5 - 1) / 2) + 1
return sum(8 / (2 * i + 1)**2 for i in range(n))

Лучше формулы

Добавление дельты

Обратите внимание, что error представляет как маленький термины, не как близко approx_pi_squared от π2:

>>> import math
>>> approx_pi_squared(1e-10)
9.869590258918535
>>> math.pi**2 - approx_pi_squared(1e-7)
0.0004472271895057389
>>> math.pi**2 - approx_pi_squared(1e-10)
1.414217082285063e-05

Даже с более чем 140 000 терминов, серия только 3 первые цифры π2. Эта формула очень проста, но сходится слишком медленно.

Что очень интересно, что разница между math.pi**2 и approx_pi_squared(error) кажется, очень близко к \$\функция sqrt{2\mathrm{ошибка}}\$. Это, кажется, справедливо для любого error, чтобы мы могли обновить функции:

def approx_pi_squared(error):
n = int(((8 / error)**0.5 - 1) / 2) + 1
delta = (2 * error)**0.5
return sum(8 / (2 * i + 1)**2 for i in range(n)) + delta

approx_pi_squared(1e-10) теперь возвращает 10 правильных цифр для π2.

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

Формулы ББП

Есть много π2 формулы, так что не стесняйтесь, чтобы забрать еще один. Например:

def approx_pi_squared(error):
n = int(((12 / error)**0.5 - 1) / 2) + 1
return 12 * sum((-1)**i / (i + 1)**2 for i in range(n))

error кажется, имеют тот же порядок величины, как math.pi**2 - approx_pi_squared(error) сейчас:

>>> math.pi**2 - approx_pi_squared(1e-9)
2.0001476030984122e-09
>>> math.pi**2 - approx_pi_squared(1e-10)
-1.9977974829998857e-10

delta похоже (-1)**n * 2 * error.

С Sympy

Вы можете делегировать работу sympy и будьте уверены, вы получите правильный результат с произвольной точностью:

>>> from sympy import Sum, N, pi, oo, init_printing
>>> from sympy.abc import i, n
>>> init_printing()
>>> Sum(8/(2*i+1)**2, (i, 0, oo))

____

╲ 8
╲ ──────────
╱ 2
╱ (2⋅i + 1)

‾‾‾‾
i = 0
>>> N(Sum(8/(2*i+1)**2, (i, 0, oo)), 100)
9.869604401089358618834490999876151135313699407240790626413349376220044822419205243001773403718552232
>>> N(pi**2, 100)
9.869604401089358618834490999876151135313699407240790626413349376220044822419205243001773403718552232

27
ответ дан 6 марта 2018 в 11:03 Источник Поделиться

Итак, у вас есть многочлен последовательности и хотим подвести свои условия, когда они больше, чем предусмотрено толерантность (то есть: допуск более низкой, чем текущая вычисленный срок).

Это легко выражается через базовые конструкции языка Python / примитивы и itertools модуль:


  1. Бесконечное полиномиальной последовательности может быть описан с помощью генератора выражение и бесконечного счетчика itertools.count:

    polynomial_sequence = (8 / (n * n) for n in itertools.count(1, 2))

  2. Вы можете извлекать термины из итерируемый (и генератор выражений итераторы), а они отвечают условию, используя itertools.takewhile:

    approximate_finite_sequence = itertools.takewhile(tolerance.__lt__, polynomial_sequence)

    Здесь __lt__ это волшебный метод, который вызывается при tolerance < … написано, так что условия последовательность будет сохраняться while tolerance < term. Но вопреки своей реализации, первый термин, который меньше терпимости не будет поддерживаться и, следовательно, не прибавляются к сумме для приближения.


  3. Вы можете суммировать все созданные условия, используя встроенный sum:

    pi_squared = sum(approximate_finite_sequence)


Собираем все вместе:

import itertools

def approximate_pi_squared(tolerance=0.0001):
polynomial_sequence = (8 / (n * n) for n in itertools.count(1, 2))
return sum(itertools.takewhile(tolerance.__lt__, polynomial_sequence))

19
ответ дан 6 марта 2018 в 09:03 Источник Поделиться


  1. Пожалуйста, исправить вмятины (видимо просто скопировать вопрос).

  2. В Python, вы не нужны скобки вокруг выражения для блока заявления типа if и while. Вам также не нужно вокруг вашего выражения (спасибо Эв. Kounis).

  3. Вы можете использовать i ** 2 вместо i * i.

  4. Вы можете использовать оператор инкремента: n += 2 вместо n = n + 2.

  5. Вы должны, вероятно, использовать i вместо n для счетчика переменных (в большинстве случаев [спасибо Coal_]).

  6. Вы можете использовать (обязательно import itertools; Я лично предпочитаю использовать from itertools import count):

    for n in itertools.count(3, 2):
    ...

    вместо

    n = 3
    while (True):
    ...
    n = n + 2

  7. Нет необходимости иметь временное diff переменной.

  8. Использовать snake_case но все же классы и "константы".

  9. Вы можете return вместо breakИнг (спасибо @hjpotter92).

Результат:

from itertools import count

def approx_pi_squared(error):
prev = 8
new = 0
for i in count(3, 2):
new = prev + 8 / i ** 2
if new - prev <= error:
return new
prev = new

15
ответ дан 6 марта 2018 в 01:03 Источник Поделиться

Когда Соломон Ucko предоставил отличную обратную связь о стиле кодирования, и дал соответствующие изменения дали свой оригинальный алгоритм, я решил сосредоточиться на бирке характеристик, которые вы добавили.

Есть много более эффективных формул для вычисления Пи, но давайте использовать тот, который вы предоставили, и сделать это быстрее. Выполнив свои функции для различных входов на форме 10^(-n)Я узнал, что ваша программа выполняется О 10**(n/2+.5) итераций (это было около 5-10% меньше).

Однажды я имел очень ограниченную количество итераций, я мог бы прибегнуть к помощи библиотеки numpy, который невероятно быстро для такого рода операций. Скрипт, который я в конечном итоге с помощью:

import numpy as np

def approx_pi_squared_fast(decimals):
n = int(10**(decimals/2+.5))
denominators = np.arange(1, 2*n, 2)**2
pi_squared = np.sum(8/denominators)
return pi_squared

Я поменял ввод от error для decimalsтак, новая программа не возвращает те же значения, как те, что вы выложили. Однако, он не возвращает более точные значения для всех входов между 1-15 (после этого ваш скрипт занимает более 10 секунд, чтобы проверить). Она также возвращает ответ в 4-6 раз быстрее, чем оригинальный сценарий.

Редактировать: Редактировать имя функции

6
ответ дан 6 марта 2018 в 09:03 Источник Поделиться

Бритвы Оккама (не умножать сущности без надобности), может быть применено также к переменным.

    prev = 8
new = 0
...
new = (prev + (8 / (n * n)))
diff = new - prev
...
prev = new

является излишне сложным. Вы знаете diff, Так что вы можете сократить prev и new С одной переменной, с более информативным названием (напр. sum):

    sum = 8
...
diff = 8 / (n * n)
sum += diff
...


Сделав явным то, что разница в том, что мы можем решить самые большие проблемы: корректность. Чтобы правильно сложить список чисел с плавающей точкой, вы должны начать с самых маленьких, не крупных. Но поскольку у нас теперь есть простое выражение для diff как функция nмы можем переверните его, чтобы найти первое значение n для которых срок составляет менее нужные ошибки, используя sqrt.

6
ответ дан 6 марта 2018 в 09:03 Источник Поделиться

Все существующие ответы предоставить ценную обратную связь, но есть один момент мне кажется не хватает, обсуждение выбора оператор цикла. В свой первоначальный алгоритм вы использовали while True: вместе с if... break. Почему бы не поставить условие проверки if в whileт. е. что-то вроде while diff > error:?

Это имеет то преимущество, что сразу понятно, что такое условие-это, следовательно, делает код легче понять. Это по умолчанию в Соломоновы Ucko в остальном отличный ответ, по крайней мере на мой взгляд. Его for n in itertools.count(3, 2): ничего не сказано о расторжении состоянии.

5
ответ дан 6 марта 2018 в 11:03 Источник Поделиться

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

def approx_pi_squared(error, curr=8, i=3):
new = curr + (8 / (i * i))
if new - curr <= error:
return new
else:
return approx_pi_squared(error, new, i+2)

Так что если на текущей итерации не вписывается в границу, тогда вам будет просто сделать функцию снова, но используете Предыдущее значение и i+2 в функции. На мой взгляд, это выглядит немного чище, хотя это не спасает любое время.

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

def approx_pi_squared(error, curr=8, i=3):
new = curr + (8 / (i * i))
if new - curr <= error:
decimal_index = str(error).index('.') + 1 # after decimal
num_decimal = len(str(error)[decimal_index:])
return round(new, num_decimal)
else:
return approx_pi_squared(error, new, i+2)

Все это дело найти, откуда десятичных находится во входном ошибки и подсчитывает количество цифр, поэтому результат совпадает с количеством десятичных знаков, ввод ошибка. Так что если вы запустите этот Вас approx_pi_squared(0.0001) вы вернулись 9.8555. Глядя вверх pi * piЯ считаю, что это ближе к 9.8696. Откуда формула взялась? Я пытаюсь найти его, но я не в состоянии.

1
ответ дан 6 марта 2018 в 01:03 Источник Поделиться

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

1
ответ дан 6 марта 2018 в 06:03 Источник Поделиться