2Сумма

2Сумма ^[1] — это алгоритм с плавающей запятой для вычисления точной ошибки округления в операции сложения чисел с плавающей запятой.

2Sum и его вариант Fast2Sum были впервые опубликованы Оле Мёллером в 1965 году. ^[2]Fast2Sum часто неявно используется в других алгоритмах, таких как алгоритмы компенсированного суммирования ; ^[1] Алгоритм суммирования Кахана был впервые опубликован в 1965 году. ^[3] а Fast2Sum позже был исключен из него Деккером в 1971 году для арифметических алгоритмов дабл-дабл . ^[4]Названия 2Sum и Fast2Sum, судя по всему, были применены Шевчуком задним числом в 1997 году. ^[5]

Алгоритм

Учитывая два числа с плавающей запятой $a$ и $b$ , 2Sum вычисляет сумму с плавающей запятой $s:=a\oplus b$ округляется до ближайшего значения и ошибка с плавающей запятой $t:=a+b-(a\oplus b)$ так что $s+t=a+b$ , где $\oplus$ и $\ominus$ соответственно обозначают сложение и вычитание, округленное до ближайшего.Ошибка $t$ само по себе является числом с плавающей запятой.

Вводит числа с плавающей запятой

a,b

Выводит округленную сумму

s=a\oplus b

и точная ошибка

t=a+b-(a\oplus b)

$s:=a\oplus b$
$a':=s\ominus b$
$b':=s\ominus a'$
$\delta _{a}:=a\ominus a'$
$\delta _{b}:=b\ominus b'$
$t:=\delta _{a}\oplus \delta _{b}$
возвращаться $(s,t)$

При условии, что арифметика с плавающей запятой правильно округлена до ближайшего значения (с любым способом разрешения связей), как это принято по умолчанию в IEEE 754 , и при условии, что сумма не переполняется, а, если она опустошается, то опустошается постепенно , можно доказать, что $s+t=a+b$ . ^[1]^[6]^[2]

Вариант 2Sum, называемый Fast2Sum, использует только три операции с плавающей запятой для арифметики с плавающей запятой в системе счисления 2 или 3, при условии, что показатель степени $a$ не меньше показателя степени $b$ , например, когда $\left|a\right|\geq \left|b\right|$ : ^[1]^[6]^[7]^[4]

Вводит числа с плавающей запятой по основанию 2 или 3.

a

и

b

, из которых хотя бы один равен нулю или которые соответственно имеют нормированные показатели степени

e_{a}\geq e_{b}

Выводит округленную сумму

s=a\oplus b

и точная ошибка

t=a+b-(a\oplus b)

$s:=a\oplus b$
$z=s\ominus a$
$t=b\ominus z$
возвращаться $(s,t)$

