Арифметика произвольной точности

редактировать
вычисления, где точность чисел ограничена только памятью компьютера

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

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

Произвольная точность используется в приложениях, где скорость арифметики не является ограничивающим фактором или где требуются точные результаты с очень большими числами. Его не следует путать с символическим вычислением, предоставляемым многими системами компьютерной алгебры, которые представляют числа с помощью таких выражений, как π · sin (2), и, таким образом, могут представлять любое вычислимое число с бесконечной точностью.

Содержание

  • 1 Приложения
  • 2 Проблемы реализации
  • 3 Предустановленная точность
  • 4 Пример
  • 5 История
  • 6 Программные библиотеки
  • 7 См. Также
  • 8 Ссылки
  • 9 Внешние ссылки

Приложения

Распространенным приложением является криптография с открытым ключом, алгоритмы которой обычно используют арифметику с целыми числами, состоящими из сотен цифр. Другой - в ситуациях, когда искусственные ограничения и переполнения неуместны. Это также полезно для проверки результатов вычислений с фиксированной точностью и для определения оптимальных или почти оптимальных значений коэффициентов, необходимых в формулах, например √⅓, которое появляется в гауссовском интегрировании.

Арифметика произвольной точности также используется для вычисления фундаментальных математических констант, таких как π, до миллионов или более цифр, а также для анализа свойств цепочек цифр или, в более общем смысле, для исследования точного поведения таких функций, как Дзета-функция Римана, где некоторые вопросы трудно исследовать с помощью аналитических методов. Другой пример - рендеринг фрактальных изображений с чрезвычайно большим увеличением, таких как те, что находятся в наборе Мандельброта.

Арифметика произвольной точности также может использоваться, чтобы избежать переполнения, что является неотъемлемым ограничением арифметики с фиксированной точностью. Подобно 5-значному отображению одометра , которое меняется с 99999 на 00000, целое число с фиксированной точностью может отображать зацикливание, если числа становятся слишком большими для представления с фиксированным уровнем точности.. Некоторые процессоры вместо этого могут справляться с переполнением с помощью насыщенности, что означает, что если результат будет непредставимым, он заменяется ближайшим представимым значением. (При 16-битном беззнаковом насыщении добавление любого положительного значения к 65535 даст 65535.) Некоторые процессоры могут генерировать исключение , если арифметический результат превышает доступную точность. При необходимости исключение может быть обнаружено и восстановлено - например, операция может быть перезапущена в программном обеспечении с использованием арифметики произвольной точности.

Во многих случаях задача или программист могут гарантировать, что целочисленные значения в конкретном приложении не станут достаточно большими, чтобы вызвать переполнение. Такие гарантии могут быть основаны на прагматических ограничениях: программа посещаемости школы может иметь ограничение в 4000 учеников. Программист может спроектировать вычисления так, чтобы промежуточные результаты оставались в пределах заданных границ точности.

Некоторые языки программирования, такие как Lisp, Python, Perl, Haskell и Ruby использовать или иметь возможность использовать числа произвольной точности для всей целочисленной арифметики. Хотя это снижает производительность, это исключает возможность получения неверных результатов (или исключений) из-за простого переполнения. Это также дает возможность гарантировать, что арифметические результаты будут одинаковыми на всех машинах, независимо от размера слова конкретной машины. Исключительное использование чисел произвольной точности в языке программирования также упрощает язык, поскольку число - это число, и нет необходимости в нескольких типах для представления различных уровней точности.

Проблемы реализации

Арифметика с произвольной точностью значительно медленнее, чем арифметика с использованием чисел, которые полностью помещаются в регистры процессора, поскольку последние обычно реализуются в аппаратной арифметике, тогда как первые должны быть реализованы в программном обеспечении. Даже если на компьютере не хватает оборудования для определенных операций (таких как целочисленное деление или все операции с плавающей запятой) и вместо него предоставляется программное обеспечение, он будет использовать размеры чисел, тесно связанные с доступными аппаратными регистрами: один или два только слова и определенно не N слов. Есть исключения, так как некоторые машины переменной длины слова 1950-х и 1960-х годов, в частности IBM 1620, IBM 1401 и серия Honeywell Liberator, могли манипулировать числами. связаны только доступной памятью с дополнительным битом, ограничивающим значение.

Числа могут быть сохранены в формате с фиксированной точкой или в формате с плавающей точкой как значащее, умноженное на произвольный показатель степени. Однако, поскольку деление почти сразу вводит бесконечно повторяющиеся последовательности цифр (например, 4/7 в десятичном или 1/10 в двоичном), если такая возможность возникнет, то либо представление будет усечено до некоторого удовлетворительного размера, либо рациональные числа будут используется: большое целое число для числителя и знаменателя . Но даже при разделении наибольшего общего делителя арифметика с рациональными числами может очень быстро стать громоздкой: 1/99 - 1/100 = 1/9900, и если затем добавить 1/101, результат будет 10001/999900.

