почему сумма списка чисел неодинаковая?

[Antares99]

Имеется список чисел (массив) с относительно большими показателями степеней. Например:
5*10^70
3*10^-40
1*10^80
3,3*10^-70 то есть числа как очень большие, так и очень маленькие.
Массив может содержать большое количество чисел, от нескольких сотен, до миллиона. Если считаю в Паскале (и не только в нём) сумму всех чисел, то меняется результат в зависимости от направления откуда начал складывать. Если программа вычисляя сумму чисел всего списка начинает складывать эти числа с начала списка в конец списка, то результат почему-то получается один.
Если же задать программе начинать сложение с конца списка в начало, то результат получается другой. Говорят, тот же глюк был и на советских программируемых микрокалькуляторах Электроника МК-52, МК-61 и так далее.
ПОЧЕМУ?

[Xaositect]

http://docs.oracle.com/cd/E19957-01/806 ... dberg.html

[Antares99]

Xaositect в сообщении #554169 писал(а):

http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

извините, столько текста на английском освоить не смогу

[ewert]

Antares99 в сообщении #554138 писал(а):

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

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

[Евгений Машеров]

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

[Antares99]

ewert, Евгений Мишеров, большое спасибо! Теперь понял. А то я думал, что электронные вычислительные устройства обладают абсолютной точностью. И свято им верил. А оно вот как эх. Ну хотя бы теперь буду знать, что от перемены мест слагаемых сумма может меняться..

[Евгений Машеров]

Ну, не на английском (ну, то есть на английском, но перевели) - есть Кнут, второй том, есть Каханер Д., Моулер К., Нэш С. Численные методы и математическое обеспечение и другие пособия.
И для раздумий - 0.1 так же не представимо точно в двоичной системе, как $\frac 1 3$ в десятичной.

[ewert]

Antares99 в сообщении #554218 писал(а):

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

Они действительно обладают абсолютной точностью (кстати, меня всегда удивляло: как это на персоналках умудрились добиться практически абсолютной надёжности, в отличие от "больших" машин 70-х-80-х годов, которые постоянно сбоили; что, впрочем, смотрелось вполне естественно).

Только вот абсолютно точны они лишь для целочисленных вычислений. Реальные же -- это всегда то или иное приближение. Просто по определению реальности.

[Antares99]

Евгений Машеров в сообщении #554192 писал(а):

Особенно чётко это проявляется при числах с разыми знаками.

Вы имеете в виду положительные и отрицательные числа? Или показатели степеней? Если числа, то почему эффект проявляется особенно сильно в этом случае? Если я складываю числа в хаотичном порядке, большие и малые, не всё ли равно, положительные они или отрицательные? В любом случае будет ошибка

[Toucan]

К общим вопросам математики тема отношения не имеет; переехали в Программирование.

[Евгений Машеров]

(Оффтоп)

Хмм... Всегда полагал, что вычислительная математика - тоже математика. Впрочем, не смею возражать.

[Евгений Машеров]

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

[ewert]

Евгений Машеров в сообщении #555964 писал(а):

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

Пусть $a_1=1$ и $a_2,a_3,\ldots,a_{10^{18}}=10^{-18}$. Сложите их сначала в одну сторону, а потом в другую.

[Евгений Машеров]

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

[Yuri Gendelman]

(Оффтоп)

ewert в сообщении #554286 писал(а):

(кстати, меня всегда удивляло: как это на персоналках умудрились добиться практически абсолютной надёжности, в отличие от "больших" машин 70-х-80-х годов, которые постоянно сбоили; что, впрочем, смотрелось вполне естественно).

1. Это - одно из преимуществ микроэлектроники перед электроникой. Ждем наноэлектронику...
2. Моей Тойоте 9 лет, но я по-прежнему открываю капот реже, чам раз в год.