#сложение — Public Fediverse posts

[Перевод] Как ускорить сложение и вычитание при помощи 2^51

Помните, как долго выполняется сложение на бумаге? ¹¹ ¹ 6876 + 3406 ------ 10282 Начиная с единиц, мы складываем 6 + 6 = 12, записываем 2 и переносим 1. Затем пошагово двигаемся влево, пока складываемые разряды не закончатся. При реализации сложения больших чисел (например, от 2 64 и выше) обычно пишут код, похожий на этот алгоритм. Любопытно здесь то, что существует простой трюк, позволяющий существенно ускорить этот процесс на современных CPU. Но сначала я задам вопрос: почему сложение столбиком мы начинаем с самого младшего разряда? Почему бы не начать слева? Дело, разумеется, в переносе. Мы не можем точно знать, каким будет текущий разряд числа, пока не выполним все сложения справа от этого разряда.

https://habr.com/ru/articles/915800/

#сложение #перенос #оптимизация_производительности #вычитание

[Перевод] Укрощаем суммы с плавающей запятой

Допустим, у нас есть массив чисел с плавающей запятой, и мы хотим их суммировать. Можно наивно подумать, что их достаточно просто сложить, например, на Rust. Однако это запросто может привести к произвольно большой накопленной погрешности. Давайте проверим: naive_sum(&vec![1.0; 1_000_000]) = 1000000.0 naive_sum(&vec![1.0; 10_000_000]) = 10000000.0 naive_sum(&vec![1.0; 100_000_000]) = 16777216.0 naive_sum(&vec![1.0; 1_000_000_000]) = 16777216.0 Ой-ёй… Что произошло? Проблема в том .что следующее 32-битное число с плавающей запятой после 16777216 — это 16777218 . Так что при вычислении 16777216 + 1 , значение округляется до ближайшего числа с плавающей запятой, имеющей чётную мантиссу, то есть снова до 16777216 . Мы зашли в тупик. К счастью, есть более совершенные способы суммирования массива.

https://habr.com/ru/articles/819135/

#числа_с_плавающей_запятой #сложение #оптимизации #округление #погрешности_округления