Популярная задача двух сумм с плавающей точкой

Question

Существует популярная проблема алгоритма, известная как Two Sum. Для тех, кто не знает об этом, вот краткое описание. Вам дан массив чисел с n элементами и целевым числом. Вы должны найти 2 числа в массиве так, чтобы они складывались в целевое число.

Эта проблема может быть найдена в Leetcode.

https://leetcode.com/problems/two-sum/

числа в массиве обычно задаются как целые числа. Вот мой вопрос. Как можно было бы решить эту проблему, если вместо этого массив был заполнен числами с плавающей запятой? Эта проблема более сложна из-за ошибок округления.

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

Answer 1

Нахождение суммы с плавающей точкой

Если проблема состоит в том, чтобы найти два элемента массива x и y , чтобы их сумма была целевым числом z при добавлении с арифметикой с плавающей точкой проблемы округления с плавающей точкой в ​​значительной степени не имеют значения.

Алгоритм задачи с двумя суммами:

1. Сортировка элементов. (Чтобы запомнить их исходные индексы в массиве, свяжите элементы с их индексами и сохраните эти ассоциации при сортировке.)
2. Установите L для указания на самый низкий элемент и H для указания на самый высокий элемент.
3. Хотя L раньше, чем H:
   • Если сумма *L (число, на которое указывает L) и *H равна z ,стоп. Желаемыми элементами являются *L и *H.
   • Если сумма меньше z , заранее L.
   • Если сумма больше z , уменьшение H.
4. Стоп. Решения не существует.

Округление с плавающей запятой не является проблемой, поскольку сложение с плавающей запятой (слабо) монотонно: если сумма с плавающей запятой равна x ₀ <<em> x ₁ , тогда сумма с плавающей точкой x ₀ и y равнаменьше или равно сумме с плавающей запятой x _{= 1} и y . Это означает, что тестовая сумма *L и *H в алгоритме всегда правильно указывает, нужно ли корректировать L или H, чтобы продолжить поиск - если тестовая сумма слишком мала, то нам нужно большее число,поэтому L должен быть продвинутым. Аналогично, если сумма теста слишком велика, H должно быть уменьшено. Ни одно решение не может быть пропущено таким образом.

Поиск суммы действительных чисел

Если проблема состоит в том, чтобы найти два элемента массива x и y , такиечто если сумма равна целевому числу z при добавлении с арифметикой действительных чисел, то приведенного выше алгоритма достаточно с простой модификацией теста.

Замените шаг 3. выше на:

• Оцените s = *L + *H; z = s - *L; t = *H - z; с помощью арифметики с плавающей точкой, используя округление до ближайшего. Тогда в арифметике действительных чисел s + t точно равно *L + *H. ¹ s содержит наиболее значительную часть суммы (ближайшее значение, представимое в плавающей-точка), а t содержит ошибку или отклонение s от суммы действительных чисел *L и *H. Если s равно z и t равно нулю, остановитесь. Желаемыми элементами являются *L и *H.
• Если s <<em> z или s = z и t <0, заранее<code>L.
• В противном случае уменьшите H.

Сноска

¹ Мюллер и др., Справочник по плаванию-Точечная арифметика , 2010, теорема 4, стр. 126-129.