Решение

@Eddy_Em · 19.05.2022, 23:51

Студворк — интернет-сервис помощи студентам

Alexis333, да, соглашусь: я проврался.
Как не хочется ссылку на говноресурс давать, но дам. Вот.

@QueryMonkey · 20.05.2022, 00:15 **[ТС]**

Alexis333, "дальнейшее увеличение числа итераций в 10 раз (до 20000) добавляет ещё 3 значащие цифры,"

Какой у вас получился ответ?

Совпали ли три дополнительные цифры с числом пи, или результат пал жертвой округлении, наличие и размер которых программист не заметил?

Добавлено через 3 минуты
"два часа работы" имелось в виду два часа усилий программиста, чтобы найти (не угадать) следующую цифру-две.

Добавлено через 17 минут

Сообщение от Alexis333

Я хоть и не программист, но набросал такой простенький алгоритм:

Я прогнал ваш алгоритм два миллиона циклов, получил число "3.00000000000000".
Это случилось из-за целочисленного деления.

После исправления ошибки получил ответ 3.38974693269176 (два миллиона циклов)

Это не похоже на число пи, хотя первая цифра совпадает.

@Alexis · 20.05.2022, 00:16

Сообщение от QueryMonkey

Совпали ли три дополнительные цифры с числом пи

20000 итераций даёт 14 верных знаков (я сравнивал с пи из калькулятора windows, там 32 знака), дальше уточнение прекращается, но оно и понятно, double позволяет хранить только 15 десятичных знаков. Если Вы о накоплении ошибок округления, то оно не большое. При желании можно конечно оценить, но по хорошему работать нужно в целочисленной арифметике, там с этим проще.

@QueryMonkey · 20.05.2022, 00:23 **[ТС]**

Сообщение от Eddy_Em

Как не хочется ссылку на говноресурс давать, но дам. Вот.

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

Code
1
2
3
position = 1000000
 fraction = 0.423429797567895 
 hex digits =  6C65E52CB4

У вас получится за пару часов доработать незнакомый код неизвестного качества с интернета, чтобы распечатать 10 первых цифр числа Пи?

Добавлено через 1 минуту

Сообщение от Alexis333

20000 итераций даёт 14 верных знаков

Учитывая что ваш код не компилируется, как вам удалось его запустить?
Если у вас есть более новая версия которая работает правильно, можно ли ее увидеть?

@Alexis · 20.05.2022, 00:25

Я набирал вручную, т.к. компилятор на другом компе, наделал ошибок.
Вот исправленный вариант:

C
1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main(void)
{
  double PI=3.0;
  int j=1, k;
  while (j<200)
  {
    k=2*j; PI+=4/(k*(k+1.0)*(k+2.0)); j++;
    k=2*j; PI-=4/(k*(k+1.0)*(k+2.0)); j++;
  }
  printf("%16.14f", PI);
}

@QueryMonkey · 20.05.2022, 00:35 **[ТС]**

Сообщение от Alexis333

Вот исправленный вариант:

Запустил, сработало очень быстро. На моем компе получил ответ 3.14159262280485
Вам удалось получить столько же правильных цифр, сколько китайскому математику 2500 лет назад.

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

(подсматривать ответ не разрешается, нужно самому определить сколько цифр являются верными)

Добавлено через 3 минуты
Не огорчайтесь. Программу которую я привел в начале темы содержит похожую ошибку, я как раз на нее хотел обратить внимание. (С какой точностью современный программист может посчитать число Пи за разумное время (пару часов))

Кто-то еще хочет попробовать свои силы в вычислении *верных* первых десяти цифр Пи?

@Alexis · 20.05.2022, 00:38

QueryMonkey, ну так Вы замените условие выхода while (j<200) на while(j<20000)

@QueryMonkey · 20.05.2022, 00:54 **[ТС]**

Сообщение от Alexis333

QueryMonkey, ну так Вы замените условие выхода while (j<200) на while(j<20000)