Размер чисел произвольной точности ограничен на практике общим доступным хранилищем, переменными, используемыми для индексации строк цифр, и временем вычисления. 32-разрядная операционная система может ограничивать доступное хранилище до менее 4 ГБ. Язык программирования, использующий 32-битные целые числа, может индексировать только 4 ГБ. Если умножение выполняется с помощью алгоритма Θ {\ displaystyle \ Theta}\ Theta (N), потребуется порядок 10 шагов, чтобы умножить два миллиона слов числа.

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

Простейшие алгоритмы предназначены для сложения и вычитание, где просто последовательно складываются или вычитаются цифры с переносом по мере необходимости, что дает алгоритм O (N) (см. нотация большого O ).

Сравнение тоже очень простое. Сравните старшие цифры (или машинные слова), пока не найдете разницу. Сравнивать остальные цифры / слова не нужно. Наихудший случай - Θ {\ displaystyle \ Theta}\ Theta (N), но обычно это происходит намного быстрее.

Для умножения наиболее простые алгоритмы, используемые для ручного умножения чисел (как учили в начальной школе), требуют Θ {\ displaystyle \ Theta}\ Theta ( N) операций, но были разработаны алгоритмы умножения, которые достигают сложности O (N log (N) log (log (N))), например, алгоритм Шёнхаге – Штрассена, основанный на на быстрых преобразованиях Фурье, а также есть алгоритмы с несколько худшей сложностью, но иногда с лучшей производительностью в реальном мире для меньших N. Умножение Карацубы является таким алгоритмом.

Для деления см. алгоритм деления.

Список алгоритмов вместе с оценками сложности см. вычислительная сложность математических операций.

Примеры в x86, см. внешние ссылки.

Предустановленная точность

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

Пример

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

Но если требуются точные значения для больших факториалов, то требуется специальное программное обеспечение, как в следующем псевдокоде, который реализует классический алгоритм для вычисления 1, 1 × 2, 1 × 2 × 3, 1 × 2 × 3 × 4 и т. Д. Последовательные факториальные числа.

Постоянный предел = 1000; % Достаточно цифр. Постоянная база = 10; % База моделируемой арифметики. Постоянный FactorialLimit = 365; % Целевое число для решения, 365! Цифра массива [1: Предел] целого числа; % Большое количество. Целочисленный перенос, d; % Помощники при умножении. Целое последнее, i; % Указатели больших цифр числа. Текст массива [1: Ограничение] символа; % Блокнот для вывода. Константа tdigit [0: 9] символа = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9" ]; НАЧАЛО цифра: = 0; % Очистить весь массив. цифра [1]: = 1; % Большое число начинается с 1, последнее: = 1; % Его старшая цифра - номер 1. для n: = 1 до FactorialLimit do % Пошаговое производство 1 !, 2 !, 3 !, 4 ! и т.д. несут: = 0; % Начать умножение на n. для i: = 1 до последний do % Шаг по каждой цифре. d: = цифра [i] * n + перенос; % Классическое умножение. цифра [i]: = d mod База; % Младшая цифра результата. carry: = d div Base; % Переход к следующей цифре. следующий i; в то время как перенос>0% Сохранение переноса в большом количестве. if last>= Limit then croak («Переполнение!»); % Если возможно! последний: = последний + 1; % Еще одна цифра. цифра [последняя]: = нести мод База; % Размещено. carry: = carry div Base; % Перенос уменьшен. Wend % With n>Base, возможно>1 дополнительная цифра. текст: = ""; % Теперь подготовим вывод. for i: = 1 to last do % Преобразовать из двоичного в текст. текст [Предел - i + 1]: = tdigit [цифра [i]]; % Изменение порядка на обратное. следующий i; % Арабские цифры ставят младший разряд последним. Печать текста, «=», n, «!»; % Распечатайте результат! следующий n; % Переход к следующему факториалу вверх. КОНЕЦ ;

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

Второе по важности решение - выбор основания арифметики, здесь десять. Есть много соображений. Переменная блокнота d должна содержать результат однозначного умножения плюс перенос от умножения предыдущей цифры. В десятичной системе счисления шестнадцатиразрядное целое число определенно подходит, поскольку оно допускает до 32767. Однако этот пример обманывает, поскольку значение n само по себе не ограничено одной цифрой. Это приводит к тому, что метод не работает при n>3200 или около того. В более общей реализации n также будет использовать многозначное представление. Второе следствие сокращения состоит в том, что после завершения многозначного умножения последнее значение переноса может потребоваться перенести в несколько цифр более высокого порядка, а не только в одну.

Существует также проблема вывода результата в десятичном формате для человеческого понимания. Поскольку база уже равна десяти, результат может быть показан просто путем печати последовательных цифр цифры массива, но они будут отображаться с последней цифрой наивысшего порядка (так что 123 будет отображаться как «321»). Весь массив может быть напечатан в обратном порядке, но это будет представлять число с ведущими нулями («00000... 000123»), что может не приниматься во внимание, поэтому эта реализация строит представление в текстовой переменной, заполненной пробелами, а затем печатает что. Первые несколько результатов (с интервалом между каждой пятой цифрой и добавленной здесь аннотацией):

