Как в вычислениях указываются действительные числа?

27

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

cc.complexity-theory computability na.numerical-analysis computing-over-reals computable-analysis Филип Уайт
источник

1

Вы можете найти обсуждение здесь интересным: en.wikipedia.org/wiki/Computable_number

Джозеф Малкевич

Кто-то должен собрать эти документы в бесплатную скачиваемую электронную книгу.

Dilawar

34

Я не согласен с вашим принятым ответом Каве. Для линейного программирования и равновесий по Нэшу плавающая точка может быть приемлемой. Но числа с плавающей точкой и вычислительная геометрия очень плохо сочетаются: ошибка округления делает недействительными комбинаторные предположения алгоритмов, что часто приводит к их краху. Более конкретно, многие алгоритмы вычислительной геометрии зависят от примитивных тестов, которые проверяют, является ли данное значение положительным, отрицательным или нулевым. Если это значение очень близко к нулю и округление с плавающей точкой приводит к тому, что оно имеет неправильный знак, могут произойти плохие вещи.

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

В большинстве теоретических работ по вычислительной геометрии эта проблема обходит стороной, предполагая, что входные данные являются точными действительными числами и что примитивы являются точными проверками знаков корней полиномов низкой степени во входных значениях. Но если вы реализуете геометрические алгоритмы, то все это становится очень важным.

Дэвид Эппштейн
источник

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

Филипп Уайт

Я не говорил, что это хорошая модель для компьютерной графики, я хотел сказать, что даже когда авторы говорят, что входные данные являются действительными числами, они не являются действительными числами . Я согласен с вами, что я не должен был включать CG среди других. Я прочитал очень небольшое количество работ по компьютерной графике. Является ли модель BSS хорошо зарекомендовавшей себя в теоретических работах по компьютерной графике?

Каве

1

Простите за мое невежество, но что означает BSS?

Филипп Уайт

1

Модель BSS является теоретической моделью, которая предполагает наличие произвольных действительных чисел. То, что сделано в CG, включает в себя фактические реализации модели, которая обычно ограничена алгебраическими числами. Также реализации CG далеки от удельной стоимости за операцию. Так что это не одно и то же. См., Например, модель действительного числа LEDA, citeseerx.ist.psu.edu/viewdoc/…

Дэвид Эппштейн

10

S

$S$

T

$T$

\sum_{s \in S} \sqrt{s} > \sum_{t \in T} \sqrt{t}

$\sum_{s\in S} \sqrt{s} > \sum_{t\in T}\sqrt{t}$

15

Вы также можете взглянуть на выступление Андрея Бауэра « Роль области интервалов в современной точной реальной арифметике» , в котором рассматриваются некоторые из различных подходов к определению вычислений над действительными числами как в теории, так и на практике.

Ноам Цайлбергер
источник

8

Это не прямой ответ на ваш вопрос, а скорее ответ Рафаэлю . Недавно была проведена большая работа по определению вычислений действительных чисел с использованием коиндукции. Вот несколько статей на эту тему.

Коиндукция для точного вычисления действительных чисел , Ульрих Бергер и Ти Хоу: ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ, том 43, номера 3-4, 394-409, DOI: 10.1007 / s00224-007-9017-6
Коиндуктивное формальное рассуждение в точной действительной арифметике , Милад Никки, Логические методы в информатике, 4 (3: 6): 1–40, 2008.
Исчисление в коиндуктивной форме , Душко Павлович и Мартин Эскардо, LICS 1998.

Они вряд ли охватывают весь спектр вычислений реальных чисел, но в настоящее время достигнут прогресс в устранении различных проблем.

Дэйв Кларк
источник

1

R

$\mathbb{R}$

Хорошая точка зрения. Я не уверен, каковы ограничения коиндуктивного подхода. Подход находится в зачаточном состоянии.

Дэйв Кларк

7

Вычислительная сложность вычислений над действительными числами рассматривается Блумом, Кукером, Шубом и Смейлом . Вот частичное описание книги:

Классическая теория вычислений берет свое начало в работах Геделя, Тьюринга, Черча и Клини и была чрезвычайно успешной основой для теоретической информатики. Тезис этой книги, однако, состоит в том, что она обеспечивает неадекватную основу для современных научных вычислений, где большинство алгоритмов являются алгоритмами действительных чисел. Цель этой книги - разработать формальную теорию вычислений, которая объединяет основные темы классической теории и которая более непосредственно применима к задачам математики, численного анализа и научных вычислений. Попутно авторы рассматривают такие фундаментальные проблемы, как: разрешимо ли множество Мандельброта? Для простых квадратичных карт Джулия установила остановочный набор? В чем реальная сложность Ньютона? с метод? Существует ли алгоритм для решения задачи о ранце в плойномиальном количестве шагов? Hilbert Nullstellensatz неразрешимый? Трудно ли найти реальный ноль полинома четвертой степени? Возможно ли линейное программирование по реалам?

Вы можете найти обзор этой книги в ACM SIGACT News .

М.С. Дусти
источник

