2Сумма

Эта статья - сирота , так как никакие другие статьи не ссылаются на нее . Пожалуйста, введите ссылки на эту страницу из связанных статей ; попробуйте инструмент "Найти ссылку", чтобы получить предложения. ( Ноябрь 2020 г. )

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

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

Алгоритм [ править ]

Учитывая два числа с плавающей запятой и , 2Sum вычисляет сумму с плавающей запятой и ошибку с плавающей запятой, так что . Ошибка сама по себе является числом с плавающей запятой. ${\ displaystyle a}$ ${\ displaystyle b}$ $s:=\operatorname {fl} (a+b)$ $t:=a+b-\operatorname {fl} (a+b)$ $s+t=a+b$ $t$

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

a,b

Сумма выходов и ошибка

s=\operatorname {fl} (a+b)

t=a+b-\operatorname {fl} (a+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 , и при условии , что сумма не переполнение и, если это недостаточное, недостаточным постепенно , это может быть доказано , что . ^[1]^[6]^[2] $s+t=a+b$

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

Входы Radix-2 или числа с плавающей точкой Radix-3 и , из которых по крайней мере один равен нулю, или которые соответственно имеют нормированные показатели

a

b

e_{a}\geq e_{b}

Сумма выходов и ошибка

s=\operatorname {fl} (a+b)

t=a+b-\operatorname {fl} (a+b)

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

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

См. Также [ править ]

Ссылки [ править ]

^ ^a ^b ^c d e f Мюллер, Жан-Мишель; Бруни, Николас; де Динешен, Флоран; Жаннерод, Клод-Пьер; Джолдес, Миоара; Лефевр, Винсент; Мелькионд, Гийом; Revol, Натали; Торрес, Серж (2018). Справочник по арифметике с плавающей точкой (2-е изд.). Чам, Швейцария: Birkhäuser. С. 104–111. DOI : 10.1007 / 978-3-319-76526-6 . ISBN 978-3-319-76525-9.
^ a b c Мёллер, Оле (март 1965 г.). «Квази-двойная точность при сложении с плавающей запятой». BIT Численная математика . 5 : 37–50. DOI : 10.1007 / BF01975722 . S2CID 119991676 .
Перейти ↑ Kahan, W. (январь 1965). «Дальнейшие замечания по уменьшению ошибок усечения». Коммуникации ACM . Ассоциация вычислительной техники. 8 (1): 40. DOI : 10,1145 / 363707,363723 . ISSN 0001-0782 . S2CID 22584810 .
^ a b Деккер, TJ (июнь 1971 г.). «Метод с плавающей запятой для увеличения доступной точности» . Numerische Mathematik . 18 (3): 224–242. DOI : 10.1007 / BF01397083 . S2CID 63218464 .
^ Шевчук, Джонатан Ричард (октябрь 1997 г.). «Адаптивная точная арифметика с плавающей запятой и быстрые надежные геометрические предикаты» . Дискретная и вычислительная геометрия . 18 (3): 305–363. DOI : 10.1007 / PL00009321 .
^ a b Кнут, Дональд Э. (1998). Искусство компьютерного программирования, Том II: получисловые алгоритмы (3-е изд.). Аддисон-Уэсли. п. 236. ISBN. 978-0-201-89684-8.
^ Стербенз, Пэт Х. (1974). Вычисление с плавающей точкой . Энглвуд Клиффс, Нью-Джерси, США: Прентис-Холл. С. 138–143. ISBN 0-13-322495-3.

[handbook-1] Мюллер, Жан-Мишель; Бруни, Николас; де Динешен, Флоран; Жаннерод, Клод-Пьер; Джолдес, Миоара; Лефевр, Винсент; Мелькионд, Гийом; Revol, Натали; Торрес, Серж (2018). Справочник по арифметике с плавающей точкой (2-е изд.). Чам, Швейцария: Birkhäuser. С. 104–111. DOI : 10.1007 / 978-3-319-76526-6 . ISBN 978-3-319-76525-9.

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

[kahan-3] Перейти ↑ Kahan, W. (январь 1965). «Дальнейшие замечания по уменьшению ошибок усечения». Коммуникации ACM . Ассоциация вычислительной техники. 8 (1): 40. DOI : 10,1145 / 363707,363723 . ISSN 0001-0782 . S2CID 22584810 .

[dekker-4] Деккер, TJ (июнь 1971 г.). «Метод с плавающей запятой для увеличения доступной точности» . Numerische Mathematik . 18 (3): 224–242. DOI : 10.1007 / BF01397083 . S2CID 63218464 .

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

[knuth-taocp-vol2-6] Кнут, Дональд Э. (1998). Искусство компьютерного программирования, Том II: получисловые алгоритмы (3-е изд.). Аддисон-Уэсли. п. 236. ISBN. 978-0-201-89684-8.

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

[1]