Code
1
2
3
4
5
200:     3.14159262280485
2000:    3.14159265355859
20000:   3.14159265358976
200000:  3.14159265358979
2000000: 3.14159265358979

Получилось. Вопрос к вам: как с этим алгоритмом определить сколько цифр верные?

Когда она перестала меняться "некоторое время", или есть более конкретный критерий?
Особая проблема если цифра равна 9 или за ней стоит девятка.
Поскольку последовательность мотонно растет, где гарантия что 3.141.....39...
не превратится в 3.141......40..... через несколько итераций?

@Alexis · 20.05.2022, 01:21

Сообщение от QueryMonkey

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

Боюсь, что Вы заблуждаетесь. Вот код с оценкой погрешности:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int main(void)
{
  double PI=3.0, r, k;
  int j=1;
  while (j<200)
  {
    k=2*j; PI+=4/(k*(k+1.0)*(k+2.0)); j++;
    k=2*j; PI-=4/(k*(k+1.0)*(k+2.0)); j++;
  }
  k=2*j; r=4/(k*(k+1.0)*(k+2.0));
  printf("%16.14f\n%e", PI, r);
}

Добавлено через 4 минуты
Более строго, в оценке погрешности нужно учитывать ошибки округления, но в первом приближении пойдёт и так.
Думаю понятно, что больше 15 верных цифр с числами double получить никак не получится.

Добавлено через 19 минут
На всякий случай сообщаю, что это был ряд Нилаканта, сходящийся намного быстрее ряда Лейбница.

@Eddy_Em · 20.05.2022, 01:57

Сообщение от QueryMonkey

У вас получится за пару часов доработать незнакомый код неизвестного качества с интернета, чтобы распечатать 10 первых цифр числа Пи?

Цена вопроса?

@QueryMonkey · 20.05.2022, 06:21 **[ТС]**

Спасибо, теперь вижу что разница между верхним и нижним пределом не превышает 4/k³.

А сколько вообще можно ожидать надежных цифр от double? Там мантисса 53 бита, т.е. чуть-чуть не дотягивает до 16 десятичных.

Получилось вымучать 20 цифр используя long double (в моем компиляторе gcc это 128 бит но арифметика, увы, 96 бит)

C++
1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
 
int main()
{
  long double pi = 0;
  for( long double i = 4e6 ; i >= 4 ; i -= 4 )
    pi += (long double)24 / ((i*i-1)*(i*i-4));
  printf("3.%020lu\n", (unsigned long)(pi*1e20) );
  printf("%.20Lf, sizeof(long double) = %lu\n", 3+pi, sizeof(long double) );
  printf("%.40Lf\n", 1+(long double)1e-28 );
}

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

~/code$ ./a.out
3.14159265358979323843
3.14159265358979323851, sizeof(long double) = 16
1.00000000000000000000000000000000000000 00

Добавлено через 3 минуты

Сообщение от Eddy_Em

Цена вопроса?

"непрограммист" Alexis333 уже решил эту задачку, включая оценку погрешности.

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

@Alexis · 20.05.2022, 12:24

У double 15-16 значащих десятичных цифр, с представленным выше алгоритмом все они получились значимыми. В long double, (в Вашем 16 байтовом варианте), 33 значащих цифры. С учётом установленной ранее скорости сходимости, для получения 33 значащих цифр потребуется 1 трлн. итераций. Ожидаемое накопление ошибки при суммировании оценивается как $https://www.cyberforum.ru/cgi-bin/latex.cgi?\epsilon \sqrt\N =10^{-34}\sqrt(10^{12})=10^{-28}$ , а в худшем случае $https://www.cyberforum.ru/cgi-bin/latex.cgi?\epsilon \sqrt\N =10^{-34}10^{12}=10^{-22}$ , т.е. теряется от 6 до 12 знаков. В итоге, ожидаемая точность 25 знаков.
В случае с double терялось максимум 2-4 знака, а как показывает опыт - ещё меньше.

