Допустим, вам нужно добавить 32-битные номера фиксированной точки, хранящиеся в огромном массиве L, и вы хотите получить наиболее точный результат результат как можно скорее. Кроме того, вам не разрешено использовать ничего, кроме L и 32-битных чисел с фиксированной точкой (т. Е. Вам не разрешено преобразовывать их в 64-разрядные). Каким будет ваш подход к получению наиболее точного результата для суммы чисел в L?Вычисление наиболее точного результата для: суммы списка нумеров с фиксированной точкой
Это будет мой текущий подход отметил в коде Sudo:
L = sort(L)
result = 0
lastMax = false -- indicates whether we've extracted the maximum from L last time
while (not empty(L)) and (result not equals +INF or -INF) do:
current = 0
if lastMax:
current = extractMin(L) -- gets and removes minimum from L
else:
current = extractMax(L) -- gets and removes maximum from L
result = safeAdd(result, current)
lastMax = not lastMax
safeAdd(a,b):
if a = +INF: return +INF
else if a = -INF: return -INF
else: return a + b
Так что я чередующихся между добавлением минимального/максимального значения из оставшегося списка L, чтобы остаться между диапазонами L. Кстати как реализовано safeAdd, показывает, что как только мы пересекли диапазоны точности (т. е. результат a+b дал +INF или -INF - так же, как это делается на C), мы больше не будем изменять результат.
Есть ли у вас предложения по улучшению подхода?
Sidenote: Если мы хотим быть очень точным: Кроме того, мы предполагаем, что + операция может дать +INF или -INF, которые могут быть представлены в виде чисел с фиксированной точкой в языке программирования. Но мы предполагаем, что значения +INF, -INF не встречаются в L. И мы игнорируем тот факт, что стандарт фиксированной точки также может иметь представление для NaN.
Рассматривали вы [Каган суммирование] (https://en.wikipedia.org/wiki/Kahan_summation_algorithm)? –
Спасибо за подсказку! Извините, но мне просто пришлось сменить вопрос с плавающей точкой на номера фиксированной точки. Так что это может быть не актуально. – ndrizza
@ndrizza Добавление с фиксированной точкой - это просто добавление целых чисел, поэтому в этой операции (то есть, это точно) не возникает ошибка, если нет переполнения, что является несколько иной проблемой, которая может быть устранена путем повторного масштабирования в зависимости от варианта использования , Обычно используемые форматы с фиксированной точкой не обеспечивают представления бесконечности. – njuffa