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

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

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

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

Приложения

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

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

Арифметика с произвольной точностью также может использоваться, чтобы избежать переполнения , что является неотъемлемым ограничением арифметики с фиксированной точностью. Подобно 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.

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

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

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

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

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

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

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

Примеры сборки x86 см. По внешним ссылкам .

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

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

Пример

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

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

Constant Limit = 1000;            % Sufficient digits.
Constant Base = 10;               % The base of the simulated arithmetic.
Constant FactorialLimit = 365;    % Target number to solve, 365!
Array digit[1:Limit] of integer;  % The big number.
Integer carry,d;                  % Assistants during multiplication.
Integer last,i;                   % Indices to the big number's digits.
Array text[1:Limit] of character; % Scratchpad for the output.
Constant tdigit[0:9] of character = ["0","1","2","3","4","5","6","7","8","9"];
BEGIN
 digit:=0;                        % Clear the whole array.
 digit[1]:=1;                     % The big number starts with 1,
 last:=1;                         % Its highest-order digit is number 1.
 for n:=1 to FactorialLimit do    % Step through producing 1!, 2!, 3!, 4!, etc. 
  carry:=0;                       % Start a multiply by n.
  for i:=1 to last do             % Step along every digit.
   d:=digit[i]*n + carry;         % The classic multiply.
   digit[i]:=d mod Base;          % The low-order digit of the result.
   carry:=d div Base;             % The carry to the next digit.
  next i;
  while carry > 0                 % Store the carry in the big number.            
   if last >= Limit then croak("Overflow!");  % If possible!
   last:=last + 1;                % One more digit.
   digit[last]:=carry mod Base;   % Placed.
   carry:=carry div Base;         % The carry reduced.
  Wend                            % With n > Base, maybe > 1 digit extra.
  text:=" ";                      % Now prepare the output.
  for i:=1 to last do             % Translate from binary to text.
   text[Limit - i + 1]:=tdigit[digit[i]];  % Reversing the order.
  next i;                         % Arabic numerals put the low order last.
  Print text," = ",n,"!";         % Print the result!
 next n;                          % On to the next factorial up.
END;

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

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

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

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

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

История

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

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

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

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

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

Смотрите также

• Алгоритм Карацубы
• Умножение Тоома – Кука
• Алгоритм Шёнхаге – Штрассена
• Алгоритм Фюрера
• Арифметика смешанной точности

использованная литература

• Кнут, Дональд (2008). Получисловые алгоритмы . Искусство программирования . 2 (3-е изд.). Эддисон-Уэсли. ISBN 978-0-201-89684-8{{несогласованные цитаты}}CS1 maint: postscript ( ссылка ) , Раздел 4.3.1: Классические алгоритмы

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

• В главе 9.3 книги Рэндалла Хайда «Искусство сборки » обсуждается многоточная арифметика с примерами сборки x86 .
• Задача Rosetta Code Целые числа произвольной точности Примеры из практики, в которой более 95 языков программирования вычисляют значение 5 ** 4 ** 3 ** 2 с использованием арифметики произвольной точности.