Текущая плавающая точка (ANSI C float, double) позволяет представить аппроксимацию действительного числа.
Есть ли способ представить реальные цифры без ошибок ?
Вот идея, которая у меня была, но она не идеальна.
Например, 1/3 - это 0,33333333 ... (основание 10) или o.01010101 ... (основание 2), но также 0,1 (основание 3).
Это хорошая идея для реализации этой "структуры":
base, mantissa, exponent
поэтому 1/3 может быть 3 ^ -1
{[11] = base 3, [1.0] mantissa, [-1] exponent}
Есть еще идеи?
Ответы:
Все зависит от того, что вы хотите сделать.
Например, то, что вы показываете, является отличным способом представления рациональных чисел. Но это все еще не может представлять что-то вроде или идеально.π e
Фактически, многие языки, такие как Haskell и Scheme, имеют встроенную поддержку рациональных чисел, сохраняя их в форме где - целые числа.ab a,b
Основная причина, по которой они не используются широко, - это производительность. Числа с плавающей точкой немного неточны, но их операции реализованы аппаратно. Предлагаемая вами система обеспечивает большую точность, но требует выполнения нескольких шагов, в отличие от одной операции, которая может быть выполнена аппаратно.
Известно, что некоторые действительные числа неисчислимы, такие как числа остановки . В отличие от , нет алгоритма перечисления его цифр, где мы можем вычислить ю цифру, если будем ждать достаточно долго.π n
Если вам нужна реальная точность для вещей, иррациональных или трансцендентных чисел, вам, вероятно, нужно использовать какую-то систему символической алгебры, а затем получить окончательный ответ в символической форме, который вы можете приблизить к любому количеству цифр. Однако из-за проблем неразрешимости, изложенных выше, этот подход обязательно ограничен. Это все еще хорошо для таких вещей, как аппроксимирующие интегралы или бесконечные ряды.
источник
Невозможно представить все действительные числа без ошибок, если каждое число должно иметь конечное представление. Существует неисчислимо много действительных чисел, но только счетное количество конечных строк 1 и 0, которые вы могли бы использовать для их представления.
источник
Ваша идея не работает, потому что число, представленное в базе с мантиссой m и показателем степени e, является рациональным числом b ⋅ m - e , таким образом, ваше представление работает именно для рациональных чисел, а не для других. Вы не можете представлять √б м е б ⋅ м- е например.2-√
Существует целая ветвь вычислимой математики, которая имеет дело с точной реальной арифметикой. Было предложено много структур данных для представления точных действительных чисел: потоков цифр, потоков аффинных сокращений, последовательностей Коши рациональных чисел, последовательностей Коши диадических рациональных чисел, разрезов Дедекинда, последовательностей интервалов сжатия и т. Д. Существуют реализации на основе точной действительной арифметики. на этих идеях, например:
Из них iRRAM является наиболее зрелым и эффективным. Маршалл в экспериментальном проекте, в то время как третий является студенческим проектом, но также и наиболее доступным. В нем очень хорошее введение, объясняющее проблемы, связанные с вычислением реальных чисел, я настоятельно рекомендую вам взглянуть на него.
Позвольте мне сделать замечание. Кто-то возразит, что бесконечный объект не может быть представлен компьютером. В каком-то смысле это правда, а в другом - нет. Нам никогда не нужно представлять целое действительное число, нам нужно только конечное приближениена каждом этапе расчета. Таким образом, нам нужно только представление, которое может представлять реальное с точностью до заданной точности. Конечно, когда у нас заканчивается компьютерная память, у нас заканчивается компьютерная память, но это ограничение компьютера, а не самого представления. Эта ситуация не отличается от многих других в программировании. Например, люди используют целые числа в Python и считают их «произвольно большими», хотя, конечно, они не могут превышать размер доступной памяти. Иногда бесконечность является полезным приближением для очень большого конечного числа.
Кроме того, я часто слышу утверждение, что компьютеры могут иметь дело только с вычислимыми действительными числами. Это упускает два важных момента. Во-первых, компьютеры имеют доступ к данным из внешнего мира, поэтому мы также должны были бы сделать (не поддающееся проверке) предположение о том, что внешний мир также вычислим. Во-вторых, нам нужно различать, что может вычислять компьютер, и что он может представлять. Например, если мы выберем потоки цифр в качестве представления действительных значений, то вполне возможно представить невычислимое действительное число: если бы кто-то дал его нам, мы бы знали, как его представить. Но если мы решим представлять реалы как части исходного кода, которые вычисляют цифры, то мы, очевидно, не сможем представлять невычислимые реалы.
В любом случае эту тему лучше всего заняться дальнейшим чтением.
источник
Существует много эффективных реализаций Rational Number, но одна из них, которая была предложена много раз и может даже хорошо обрабатывать некоторые иррациональные числа, - это Continued Fractions .
Цитата из продолжения фракций Даррена Коллинза :
Цитата из Mathworld - периодические дроби
т.е. все корни могут быть выражены как периодические непрерывные дроби.
Существует также Точная Продолженная Фракция для π, которая удивила меня, пока @AndrejBauer не указал, что на самом деле это не так.
источник
В комментариях есть ряд «точных реальных» предложений (например, непрерывные дроби, линейные дробные преобразования и т. Д.). Типичный улов в том, что, хотя вы можете вычислить ответы по формуле, равенство часто неразрешимо.
Однако, если вы просто заинтересованы в алгебраических числах, то вам повезло: теория реальных замкнутых полей полна, минимальна и разрешима. Это было доказано Тарским в 1948 году.
Но тут есть подвох. Вы не хотите использовать алгоритм Тарского, так как он находится в классе сложности NELELEMENTARY, который настолько непрактичен, насколько непрактичны алгоритмы. Существуют более современные методы, которые сводят сложность к DEXP, который является лучшим из известных нам в настоящее время.
Обратите внимание, что проблема NP-трудна, потому что она включает SAT. Тем не менее, неизвестно (или не считается) быть в NP.
РЕДАКТИРОВАТЬ Я собираюсь попытаться объяснить это немного больше.
Основой для понимания всего этого является проблема решения, известная как Теория удовлетворенности по модулю, или SMT для краткости. По сути, мы хотим решить SAT для теории, построенной на основе классической логики.
Итак, мы начнем с классической логики первого порядка с теста на равенство. Какие функциональные символы мы хотим включить и каковы их аксиомы, определяют, является ли теория разрешимой.
Есть много интересных теорий, выраженных в рамках SMT. Например, существуют теории структур данных (например, списки, двоичные деревья и т. Д.), Которые используются для доказательства правильности программ, и теория евклидовой геометрии. Но для нашей цели мы смотрим на теории разных видов чисел.
Пресбургерская арифметика - это теория натуральных чисел с сложением. Эта теория разрешима.
Арифметика Пеано - это теория натуральных чисел с сложением и умножением. Эта теория не является разрешимой, как это доказал Гедель.
Арифметика Тарского - это теория действительных чисел со всеми полевыми операциями (сложение, вычитание, умножение и деление). Интересно, что эта теория разрешима. Это был очень нелогичный результат в то время. Вы можете предположить, что, поскольку это «надмножество» натуральных чисел, это «сложнее», но это не так; например, сравнивать линейное программирование для рациональных чисел с линейным программированием для целых чисел.
Может показаться неочевидным, что удовлетворение - это все, что вам нужно, но это так. Например, если вы хотите проверить, равен ли положительный квадратный корень из 2 реальному кубическому корню из 3, вы можете выразить это как проблему выполнимости:
Альфред Тарский (1948) . Метод решения элементарной алгебры и геометрии .
источник
Можно точно представить очень большой класс чисел, называемых алгебраическими числами , рассматривая их как корни полиномов.
источник
источник
Вы не можете представить все действительные числа в компьютере, но вы можете представить многие. Вы можете использовать дроби, которые будут представлять больше чисел, чем числа с плавающей запятой. Вы также можете сделать более сложные вещи, такие как представление чисел как корня некоторого многочлена с приближением, которое при использовании метода ньютонов будет сходиться к числу.
источник
Можно точно представить любое число, где входные данные представимы, сохраняя их как строку операций, так что, например, вы сохраняете
1/3
как1 divided by 3
, обрабатывая отмену операций, вы можете упростить следующую операцию, чтобы получить точный ответ(1/3) * 3
. Это также может справиться с ситуациями, когда вы знаете иррациональные числа, напримерπ
, сохраняя их в своих вычислениях.Тем не менее, он требует увеличения объема памяти для каждого числа и - при условии, что ваш упрощатель не совершенен - возможно, потребуется постоянно увеличивающийся объем для значений, над которыми вы много работаете.
источник