Даже если условия не выполняются, 2Sum и Fast2Sum часто обеспечивают разумное приближение к ошибке, т.е. $s+t\approx a+b$ , что позволяет алгоритмам компенсированного суммирования, скалярного произведения и т. д. иметь низкую ошибку, даже если входные данные не отсортированы или режим округления необычен. ^[1]^[2]Более сложные варианты 2Sum и Fast2Sum также существуют для режимов округления, отличных от округления до ближайшего. ^[1]

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Мюллер, Жан-Мишель; Бруни, Николас; де Динешен, Флоран; Жаннерод, Клод-Пьер; Джолдес, Миоара; Лефевр, Винсент; Мелькионд, Гийом; Револь, Натали ; Торрес, Серж (2018). Справочник по арифметике с плавающей запятой (2-е изд.). Хам, Швейцария: Биркхойзер. стр. 104–111. дои : 10.1007/978-3-319-76526-6 . ISBN 978-3-319-76525-9 . Архивировано из оригинала 28 апреля 2023 г. Проверено 20 сентября 2020 г.
^ Jump up to: ^а ^б ^с Мёллер, Оле (март 1965 г.). «Квазидвойная точность при сложении с плавающей запятой». БИТ Численная математика . 5 : 37–50. дои : 10.1007/BF01975722 . S2CID 119991676 .
^ Кахан, В. (январь 1965 г.). «Дальнейшие замечания по уменьшению ошибок усечения» . Коммуникации АКМ . 8 (1). Ассоциация вычислительной техники: 40. doi : 10.1145/363707.363723 . ISSN 0001-0782 . S2CID 22584810 .
^ Jump up to: ^а ^б Деккер, Ти Джей (июнь 1971 г.). «Техника с плавающей запятой для повышения доступной точности» . Нумерическая математика . 18 (3): 224–242. дои : 10.1007/BF01397083 . S2CID 63218464 . Архивировано из оригинала 19 июля 2020 г. Проверено 24 сентября 2020 г.
^ Шевчук, Джонатан Ричард (октябрь 1997 г.). «Адаптивная точная арифметика с плавающей запятой и быстрые устойчивые геометрические предикаты» . Дискретная и вычислительная геометрия . 18 (3): 305–363. дои : 10.1007/PL00009321 .
^ Jump up to: ^а ^б Кнут, Дональд Э. (1998). Искусство компьютерного программирования, Том II: Получисловые алгоритмы (3-е изд.). Аддисон-Уэсли. п. 236. ИСБН 978-0-201-89684-8 . Архивировано из оригинала 16 июля 2017 г. Проверено 20 сентября 2020 г.
^ Стербенс, Пэт Х. (1974). Вычисление с плавающей запятой . Энглвуд Клиффс, Нью-Джерси, США: Прентис-Холл. стр. 138–143. ISBN 0-13-322495-3 .

[handbook-1] Jump up to: ^а ^б ^с ^д ^и ^ж Мюллер, Жан-Мишель; Бруни, Николас; де Динешен, Флоран; Жаннерод, Клод-Пьер; Джолдес, Миоара; Лефевр, Винсент; Мелькионд, Гийом; Револь, Натали ; Торрес, Серж (2018). Справочник по арифметике с плавающей запятой (2-е изд.). Хам, Швейцария: Биркхойзер. стр. 104–111. дои : 10.1007/978-3-319-76526-6 . ISBN 978-3-319-76525-9 . Архивировано из оригинала 28 апреля 2023 г. Проверено 20 сентября 2020 г.

[moeller-2] Jump up to: ^а ^б ^с Мёллер, Оле (март 1965 г.). «Квазидвойная точность при сложении с плавающей запятой». БИТ Численная математика . 5 : 37–50. дои : 10.1007/BF01975722 . S2CID 119991676 .

[kahan-3] Кахан, В. (январь 1965 г.). «Дальнейшие замечания по уменьшению ошибок усечения» . Коммуникации АКМ . 8 (1). Ассоциация вычислительной техники: 40. doi : 10.1145/363707.363723 . ISSN 0001-0782 . S2CID 22584810 .

[dekker-4] Jump up to: ^а ^б Деккер, Ти Джей (июнь 1971 г.). «Техника с плавающей запятой для повышения доступной точности» . Нумерическая математика . 18 (3): 224–242. дои : 10.1007/BF01397083 . S2CID 63218464 . Архивировано из оригинала 19 июля 2020 г. Проверено 24 сентября 2020 г.

[shewchuk-5] Шевчук, Джонатан Ричард (октябрь 1997 г.). «Адаптивная точная арифметика с плавающей запятой и быстрые устойчивые геометрические предикаты» . Дискретная и вычислительная геометрия . 18 (3): 305–363. дои : 10.1007/PL00009321 .

[knuth-taocp-vol2-6] Jump up to: ^а ^б Кнут, Дональд Э. (1998). Искусство компьютерного программирования, Том II: Получисловые алгоритмы (3-е изд.). Аддисон-Уэсли. п. 236. ИСБН 978-0-201-89684-8 . Архивировано из оригинала 16 июля 2017 г. Проверено 20 сентября 2020 г.

[sterbenz-7] Стербенс, Пэт Х. (1974). Вычисление с плавающей запятой . Энглвуд Клиффс, Нью-Джерси, США: Прентис-Холл. стр. 138–143. ISBN 0-13-322495-3 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]