Эта книга выглядит очень интересно, спасибо.

Филипп Уайт

Добро пожаловать.

MS Dousti 9.10.10

5

Стоит отметить, что модель вычисления BSS по реалам противоречива, по причинам, очень похожим на то, на что ссылался Дэвид Эппштейн в комментарии выше. Например: аксиома BSS, вычисляющая, занимает ли x <y один временной шаг, для произвольных вещественных чисел x и y. Напротив, подходы, такие как Эффективность второго типа (TTE), определяют машины, которые принимают в качестве входных приближений к действительным значениям и выводят вычислимые приближения для функций по действительным значениям. Чем больше времени проходит, тем лучше могут стать приближения входа и выхода. Такой подход кажется мне более реалистичным.

Аарон Стерлинг

@ Аарон Стерлинг: знаете ли вы хороший справочник по эффективности второго типа?

Джошуа Грохов

3

@ Джошуа Грохов: Извините, я не дошел до этого раньше. Книга, на которую ссылается Каве, - «Нильсен и Чуанг» TTE. Тем не менее, он настолько насыщен нотацией, что казался бы тайным для обычного читателя. Вместо этого я бы предложил следующие учебные слайды Vasco Brattka: cca-net.de/vasco/cca/tutorial.pdf

Аарон Стерлинг,

7

Отредактировано / исправлено на основе комментариев

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

С другой стороны, если статья посвящена вычислимости и сложности в анализе , то они не используют обычную модель вычислений, и существуют различные несовместимые модели вычислений / сложности над действительными числами.

Если в статье не указана модель вычисления по действительным числам, можно смело предположить, что это первый случай, то есть это просто рациональные числа.

Вычислительная геометрия отличается. В большинстве работ в CG, если авторы не указывают, что это за модель, в отношении которой обсуждается правильность и сложность алгоритма, можно предположить, что это модель BSS (она же настоящая RAM).

Модель не является реалистичной и, следовательно, реализация не является прямой. (Это одна из причин того, что некоторые люди в CCA предпочитают теоретические модели Ко-Фридмана / TTE / Domain , но проблема этих моделей заключается в том, что они не так быстры, как вычисления с плавающей точкой на практике.) Правильность и сложность алгоритм в модели BSS не обязательно переходит на правильность реализованного алгоритма.

Книга Вейраха содержит сравнение между различными моделями (раздел 9.8). Это только три страницы и стоит читать.

(Существует также третий способ, который может быть более подходящим для CG, вы можете взглянуть на этот документ:

Чи Яп, " Теория реальных вычислений по EGC "

где EGC - точное геометрическое вычисление .)

Кава
источник

Я думаю, что статья, в которой я в первую очередь заинтересован, определяет модель, учитывая, что она включает в себя предложение: «Теперь мы формально определим нашу модель вычислений». Эта статья называется «Нижние границы для задач удовлетворительности», и, как представляется, здесь обсуждаются линейные деревья решений и полиномы запросов. Итак, я думаю, что это ответ, который я искал там ... спасибо. Я перечитал газету и посмотрю, смогу ли я в этом разобраться.

Филипп Уайт

2

Я не согласен. Это неправильная модель для вычислительной геометрии. Смотрите мой более подробный ответ ниже.

Дэвид Эппштейн

1

@Kaveh: Я думаю, вы должны сказать, что это рациональные числа, а не числа с плавающей точкой. Точные рациональные числа легко представить с помощью конечных строк, и во многих приложениях (например, связанных с линейным программированием) промежуточные результаты также будут рациональными числами, если ваши входные данные являются рациональными числами. (Конечно, как отметил Дэвид Эппштейн, comp. Geom. Является заметным исключением в том смысле, что промежуточные результаты обычно не рациональны.)

Юкка Суомела

@Jukka: Вы правы, я заменю число с плавающей точкой на рациональное.

Каве

5

Нет. Когда я пишу «реальное число», я действительно имею в виду «реальное число», и под этим я подразумеваю действительно реальное число, действительно из действительных чисел. В самом деле. В частности, в статье, о которой говорит @Philip, я должен предположить, что алгоритмы работают для произвольного реального ввода, так что я могу применять результаты нестандартного анализа.

Джефф

3

Их нет и не может, в общем. Мы можем обрабатывать только счетное количество входов (и выходов и функций) с нашими моделями вычислений. В частности, любой вход должен быть конечным, но не все действительные числа имеют конечные представления.

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

Рафаэль
источник

Если это правда, то как LDT может иметь дело с действительными числами? Я читал кое-что о «r-Linear Decision Trees», но не совсем понял, о чем они говорили, в статье «Нижние границы для линейных задач по насыщаемости».

Филипп Уайт

Могу поспорить, что они либо не могут, либо не используют машины Тьюринга (или эквивалентные концепции). Другие ответы, которые не так строги / общие, как мои, должны пролить свет на это.

Рафаэль

Как в вычислениях указываются действительные числа?

Ответы:

Отредактировано / исправлено на основе комментариев