Факториальные числаДосягаемость компьютерных целых чисел
1 =1!
2 =2!
6 =3!
24 =4!
120 =5!8-бит255
720 =6!
5040 =7!
40320 =8!16-битный65535
3 62880 =9!
36 28800 =10!
399 16800 =11!
4790 01600 =12!32-битный42949 67295
62270 20800 =13!
8 71782 91200 =14!
130 76743 68000 =15!
2092 27898 88000 =16!
35568 74280 96000 =17!
6 40237 37057 28000 =18!
121 64510 04088 32000 =19!
2432 90200 81766 40000 =20!64-битный18446 74407 37095 51615
51090 94217 17094 40000 =21!
11 24000 72777 76076 80000 =22!
258 52016 73888 49766 40000 =23!
6204 48401 73323 94393 60000 =24!
1 55112 10043 33098 59840 00000 =25!
40 32914 61126 60563 55840 00000 =26!
1088 88694 50418 35216 07680 00000 =27!
30488 83446 11713 86050 15040 00000 =28!
8 84176 19937 39701 95454 36160 00000 =29!
265 25285 98121 91058 63630 84800 00000 =30!
8222 83865 41779 22817 72556 28800 00000 =31!
2 63130 83693 36935 30167 21801 21600 00000 =32!
86 83317 61881 18864 95518 19440 12800 00000 =33!
2952 32799 03960 41408 47618 60964 35200 00000 =34!128-бит3402 82366 92093 84634 63374 60743 17682 11455
1 03331 47966 38614 49296 66651 33752 32000 00000 =35!

Эта реализация могла бы более эффективно использовать встроенную арифметику компьютера. Простым расширением было бы использование базы 100 (с соответствующими изменениями в процессе преобразования для вывода) или, с достаточно широкими компьютерными переменными (такими как 32-битные целые числа), мы могли бы использовать более крупные базы, такие как 10000. Работа с основанием степени двойки ближе к встроенным в компьютер целочисленным операциям дает преимущества, хотя преобразование в десятичное основание для вывода становится более трудным. На типичных современных компьютерах сложение и умножение занимают постоянное время независимо от значений операндов (при условии, что операнды помещаются в отдельные машинные слова), поэтому есть большой выигрыш от упаковки как можно большего количества больших чисел в каждый элемент массив цифр. Компьютер может также предлагать средства для разделения продукта на цифры и переноса без необходимости выполнения двух операций mod и div, как в примере, и почти все арифметические устройства предоставляют флаг переноса , который можно использовать в нескольких -точность сложения и вычитания. Подобного рода детали необходимы программистам, занимающимся машинным кодом, и подходящая процедура bignumber на языке ассемблера может работать намного быстрее, чем результат компиляции языка высокого уровня, который не предоставляет доступа к таким средствам.

Для однозначного умножения рабочие переменные должны иметь возможность удерживать значение (основание-1) + перенос, где максимальное значение переноса равно (основание-1). Точно так же переменные, используемые для индексации массива цифр, сами ограничены по ширине. Простым способом расширения индексов было бы иметь дело с цифрами большого числа в блоках некоторого удобного размера, чтобы адресация осуществлялась через (блок i, цифра j), где i и j были бы небольшими целыми числами, или можно было бы увеличить до использование методов двойного числа для индексирования переменных. В конечном итоге объем памяти машины и время выполнения накладывают ограничения на размер проблемы.

История

Первый бизнес-компьютер IBM, IBM 702 (лампа ) середины 1950-х годов, полностью реализовал целочисленную арифметику аппаратно на цепочках цифр любой длины от 1 до 511 цифр. Самая ранняя широко распространенная программная реализация арифметики произвольной точности была, вероятно, в Maclisp. Позже, примерно в 1980 году, операционные системы VAX / VMS и VM / CMS предлагали большие возможности как набор string функции в одном случае и на языках EXEC 2 и REXX в другом.

Ранняя широко распространенная реализация была доступна через IBM 1620 1959–1970 гг. Модель 1620 была десятичной машиной, которая использовала дискретные транзисторы, но при этом имела оборудование (которое использовало таблицы поиска ) для выполнения целочисленных арифметических операций над строками цифр длиной от двух до любой доступной памяти. Для арифметики с плавающей запятой мантисса ограничивалась сотней или меньше цифр, а показатель степени ограничивался только двумя цифрами. Самый большой из представленных модулей памяти предлагал 60 000 цифр, однако компиляторы Fortran для 1620 остановились на фиксированных размерах, таких как 10, хотя его можно было указать на карте управления, если значение по умолчанию было неудовлетворительным.

Программные библиотеки

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

В разных библиотеках есть разные способы представления чисел произвольной точности, некоторые библиотеки работают только с целыми числами, другие хранят числа с плавающей запятой в различных основаниях (десятичные или двоичные степени). Вместо того, чтобы представлять число как отдельное значение, некоторые хранят числа как пару числитель / знаменатель (rationals ), а некоторые могут полностью представлять вычислимые числа, хотя только до некоторого предела хранения. По сути, машины Тьюринга не могут представлять все действительные числа, поскольку мощность ℝ превышает мощность ℤ.

См. Также

Литература

Внешние ссылки

Последняя правка сделана 2021-06-11 23:41:32
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте