Вера в 1+1=2 сильно пошатнулась

Среда PascalABC.NET
#1

Вот только что на киберфоруме в разделе PABC.NET мы разбирались с простым, казало бы примером: „Определить сумму всех элементов последовательности на произвольном интервале изменения индексов. ai,j = sin2i + cos²j “

В результате получилось вот что:

  WriteLn(Range(i0,i1).Select(i->sin(2*i)).Sum * (j1-j0+1) + Range(j0,j1).Select(j->sqr(cos(j))).Sum * (i1-i0+1));
  WriteLn(MillisecondsDelta);

  writeln(Range(i0,i1).Cartesian(Range(j0,j1)).Sum(v->sin(2*v[0]) + sqr(cos(v[1]))));
  WriteLn(MillisecondsDelta);

  writeln(Range(i0,i1).Cartesian(Range(j0,j1)).Select(v->sin(2*v[0]) + sqr(cos(v[1]))).Sum);
  WriteLn(MillisecondsDelta);

  var s := 0.0;
  for var i := i0 to i1 do
    for var j := j0 to j1 do
      s += sin(2*i) + sqr(cos(j));
  WriteLn(s);
  WriteLn(MillisecondsDelta);

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

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

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

1 лайк
#2
  1. Вроде, range не включает в себя элемент со вторым аругментом (индекс i1 и j1), а в последнем варианте цикл включает.
  2. Повысить точность можно такими методами
    1. Отсортировать элементы и начинать суммирование с наименьших.
    2. Сгруппировать элементы парами и просуммировать пары. Повторять эту процедуру, пока не получится одно число – итоговая сумма.

Второй вариант предпочтителен, когда слагаемых много и они примерно одного порядка.

К сожалению, эти методы скорости не прибавят.

#3

Насчёт первого пункта оказался неправ – Range в PascalABC.NET последний элемент включается.

#4

Ни какой разницы от сортировки:

begin
  var i0 := -1000;
  var i1 := +1000;
  var j0 := -1000;
  var j1 := +1000;
  MillisecondsDelta;

  WriteLn(Range(i0,i1).Select(i->sin(2*i)).Sorted.Sum * (j1-j0+1) + Range(j0,j1).Select(j->sqr(cos(j))).Sorted.Sum * (i1-i0+1));
  WriteLn(MillisecondsDelta);

  var s := 0.0;
  for var i := i0 to i1 do
    for var j := j0 to j1 do
      s += sin(2*i) + sqr(cos(j));
  WriteLn(s);
  WriteLn(MillisecondsDelta);
end.

2002230.32680519 16 2002230.32680505 344

#5

А что было до сортировки? Ну, и первое значение у вас точнее второго получилось.

Вот правильный ответ с запасом цифр: 2002230.3268051866005911170309981

#6

— Абсолютно то-же самое.

— А считалось второе простыми циклами!

— Каков же код?

#7

У вас относительная погрешность получилась порядка 1e-15. Подозреваю, вычисление тригонометрических функций для больших аргументов имеет тот же порядок погрешности, так что большую точность на 8-байтных флоатах скорее всего не получить.

— Каков же код?

Код на Python:

from mpmath import mp
mp.prec = 157
s = mp.mpf(0)
for i in range(-1000, 1001):
    for j in range(-1000, 1001):
        s += mp.sin(2*i) + mp.cos(j)**2;
print(s)
#8

Это хорошо! Но, мы находимся в разделе PABC.NET. Поэтому код ожидается на нём! А ваш код, переведённый на PABC выдаёт:

2002230.32680505 438

s := 0.0;
foreach var i in range(i0,i1) do
  foreach var j in range(j0,j1) do
    s += sin(2*i) + sqr(cos(j));
WriteLn(s);
WriteLn(MillisecondsDelta);
#9

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

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

#10

А так не пробовали?

begin
  var i0 := -1000; var i1 := 1000;
  var j0 := -1000; var j1 := 1000;

  var sx : double := 0.0; 
  for var i := i0 to i1 do
    sx += sin(2*i);
  
  var sy : double := 0.0;
  for var i := j0 to j1 do
    sy += sqr(cos(i));
    
  WriteLn(sx*(j1-j0+1)+sy*(i1-i0+1));
  WriteLn('Ms : ' , MillisecondsDelta);
end.
#11

По-моему, вопрос совершенно не зависит от того, PascalABC.NET это или иная среда программирования. Вопрос о нахождении суммы нескольких слагаемых в рамках ограниченной точности представления данных, находящихся в большом диапазоне, относится к проблематике организации процесса вычислений, а не особенностям реализации языка или платформы. Если используется библиотека (в частности, LINQ to Objects), то реализация части алгоритма скрыта и попытки увеличить точность результата - это игра в рулетку с черным ящиком. Хочется гарантированно иметь максимально возможную в данных условиях точность - реализуйте все на базе примитивных циклов. Это одна из причин того, почему в серьезных расчетах до сих пор используется Фортран.

3 лайка
#12

Вопрос, вынесенный в заголовок, - другой. Вопрос - о вере. А она - пошатнулась

3 лайка
#13

Ну а нечего верить во что ни попадя :smile:

#14

Так что - нельзя в Большого Летающего Макаронного монстра?

#15

Навеяло все это воспоминания о додревнем еврейском анекдоте.

– Ребе, у меня дохнут куры. Что делать? – Кидай им зерно в круг, предварительно его начертив. Еврей начертил круг, стал кидать в него зерно, но куры все равно дохли. Тогда он опять пришел к ребе: – Что делать? – Нарисуй квадрат и бросай зерно в квадрат. Еврей нарисовал квадрат, стал бросать в него зерно, но куры все равно дохли. – Что делать, ребе? – Нарисуй треугольник и бросай зерно в треугольник. Еврей нарисовал треугольник и стал бросать туда зерно. Куры сдохли все. – Ребе, все куры сдохли. – Жалко, у меня было еще столько хороших идей!

#16

Можно верить, дело личное, но ждать от него спагетти с тефтельками не нужно :wink:

Более серьезно, мы говорим о вычислениях с плавающей запятой, которые не совсем такие, как точные. Например, общеизвестным (?) фактом является зависимость от порядка суммирования и тому подобные вещи… Когда-то этому учили… Наверное…

#17

Учили. Даже у нас, в техническом вузе, в начале далёких 70-х.Тогда еще и предмета информатики не было в помине в школах, а в вузах непрофильных для электронной вычислитепьной техники был односеместровый курс “Прикладная математика”. Вот там и учили - все сразу.