Арифметика произвольной точности
 | Эта статья нуждается в дополнительных цитатах для проверки . ( июль 2007 г. ) |
| с плавающей запятой Форматы |
|---|
| ИЭЭЭ 754 |
|
| Другой |
| Альтернативы |
В информатике арифметика произвольной точности , также называемая арифметикой больших чисел , арифметикой множественной точности или иногда арифметикой бесконечной точности , означает, что вычисления выполняются над числами, которых цифр точность потенциально ограничена только доступной памятью хост-системы. Это контрастирует с более быстрой арифметикой с фиксированной точностью, присутствующей в большинстве аппаратных средств арифметико-логических устройств (АЛУ), которые обычно обеспечивают от 8 до 64 бит точность .
Некоторые современные языки программирования имеют встроенную поддержку больших чисел. [1] [2] [3] [4] и у других есть библиотеки для вычислений с целыми числами произвольной точности и с плавающей запятой . Вместо того, чтобы хранить значения в виде фиксированного количества бит, связанного с размером регистра процессора переменной длины , в этих реализациях обычно используются массивы цифр .
Произвольная точность используется в приложениях, где скорость арифметических вычислений не является ограничивающим фактором или где точные результаты требуются с очень большими числами. Его не следует путать с символьными вычислениями, обеспечиваемыми многими системами компьютерной алгебры , которые представляют числа с помощью таких выражений, как π ·sin(2) и, таким образом, могут представлять любое вычислимое число с бесконечной точностью.
Приложения [ править ]
Распространенным применением является криптография с открытым ключом , алгоритмы которой обычно используют арифметику с целыми числами, имеющими сотни цифр. [5] [6] Другой вариант — в ситуациях, когда искусственные ограничения и переполнения неуместны. Это также полезно для проверки результатов вычислений с фиксированной точностью и для определения оптимальных или близких к оптимальным значений коэффициентов, необходимых в формулах, например это появляется при интегрировании по Гауссу . [7]
Арифметика произвольной точности также используется для вычисления фундаментальных математических констант, таких как π, до миллионов или более цифр, а также для анализа свойств строк цифр. [8] или, в более общем смысле, для исследования точного поведения таких функций, как дзета-функция Римана , где некоторые вопросы трудно исследовать с помощью аналитических методов. Другой пример — рендеринг фрактальных изображений с чрезвычайно большим увеличением, например, найденных в множестве Мандельброта .
Арифметика произвольной точности также может использоваться, чтобы избежать переполнения , которое является неотъемлемым ограничением арифметики фиксированной точности. Подобно пятизначному дисплею одометра , который меняется от 99999 до 00000, целое число с фиксированной точностью может проявлять зацикливание, если числа становятся слишком большими для представления с фиксированным уровнем точности. Вместо этого некоторые процессоры могут справиться с переполнением по насыщению , что означает, что если результат будет непредставимым, он заменяется ближайшим представимым значением. (При 16-битном беззнаковом насыщении добавление любой положительной суммы к 65535 даст 65535.) Некоторые процессоры могут генерировать исключение , если арифметический результат превышает доступную точность. При необходимости исключение можно перехватить и устранить — например, операцию можно перезапустить в программном обеспечении с использованием арифметических операций произвольной точности.
Во многих случаях задача или программист могут гарантировать, что целочисленные значения в конкретном приложении не станут достаточно большими, чтобы вызвать переполнение. Такие гарантии могут быть основаны на прагматических ограничениях: программа посещаемости школы может иметь ограничение в 4000 учащихся. Программист может спроектировать вычисления так, чтобы промежуточные результаты оставались в пределах заданных границ точности.
Некоторые языки программирования, такие как Lisp , Python , Perl , Haskell , Ruby и Raku , используют или имеют возможность использовать числа произвольной точности для всей целочисленной арифметики. Хотя это снижает производительность, но исключает возможность получения неверных результатов (или исключений) из-за простого переполнения. Это также позволяет гарантировать, что арифметические результаты будут одинаковыми на всех машинах, независимо от размера слова какой-либо конкретной машины . Исключительное использование чисел произвольной точности в языке программирования также упрощает язык, поскольку число — это число , и нет необходимости в нескольких типах для представления разных уровней точности.
Проблемы реализации [ править ]
Арифметика произвольной точности выполняется значительно медленнее, чем арифметика с использованием чисел, которые полностью помещаются в регистры процессора, поскольку последние обычно реализуются в аппаратной арифметике, тогда как первые должны быть реализованы в программном обеспечении. Даже если в компьютере нет аппаратного обеспечения для определенных операций (например, целочисленного деления или всех операций с плавающей запятой) и вместо него предоставляется программное обеспечение, он будет использовать размеры чисел, тесно связанные с доступными аппаратными регистрами: только одно или два слова. Есть исключения, поскольку некоторые машины с переменной длиной слова 1950-х и 1960-х годов, особенно IBM 1620 , IBM 1401 и серии Honeywell 200 , могли манипулировать числами, связанными только с доступной памятью, с дополнительным битом, который ограничивал значение.
Числа могут храниться в формате с фиксированной запятой или в формате с плавающей запятой как мантисса, умноженная на произвольный показатель степени. Однако, поскольку деление почти сразу же приводит к бесконечно повторяющимся последовательностям цифр (например, 4/7 в десятичной системе счисления или 1/10 в двоичной системе), если такая возможность возникнет, тогда либо представление будет усечено до некоторого удовлетворительного размера, либо рациональные числа будут используется: большое целое число для числителя и знаменателя . Но даже если выделить наибольший общий делитель , арифметика с рациональными числами может очень быстро стать громоздкой: 1/99 − 1/100 = 1/9900, а если затем прибавить 1/101, результат будет 10001/999900.
Размер чисел произвольной точности на практике ограничен общим объемом доступной памяти и временем вычислений.
множество алгоритмов Было разработано для эффективного выполнения арифметических операций над числами, хранящимися с произвольной точностью. В частности, предполагая, что сложность N цифр, были разработаны алгоритмы, позволяющие минимизировать асимптотическую для больших 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, и т. д. последовательные факториалы.
constants:
Limit = 1000 % Sufficient digits.
Base = 10 % The base of the simulated arithmetic.
FactorialLimit = 365 % Target number to solve, 365!
tdigit: Array[0:9] of character = ["0","1","2","3","4","5","6","7","8","9"]
variables:
digit: Array[1:Limit] of 0..9 % The big number.
carry, d: Integer % Assistants during multiplication.
last: Integer % Index into the big number's digits.
text: Array[1:Limit] of character % Scratchpad for the output.
digit[*] := 0 % Clear the whole array.
last := 1 % The big number starts as a single-digit,
digit[1] := 1 % its only digit is 1.
for n := 1 to FactorialLimit: % Step through producing 1!, 2!, 3!, 4!, etc.
carry := 0 % Start a multiply by n.
for i := 1 to last: % Step along every digit.
d := digit[i] * n + carry % Multiply a single digit.
digit[i] := d mod Base % Keep the low-order digit of the result.
carry := d div Base % Carry over to the next digit.
while carry > 0: % Store the remaining carry in the big number.
if last >= Limit: error("overflow")
last := last + 1 % One more digit.
digit[last] := carry mod Base
carry := carry div Base % Strip the last digit off the carry.
text[*] := " " % Now prepare the output.
for i := 1 to last: % Translate from binary to text.
text[Limit - i + 1] := tdigit[digit[i]] % Reversing the order.
print text[Limit - last + 1:Limit], " = ", n, "!"
Рассмотрев пример, можно обсудить ряд деталей. Самым важным является выбор представления большого числа. В этом случае для цифр требуются только целые значения, поэтому достаточно массива целых чисел фиксированной ширины. Удобно, чтобы последовательные элементы массива представляли высшие степени основания.
Второе по важности решение – это выбор основания арифметики, здесь десять. Есть много соображений. Переменная блокнота d должна быть способна хранить результат умножения одной цифры плюс перенос от умножения предыдущей цифры. В десятичной системе счисления, безусловно, достаточно шестнадцатибитного целого числа, поскольку оно позволяет получить число до 32767. Однако этот пример является обманом, поскольку значение n само по себе не ограничивается одной цифрой. Это приводит к тому, что метод не будет работать при n > 3200 или около того. В более общей реализации n также будет использовать многозначное представление. Вторым последствием сокращения является то, что после завершения многозначного умножения последнее значение переноса , возможно, придется перенести в несколько цифр старшего порядка, а не только в одну.
Существует также проблема вывода результата в десятичной системе счисления для человеческого рассмотрения. Поскольку основание уже равно десяти, результат можно показать, просто напечатав последовательные цифры массива digit , но они будут отображаться с последней цифрой старшего порядка (так что 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-битные целые числа), мы могли бы использовать более крупные базы, например 10 000. Работа с базой степени 2, более близкой к встроенным целочисленным операциям компьютера, дает преимущества, хотя преобразование в десятичную базу для вывода становится более трудным. На типичных современных компьютерах сложение и умножение занимают постоянное время, независимо от значений операндов (пока операнды укладываются в отдельные машинные слова), поэтому можно получить большую выгоду от упаковки как можно большего количества больших чисел в каждый элемент. массив цифр. Компьютер также может предлагать средства для разделения произведения на цифры и переноса без необходимости выполнения двух операций mod и div , как в примере, и почти все арифметические единицы имеют флаг переноса , который можно использовать при сложении и вычитании с многократной точностью. Такого рода детали составляют основу программистов машинного кода, и подходящая программа больших чисел на языке ассемблера может работать быстрее, чем результат компиляции языка высокого уровня, который не обеспечивает прямого доступа к таким средствам, а вместо этого отображает инструкции высокого уровня для своей модели целевой машины с использованием оптимизирующего компилятора.
Для однозначного умножения рабочие переменные должны иметь возможность хранить значение (по основанию -1). 2 + перенос, где максимальное значение переноса равно (основание-1). Аналогично, переменные, используемые для индексации массива цифр, сами по себе ограничены по ширине. Простым способом расширения индексов было бы обрабатывать цифры больших чисел блоками некоторого удобного размера, чтобы адресация осуществлялась через (блок i , цифра j ), где i и j были бы маленькими целыми числами, или можно было бы перейти к использование методов больших чисел для индексирующих переменных. В конечном счете, емкость машины и время выполнения накладывают ограничения на размер задачи.
История [ править ]
Первый бизнес-компьютер IBM, IBM 702 ( ламповая машина) середины 1950-х годов, полностью аппаратно реализовал целочисленную арифметику с цифровыми строками любой длины от 1 до 511 цифр. Самая ранняя широко распространенная программная реализация арифметики произвольной точности, вероятно, была в Maclisp . Позже, примерно в 1980 году, операционные системы VAX/VMS и VM/CMS предлагали средства bignum в виде набора строковых функций в одном случае и в языках EXEC 2 и REXX – в другом.
Ранняя широко распространенная реализация была доступна через IBM 1620 1959–1970 годов. 1620 представлял собой машину с десятичными цифрами, в которой использовались дискретные транзисторы, но при этом у нее было аппаратное обеспечение (которое использовало справочные таблицы ) для выполнения целочисленных арифметических операций над строками цифр длиной от двух до любой доступной памяти. Для арифметики с плавающей запятой мантисса была ограничена сотней цифр или меньше, а показатель степени — только двумя цифрами. Самая большая поставляемая память предлагала 60 000 цифр, однако компиляторы Фортрана для 1620 остановились на фиксированных размерах, таких как 10, хотя это можно было указать на контрольной карте, если значение по умолчанию было неудовлетворительным.
Библиотеки программного обеспечения [ править ]
Арифметика произвольной точности в большинстве компьютерных программ реализуется путем вызова внешней библиотеки , которая предоставляет типы данных и подпрограммы для хранения чисел с запрошенной точностью и выполнения вычислений.
Разные библиотеки имеют разные способы представления чисел произвольной точности, некоторые библиотеки работают только с целыми числами, другие хранят числа с плавающей запятой в различных системах счисления (десятичные или двоичные степени). Вместо того, чтобы представлять число как одно значение, некоторые хранят числа в виде пары числитель/знаменатель ( рациональные числа ), а некоторые могут полностью представлять вычислимые числа , хотя и только до некоторого предела хранения. По сути, машины Тьюринга не могут представлять все действительные числа , мощность поскольку превышает мощность .
См. также [ править ]
- Алгоритм Фюрера
- Алгоритм Карацубы
- Арифметика смешанной точности
- Алгоритм Шенхаге – Штрассена
- Умножение Тума – Кука
- База Little Endian 128
Ссылки [ править ]
- ^ дотнет-бот. «Структура BigInteger (System.Numerics)» . docs.microsoft.com . Проверено 22 февраля 2022 г.
- ^ «PEP 237 — Объединение длинных и целых чисел» . Python.org . Проверено 23 мая 2022 г.
- ^ «BigInteger (платформа Java SE 7)» . docs.oracle.com . Проверено 22 февраля 2022 г.
- ^ «BigInt — JavaScript | MDN» . http://developer.mozilla.org . Проверено 22 февраля 2022 г.
- ^ Жаки Ченг (23 мая 2007 г.). «Исследователи: взлом 307-значного ключа ставит под угрозу 1024-битный RSA» .
- ^ «RSA Laboratories - 3.1.5 Какой размер ключа следует использовать в криптосистеме RSA?» . Архивировано из оригинала 1 апреля 2012 г. Проверено 31 марта 2012 г. рекомендует, чтобы важные ключи RSA имели длину 2048 бит (примерно 600 цифр).
- ^ Лоран Фусс (2006). Численное интегрирование с ограниченной ошибкой произвольной точности. Моделирование и симуляция (Отчет) (на французском языке). Университет Анри Пуанкаре - Нанси И.
- ^ РК Патрия (1962). «Статистическое исследование случайности среди первых 10 000 цифр числа Пи» . Математика вычислений . 16 (78): 188–197. дои : 10.1090/s0025-5718-1962-0144443-7 . Проверено 10 января 2014 г. Пример цитаты из этой статьи: «Подобный крайний паттерн опасен, даже если он разбавлен одним из соседних блоков»; это было появление последовательности 77 двадцать восемь раз в одном блоке из тысячи цифр.
Дальнейшее чтение [ править ]
- Кнут, Дональд (2008). Получисловые алгоритмы . Искусство компьютерного программирования . Том. 2 (3-е изд.). Аддисон-Уэсли. ISBN 978-0-201-89684-8 . , Раздел 4.3.1: Классические алгоритмы
- Дерик Вуд (1984). Парадигмы и программирование на языке Паскаль . Пресса по информатике. ISBN 0-914894-45-5 .
- Ричард Крэндалл, Карл Померанс (2005). Простые числа . Спрингер-Верлаг. ISBN 9780387252827 . , Глава 9: Быстрые алгоритмы для арифметики больших целых чисел
Внешние ссылки [ править ]
- В главе 9.3 книги «Искусство сборки» Рэндалла Хайда обсуждается арифметика с множественной точностью и приводятся примеры на ассемблере x86 .
- Задача Rosetta Code Целые числа произвольной точности Практические примеры в стиле, в котором более 95 языков программирования вычисляют значение 5**4**3**2 с использованием арифметики произвольной точности.