Как реализованы математические библиотеки с бесконечной точностью?

Итак, я знаю о точности с плавающей запятой (и о том, как такие вещи, как 1.1, не могут быть выражены точно в двоичном виде), и все это, но мне интересно: как тогда библиотеки, связанные с математикой, реализуют бесконечную точность? Другими словами, как бы вы точно представляли, например, 1.1 в двоичном формате? Просто краткое описание было бы замечательным, я сам смогу выяснить детали. Благодарю. :)Как реализованы математические библиотеки с бесконечной точностью?

источник

2009-06-17 Sasha Chedygov

Нет библиотек бесконечной точности, но существуют библиотеки точности точности. Подробнее о том, как они реализованы, читайте около documentation :-)

Для представления 1.1 точно в двоичном формате с плавающей запятой нельзя использовать, как вы правильно указываете. Его можно представить, если вы храните интегральную часть (1) в виде целого числа, а дробную часть (.1) - как еще одно целое, а затем вам нужно создать логику для работы с этими структурами. В качестве альтернативы он может храниться как фракция (11/10) как с знаменателем, так и с числителем, хранящимся в виде целых чисел.

источник

2009-06-17 03:47:25

Ах, вот что я искал. Благодарю. :) Еще одна вещь: насколько эффективна (или неэффективная) такая библиотека «фракций» сравниваться с использованием только плавающих? –

Фракции не так уж плохи, но они по-прежнему ограничены в точности по типу числителя и знаменателя. Если вы попытаетесь сделать большие десятичные знаки, тогда код слоя для обработки фракций (GCD, LCF и т. Д.), Помимо этого, вы можете просто использовать для поплавков с большой точностью. И фракции все еще имеют проблему неспособности представлять трансценденталы. – paxdiablo

Они не так эффективны, как плавающие при условии, что ваш процессор был разработан для работы с поплавками. CPU может просто умножить два числа с плавающей запятой, тогда как для умножения двух фракций придется делать несколько умножений и, возможно, GCD. –

Математические библиотеки с бесконечными точностью не реализованы. Это невозможно. Число 1/3 не может быть представлено в конечном числе бит, кроме как в виде дроби. Трансцендентные числа, такие как pi и e, не могут быть представлены полностью никоим образом.

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

источник

2009-06-17 03:41:54 paxdiablo

Извините, я не знаю терминологию, я просто использовал «бесконечную точность», потому что это то, что кажется. –

Итак, все, что они делают, просто добавляет больше точности? Это оно? Бросить в него больше бит? –

По определению вы не можете сказать, что бесконечная точность не реализована; вы не можете завершить оценку! :-) –

-1

Хотя Pax здесь совершенно прав, когда мы говорим о плавающих точках и номерах, я считаю, что есть решение, но оно очень неэффективно.
Вы можете использовать строку для представления вашего номера, строки не имеют точности потерь.
Всякий раз, когда у вас есть число «0,0001» + «0,1», вы перебираете обе строки и конвертируете только текущую позицию в int.
Шаг 1:
0 + 0 = 0 -> преобразовать в строку и присвоить данные [0].
Шаг 2:
0 + 1 = 1 -> преобразовать в строку и присвоить данные [1].
Шаг 3:
iter> "0.1" .lenght() -> stop.

источник

2009-06-17 03:48:59

Вы по-прежнему теряете точность (хотя это займет больше времени) из-за ограниченной доступной памяти. (1/3) * 3, даже со строками, приведет к точной потере. Вы можете также распределить эту «ограниченную» память на значение с плавающей запятой IEE754 2G (12gigabit). Вычисления будут быстрее, и вы получите лучшую точность (хотя вы могли бы удерживать только один поплавок в памяти за раз :-) – paxdiablo

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

(1/3) * 3 не нужно терять точность, если 1/3 хранится как числитель и знаменатель (что и делают некоторые библиотеки). То, что у вас есть (1/3) * (3/1), и библиотека умножает числители вместе и знаменатели вместе и получает 3/3, что соответствует 1. Паренс не имеет значения, потому что пара {числитель, знаменатель} считается числом. Конечно, в конце концов вам нужно решить что-то вроде этого: (1/3) +1. И в этот момент вы должны принять решение о том, сколько цифр нужно держать. – Nosredna

Существуют определенные геометрические алгоритмы, которые зависят от точной арифметики, поэтому, если вы посмотрите в библиотеке CGAL, вы найдете множество точных числовых типов, которые «закрыты» под различными операциями. То есть, нет способа использовать поддерживаемые операции для получения результата, который не может быть представлен точно.

Некоторые примеры:

Целые замкнуты относительно сложения и умножения.
Рациональность также закрыта под делением, за исключением специального случая для нуля. Может быть представлено в виде пары целых чисел. См. Также rational number functions in GMP. например, 1.1 = 11/10, могут быть представлены как (11, 10).
Тип номера, который также закрыт под квадратным корнем.

источник

2009-06-17 04:44:36

Определенный диапазон целых чисел может быть представлен внутри компьютера, но не * все * из них (ограничения хранения). Мои друзья в отделах математики и физики в местном Uni меня оживили, если бы я сделал такое заявление :-) – paxdiablo

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

Это не педантично, а не все * знают, это и многие другие вопросы. SO не только для людей, которые понимают пределы машинного представления целых чисел или плавающих, это для всех людей. Ваше утверждение о том, что добавление в целые числа «не позволяет ... получить результат, который невозможно представить точно», имеет смысл, если вы укажете ограниченный диапазон целых чисел. Я не говорю, что они не работоспособны (поплавки и удваивания работоспособны для большинства целей), просто цифры, такие как квадратный корень из двух, не становятся точными, просто бросая в них конечное число цифр. – paxdiablo

Если вы на самом деле означает бесконечную точность есть два варианта:

использовать некоторую форму ленивого вычисления. Затем вы можете запросить номер для такой же точности, как вам нравится «после» выполнения вычисления (поскольку он ленив, он фактически выполняется только тогда). Недостатком является то, что это очень неэффективно. Вы можете сделать это на языке, таком как Haskell, с использованием специальной системы счисления, где наложения перекрываются, например. base 2 с цифрами -1, 0, 1. Обычное представление непригодно, потому что, скажем, 1, вам нужно бесконечную точность, чтобы решить между выводом 0 для 0.999 ... и 1 для 1.000 ...
Вычисляют символически , Представляйте целые числа, рациональности, корни и т. Д. Это необходимо, если вы хотите решить равенство, но также довольно неэффективны и ограничены специальными случаями.

источник

2009-06-17 07:02:58 starblue

Символическое вычисление может быть неэффективным для хрустания чисел, но это именно то, что делают системы компьютерной алгебры (такие как Maple, Mathematica, Reduce, Axiom, ...). –

Даже в символическом случае равенство вполне может быть неразрешимым, в зависимости от того, сколько цифр вы можете представить. –

Вы также можете представлять числа в десятичной системе и выполнять десятичную арифметику. Основное представление является двоичным в том смысле, что каждая цифра представлена двоичным кодом. Каждая цифра - будь то слева или справа от десятичной точки - рассматривается как целое число. Затем выполняется арифметика `` вручную '', цифра-цифра.

Одним из примеров десятичной библиотеки является BCMath в PHP.

источник

2009-06-17 13:50:07

Как реализованы математические библиотеки с бесконечной точностью?

ответ

Смежные вопросы