В информатике арифметика произвольной точности , также называемая арифметикой больших чисел , арифметикой многократной точности или иногда арифметикой бесконечной точности , означает, что вычисления выполняются над числами, точность цифр которых потенциально ограничена только доступной памятью хост-системы. Это контрастирует с более быстрой арифметикой фиксированной точности, встречающейся в большинстве аппаратных средств арифметико-логических устройств (АЛУ), которые обычно предлагают точность от 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 series, могли манипулировать числами, связанными только с доступной памятью, с дополнительным битом, который ограничивал значение.
Числа могут храниться в формате с фиксированной точкой или в формате с плавающей точкой как мантисса, умноженная на произвольную экспоненту. Однако, поскольку деление почти сразу вводит бесконечно повторяющиеся последовательности цифр (например, 4/7 в десятичной системе или 1/10 в двоичной), если бы возникла такая возможность, то либо представление было бы усечено до некоторого удовлетворительного размера, либо использовались бы рациональные числа: большое целое число для числителя и для знаменателя . Но даже при разделении наибольшего общего делителя арифметика с рациональными числами может очень быстро стать громоздкой: 1/99 − 1/100 = 1/9900, а если затем добавить 1/101, то результат будет 10001/999900.
Размер чисел произвольной точности на практике ограничен общим объемом доступной памяти и временем вычислений.
Было разработано множество алгоритмов для эффективного выполнения арифметических операций над числами, хранящимися с произвольной точностью. В частности, предполагая , что используется N цифр, были разработаны алгоритмы для минимизации асимптотической сложности для больших N.
Простейшими алгоритмами являются сложение и вычитание , когда просто последовательно добавляются или вычитаются цифры, переносясь по мере необходимости, что дает алгоритм с сложностью O( N ) (см. нотацию big 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 % Основание моделируемой арифметики. ФакториалПредел = 365 % Целевое число для решения, 365! tdigit: Массив[0:9] символов = ["0","1","2","3","4","5","6","7","8","9"]переменные: digit: Array[1:Limit] of 0..9 % Большое число. carry, d: Integer % Помощники при умножении. last: Integer % Индекс в цифрах большого числа. text: Array[1:Limit] of character % Блокнот для вывода.digit[*] := 0 % Очистить весь массив.
last := 1 % Большое число начинается с одной цифры,
digit[1] := 1 % его единственная цифра — 1.для n := 1 до FactorialLimit: % Пошаговое выполнение до получения 1!, 2!, 3!, 4! и т. д. перенос := 0 % Начать умножение на n. for i := 1 to last: % Пройти по каждой цифре. d := digit[i] * n + перенос % Умножить одну цифру. digit[i] := d mod Base % Сохраните младшую цифру результата. перенос := d div Base % Перенести на следующую цифру. while carry > 0: % Сохраняем оставшийся перенос в большом числе. if last >= Limit: error("overflow") last := last + 1 % Еще одна цифра. digit[last] := carry mod Base перенос := перенос div Base % Удалить последнюю цифру из переноса. text[*] := " " % Теперь подготовим вывод. for i := 1 to last: % Преобразуем из двоичного в текстовый. text[Limit - i + 1] := tdigit[digit[i]] % Изменяем порядок на обратный. print text[Limit - last + 1:Limit], " = ", n, "!"Учитывая пример, можно обсудить ряд деталей. Наиболее важным является выбор представления большого числа. В этом случае для цифр требуются только целые значения, поэтому достаточно массива целых чисел фиксированной ширины. Удобно, чтобы последовательные элементы массива представляли более высокие степени основания.
Второе по важности решение касается выбора основания арифметики, здесь десять. Есть много соображений. Переменная блокнота d должна иметь возможность хранить результат умножения одной цифры плюс перенос от умножения предыдущей цифры. В основании десять шестнадцатибитное целое число, безусловно, достаточно, поскольку оно допускает до 32767. Однако этот пример жульничает, поскольку само значение n не ограничено одной цифрой. Это приводит к тому, что метод не будет работать при n > 3200 или около того. В более общей реализации n также будет использовать многозначное представление. Второе следствие сокращения заключается в том, что после завершения многозначного умножения последнее значение переноса может потребоваться перенести в несколько цифр более высокого порядка, а не только в одну.
Также существует проблема печати результата в десятичной системе счисления для человеческого восприятия. Поскольку основание уже равно десяти, результат можно было бы показать просто путем печати последовательных цифр массива digit , но они бы появились с самой высокой цифрой в конце (так что 123 выглядело бы как "321"). Весь массив можно было бы напечатать в обратном порядке, но это представило бы число с ведущими нулями ("00000...000123"), что может быть не оценено, поэтому эта реализация создает представление в текстовой переменной с пробелами, а затем печатает ее. Первые несколько результатов (с пробелами через каждую пятую цифру и добавленной здесь аннотацией) таковы:
Эта реализация могла бы более эффективно использовать встроенную арифметику компьютера. Простым расширением было бы использование основания 100 (с соответствующими изменениями в процессе перевода для вывода), или, с достаточно широкими компьютерными переменными (такими как 32-битные целые числа), мы могли бы использовать более крупные основания, такие как 10 000. Работа в основании степени 2, более близком к встроенным целочисленным операциям компьютера, дает преимущества, хотя преобразование в десятичное основание для вывода становится более сложным. На типичных современных компьютерах сложения и умножения занимают постоянное время независимо от значений операндов (при условии, что операнды умещаются в отдельные машинные слова), поэтому есть большой выигрыш в упаковке как можно большего количества большого числа в каждый элемент массива цифр. Компьютер также может предлагать возможности для разделения произведения на цифру и перенос без необходимости выполнения двух операций mod и div , как в примере, и почти все арифметические устройства предоставляют флаг переноса , который может быть использован при сложении и вычитании с многократной точностью. Такого рода детали — суть заботы программистов машинного кода, и подходящая процедура bignumber на языке ассемблера может работать быстрее, чем результат компиляции языка высокого уровня, который не предоставляет прямого доступа к таким возможностям, а вместо этого сопоставляет операторы высокого уровня со своей моделью целевой машины с помощью оптимизирующего компилятора.
Для умножения одной цифры рабочие переменные должны иметь возможность хранить значение (основание-1) 2 + перенос, где максимальное значение переноса равно (основание-1). Аналогично, переменные, используемые для индексации массива цифр, сами по себе ограничены по ширине. Простым способом расширить индексы было бы иметь дело с цифрами bignumber в блоках некоторого удобного размера, так что адресация будет осуществляться через (блок i , цифра j ), где i и j будут небольшими целыми числами, или можно было бы перейти к использованию методов bignumber для индексирующих переменных. В конечном счете, емкость памяти машины и время выполнения накладывают ограничения на размер задачи.
Первый бизнес-компьютер IBM, IBM 702 ( ламповая машина) середины 1950-х годов, реализовал целочисленную арифметику полностью на аппаратном уровне на строках цифр любой длины от 1 до 511 цифр. Самая ранняя широко распространенная программная реализация арифметики произвольной точности была, вероятно, в Maclisp . Позднее, около 1980 года, операционные системы VAX/VMS и VM/CMS предложили средства bignum как набор строковых функций в одном случае и в языках EXEC 2 и REXX в другом.
Ранняя широко распространенная реализация была доступна через IBM 1620 1959–1970 годов. 1620 была десятичной машиной, которая использовала дискретные транзисторы, но при этом имела аппаратное обеспечение (которое использовало таблицы поиска ) для выполнения целочисленной арифметики над строками цифр длиной от двух до любой доступной памяти. Для арифметики с плавающей точкой мантисса была ограничена сотней цифр или меньше, а показатель степени был ограничен только двумя цифрами. Наибольший предоставленный объем памяти предлагал 60 000 цифр, однако компиляторы Fortran для 1620 остановились на фиксированных размерах, таких как 10, хотя это можно было указать на плате управления, если значение по умолчанию было неудовлетворительным.
Арифметика произвольной точности в большинстве компьютерных программ реализуется путем вызова внешней библиотеки , которая предоставляет типы данных и подпрограммы для хранения чисел с требуемой точностью и выполнения вычислений.
Различные библиотеки имеют различные способы представления чисел произвольной точности, некоторые библиотеки работают только с целыми числами, другие хранят числа с плавающей точкой в различных базах (десятичные или двоичные степени). Вместо того, чтобы представлять число как одно значение, некоторые хранят числа как пару числитель/знаменатель ( рациональные числа ), а некоторые могут полностью представлять вычислимые числа , хотя и только до некоторого предела хранения. По сути, машины Тьюринга не могут представлять все действительные числа , так как мощность превышает мощность .