Попробуйте вот такой вариант, точность должна быть хорошей

C
1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main(void)
{
  long double PI=3.0, r, k, e=0.0, t;
  long long j=1;
  while (j<1000000000000)
  {
    k=2*j; r= 4/(k*(k+1.0)*(k+2.0))-e; t=PI+r; e=(t-PI)-r;  PI=t; j++;
    k=2*j; r=-4/(k*(k+1.0)*(k+2.0))-e; t=PI+r; e=(t-PI)-r;  PI=t; j++;
  }
  k=2*j; r=4/(k*(k+1.0)*(k+2));
  printf("%34.32f\n%e", PI, r);

@QueryMonkey · 20.05.2022, 17:56 **[ТС]**

Сообщение от Alexis333

В long double, (в Вашем 16 байтовом варианте), 33 значащих цифры.

Увы, у меня 1+1е-28 дает 1.0000000000000000000000000000000000000
Мой 16-байтовый long double похоже не хранит 128-битовое число, просто выравнен на границе.

Триллион итераций на моем компе займет несколько часов, но я попробовал 10 миллиардов.

3.14159265358979323846264338327950288419 716 <- известные числа Пи из справочника
3.14159265358979323851280895940619 <- распечатка из программы (10Г цикл), 19 верных цифр
5.000000e-31 <- оценка точности из программы, намекает что 30 цифр должны быть верны

Запустил 100 млрд цикл, жду.

Добавлено через 32 минуты
Результат для 100Г цикла, первая строчка для сравнения

3.14159265358979323846264338327950288419 716 <- известные числа Пи из справочника
3.14159265358979323851280895940619 <-- то же число, что и для 10 млрд цикла
5.000000e-34
real 18m1.635s
user 17m46.035s
sys 0m1.651s

Как я вижу из этих результатов, 19 значащих цифр это ограничение 80-битной арифметики х87, где мантисса 64+1 бит.
Более длинных плавающих в моем компиляторе нет, поэтому это максимум.
Можно выжать еще одну цифру как я сделал в примере, если не добавлять 3.0. Добавление этой константы убивает одну цифру точности.

@Alexis · 20.05.2022, 18:32

К большому соалению у меня VC++ и нет long duble. Но я попробовал через целочисленную арифметику, вот такой код:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
 
int _tmain(int argc, _TCHAR* argv[])
{
    const long long C=4000000000000000000;
    long long PiH=3000000000000000000, PiL=0, dH, dL;
    long long j=1, p, u=1000000000;
 
    while (j<1000000000)
    {
     p=2*j; dH=C/p; dL=((C%p)*u)/p; p++;
     dL/=p; dL+=((dH%p)*u)/p; dH/=p; if (dL>=u) {dL-=u;  dH++;} p++;
     dL/=p; dL+=((dH%p)*u)/p; dH/=p; if (dL>=u) {dL-=u;  dH++;} p++;
     PiH+=dH; PiL+=dL; if (PiL>=u) {PiL-=u;  PiH++;} j++;
 
     p=2*j; dH=C/p; dL=((C%p)*u)/p; p++;
     dL/=p; dL+=((dH%p)*u)/p; dH/=p; if (dL>=u) {dL-=u;  dH++;} p++;
     dL/=p; dL+=((dH%p)*u)/p; dH/=p; if (dL>=u) {dL-=u;  dH++;} p++;
     PiH-=dH; PiL-=dL; if (PiL<0) {PiL+=u;  PiH--;} j++;
    }
    
    printf("%I64d%I64d", PiH, PiL);
    getchar();
    return 0;
}

1 млрд. итераций даёт 24 верных знака.

Добавлено через 23 минуты
Нашел проблему, идёт накопление ошибок при целочисленном сложении. Если в приведённом выше алгоритме уменьшить число итераций до 100 млн. и увеличить переменную u до 10 млрд., то точность возрастает до 28 знаков, а время работы уменьшается с 1 минуты до 6 сек.
QueryMonkey, не нужно стремиться увеличить число итераций, с определённого момента из-за накопления ошибок начинает только падать.

@QueryMonkey · 20.05.2022, 19:05 **[ТС]**

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

Сообщение от Alexis333

с определённого момента из-за накопления ошибок начинает только падать.

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

1.0 + 1e-30 == 1.0, т.к. малый довесок к единице теряется без следа, если превосходит разрядность мантиссы.

P.S. Да, я тоже прочитал что MSVC "схитрил" и поленился сделать более длинный тип.

@Alexis · 20.05.2022, 19:26

Сообщение от QueryMonkey

P.S. Да, я тоже прочитал что MSVC "схитрил" и поленился сделать более длинный тип

Зато в GCC кажется есть int128 и Вы смогли бы запустить с ним последний алгоритм. Менять нужно u и число итераций, чтобы их произведение не приводило к переполнению int128. У меня int64, поэтому не получается проверить, но думаю, что точность увеличится существенно.

@QueryMonkey · 20.05.2022, 20:07 **[ТС]**

Alexis333, я как раз писал с unsigned __int128 когда ударила молния и в моем хуторе пропал свет.
Упса хватило только чтоб сервак потушить.

@Alexis · 20.05.2022, 20:38

Жаль, на самом интересном месте ...
Кстати, unsigned для PiL лучше не используйте, по ходу работы он может быть и отрицательным.

@QueryMonkey · 21.05.2022, 04:06 **[ТС]**

Сообщение от Alexis333

Жаль, на самом интересном месте ...

Свет починили, а вот программа меня помучала.

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

Нашел вот такой сюрприз:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
 
int main()
{
    unsigned __int128 u = 1e36; // <============== !!!!
    char sz[100] = "\n";
    int  i = 1;
 
    do
        sz[i++] = (char)('0' + u%10);
    while( u /= 10 );
    while( i-- )
      putchar( sz[i] );
}

Инициализация больших значений __int128 содержит грабли, т.к. константы такого типа в моем компиляторе не определены, самое длинное это 1LL или 1ULL для 64-битного long long.

А попытка инициализировать через экспоненту не дала предупшреждений, но присвоила не то, что я ожидал:
1000000000000000042420637374017961984

Близко, но не совсем 1е36. Из-за этого у меня число Пи зашкаливало в районе 7 миллионного цикла.

@Alexis · 21.05.2022, 06:24

QueryMonkey, какая в итоге получилась точность?

Новые блоги и статьи Все статьи Все блоги /
Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .

@Eddy_Em Нарушитель 444 / 885 / 105 Регистрация: 23.11.2021 Сообщений: 5,197 Записей в блоге: 19
	19.05.2022, 23:51
	Alexis333, да, соглашусь: я проврался. Как не хочется ссылку на говноресурс давать, но дам. Вот. 0

@Alexis 496 / 543 / 131 Регистрация: 31.10.2016 Сообщений: 4,397
	20.05.2022, 00:38
	QueryMonkey, ну так Вы замените условие выхода while (j<200) на while(j<20000) 0

@QueryMonkey Нарушающий 417 / 305 / 46 Регистрация: 13.04.2022 Сообщений: 1,759
	20.05.2022, 20:07 [ТС]
	Alexis333, я как раз писал с unsigned __int128 когда ударила молния и в моем хуторе пропал свет. Упса хватило только чтоб сервак потушить. 0

@Alexis 496 / 543 / 131 Регистрация: 31.10.2016 Сообщений: 4,397
	20.05.2022, 20:38
	Жаль, на самом интересном месте ... Кстати, unsigned для PiL лучше не используйте, по ходу работы он может быть и отрицательным. 0

@Alexis 496 / 543 / 131 Регистрация: 31.10.2016 Сообщений: 4,397
	21.05.2022, 06:24
	QueryMonkey, какая в итоге получилась точность? 0