Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Приложения [ править ]

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

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

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

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

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

Проблемы реализации [ править ]

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

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

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

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

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

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

Для умножения самые простые алгоритмы, используемые для умножения чисел вручную (как учат в начальной школе), требуют ( N 2 ) операций, но алгоритмы умножения, которые достигают сложности 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 !, и т. Д. Carry: = 0; % Начать умножение на n.  for i: = 1 to last do  % Шаг по каждой цифре. d: = цифра [i] * n + перенос; % Классическое умножение. цифра [i]: = d mod Base; % Младшая цифра результата. carry: = d div Base; % Переход к следующей цифре.  следующий я; при переносе> 0 % Сохраните перенос в большом количестве.  если last> = Limit, то квакать ("Переполнение!"); % Если возможно! последний: = последний + 1; % Еще одна цифра. цифра [последняя]: = переносить мод Base; % Размещено. carry: = переносить div Base; % Перенос уменьшен.  Wend  % При n> Base, возможно,> 1 лишняя цифра. текст: = ""; % Теперь подготовим вывод.  for i: = 1 to last do  % Перевести из двоичного в текстовый. текст [Предел - i + 1]: = tdigit [цифра [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) 2 + перенос, где максимальное значение переноса равно (основание-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, хотя его можно было указать на карте управления, если значение по умолчанию было неудовлетворительным.

Программные библиотеки [ править ]

См. Также: Список арифметических программ произвольной точности

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ↑ Jacqui Cheng (23 мая 2007 г.). «Исследователи: взлом 307-значного ключа подвергает опасности 1024-битный RSA» .
  2. ^ "Архивная копия" . Архивировано из оригинала на 2012-04-01 . Проверено 31 марта 2012 .CS1 maint: заархивированная копия как заголовок ( ссылка ) рекомендует, чтобы важные ключи RSA составляли 2048 бит (примерно 600 цифр).
  3. ^ Лоран Фусс (2006). Integration numérique avec erreurbornée en précision armitraire. Моделирование и моделирование (Отчет) (на французском языке). Университет Анри Пуанкаре - Нэнси И.
  4. ^ RK Pathria (1962). «Статистическое исследование случайности первых 10 000 цифр числа Пи» . Математика вычислений . 16 (78): 188–197. DOI : 10.1090 / s0025-5718-1962-0144443-7 . Проверено 10 января 2014 .Цитата из этой статьи: «Такой крайний узор опасен, даже если он разбавлен одним из соседних блоков»; это была последовательность 77 двадцать восемь раз в одном блоке из тысячи цифр.
  • Кнут, Дональд (2008). Получисловые алгоритмы . Искусство программирования . 2 (3-е изд.). Эддисон-Уэсли. ISBN 978-0-201-89684-8{{несогласованные цитаты}}CS1 maint: postscript (link), Раздел 4.3.1: Классические алгоритмы

Внешние ссылки [ править ]

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