О машинной арифметике (комментарий к удаленной ветке)

← →
Юрий Зотов © (2010-10-18 11:13) [0]

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

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

> 0x00FF00 © (18.10.10 03:35) [9]

Тут не все так просто, есть подводный камень. Конкретно в ЭТОЙ задаче он вряд ли есть, но при достаточно большом количестве членов ряда проблема возникнет обязательно.

Дело в том, что ряд знакопеременный и убывающий (поскольку |x|<1). На какой-то итерации происходит сложение SUMновое = SUMстарое + Z (где Z - очередной член ряда) и оказывается, что Sстарое намного больше Z - настолько, что при приведении порядка Z просто "исчезает" (происходит переполнение разрядной сетки). Начиная с этой итерации, SUMновое всегда будет равно SUMстарое, поэтому заданная погрешность не будет достигнута никогда и цикл, соответственно, становится бесконечным.

Машинная арифметика, однако. Существует так называемое "машинное эпсилон" (число E, при котором 1+E=1).

Для обхода этой проблемы существуют специальные алгоритмы. Например, если сделать такую замену переменной, при которой ряд превратится в возрастающий (скажем, Y=1/X), то проблема либо исчезает, либо, по крайней мере, существенно увеличивается номер итерации, на которой она возникает. Еще лучше будет, если накапливать суммы отрицательных и положительных членов ряда раздельно.

Литература:
Д. Мак-Кракен, У. Дорн. "Численные методы и программирование на Фортране".

http://www.google.ru/search?q=%D0%9C%D0%B0%D0%BA-%D0%9A%D1%80%D0%B0%D0%BA%D0%B5%D0%BD&rls=com.microsoft:ru:IE-SearchBox&ie=UTF-8&oe=UTF-8&sourceid=ie7&rlz=1I7GZHZ&redir_esc=&ei=E--7TNW7L4eaOpXYsMQM

PS
Естественно, слово "Фортран" не должно вводить в заблуждение - это проблема общая.

← →
palva © (2010-10-18 14:22) [1]

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

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

← →
0x00FF00 © (2010-10-18 14:33) [2]

> Но, конечно, наиболее эффективно проанализировать ряд математическими методами.

Дык, что я в самом начале и предложил.
Он довольно легко суммировался.

> Юрий Зотов © (18.10.10 11:13)

Благодарю за фундаментальное разъяснение!

Только, боюсь, автору удалённой ветки всё это было гораздо важнее, чем мне.
Есть ли какой-нибудь способ переименовать текущую?

← →
Kerk © (2010-10-18 14:34) [3]

Дискретная математика, 3й курс :)

Или даже второй

> Дискретная математика, 3й курс :)

Здравый смысл, 4-й класс.

О машинной арифметике (комментарий к удаленной ветке) Найти похожие ветки