Арифметика произвольной точности: вычисления без ограничений по размеру чисел

Введение

Расчеты, в которых точность чисел ограничена лишь объемом памяти компьютера.

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

Приложения

Общим применением является криптография с открытым ключом, алгоритмы которой обычно используют арифметику с целыми числами, содержащими сотни цифр. Другая область применения – ситуации, где искусственные ограничения и переполнения недопустимы. Она также полезна для проверки результатов вычислений с фиксированной точностью и для определения оптимальных или близких к оптимальным значений коэффициентов, необходимых в формулах, например, коэффициента, используемого в гауссовском интегрировании. Арифметика произвольной точности также применяется для вычисления фундаментальных математических констант, таких как π, с миллионами и более цифр, и для анализа свойств последовательностей цифр или, в более общем смысле, для исследования точного поведения функций, таких как дзета-функция Римана, где определенные вопросы сложно исследовать аналитическими методами. Другой пример – рендеринг фрактальных изображений с чрезвычайно высоким увеличением, например, изображений, встречающихся в множестве Мандельброта. Арифметику произвольной точности также можно использовать для предотвращения переполнения, которое является неотъемлемым ограничением арифметики с фиксированной точностью. Подобно пятизначному одометру, который переходит от 99999 к 00000, целое число с фиксированной точностью может демонстрировать перенос, если числа становятся слишком большими для представления на заданном уровне точности. Некоторые процессоры могут обрабатывать переполнение посредством насыщения, что означает, что если результат не может быть представлен, он заменяется ближайшим представимым значением. (При 16-битном ненасыщенном насыщении добавление любого положительного числа к 65535 даст 65535.) Некоторые процессоры могут генерировать исключение, если арифметический результат превышает доступную точность. При необходимости исключение можно перехватить и обработать, например, операцию можно перезапустить в программном обеспечении с использованием арифметики произвольной точности. Во многих случаях задача или программист могут гарантировать, что целочисленные значения в конкретном приложении не станут достаточно большими, чтобы вызвать переполнение. Такие гарантии могут основываться на практических ограничениях: программа учета посещаемости школы может иметь ограничение в 4000 учеников. Программист может спроектировать вычисления таким образом, чтобы промежуточные результаты оставались в пределах заданных границ точности. Некоторые языки программирования, такие как Lisp, Python, Perl, Haskell, Ruby и Raku используют или предоставляют возможность использования чисел произвольной точности для всех целочисленных операций. Хотя это снижает производительность, это исключает возможность получения неверных результатов (или исключений) из-за простого переполнения. Это также позволяет гарантировать, что арифметические результаты будут одинаковыми на всех машинах, независимо от размера слова в конкретной машине. Исключительное использование чисел произвольной точности в языке программирования также упрощает язык, поскольку число – это просто число, и нет необходимости в нескольких типах для представления разных уровней точности.

A common application is public key cryptography, whose algorithms commonly employ arithmetic with integers having hundreds of digits. Another is in situations where artificial limits and overflows would be inappropriate. It is also useful for checking the results of fixed precision calculations, and for determining optimal or near optimal values for coefficients needed in formulae, for example the that appears in Gaussian integration. Arbitrary precision arithmetic is also used to compute fundamental mathematical constants such as π to millions or more digits and to analyze the properties of the digit strings or more generally to investigate the precise behaviour of functions such as the Riemann zeta function where certain questions are difficult to explore via analytical methods. Another example is in rendering fractal images with an extremely high magnification, such as those found in the Mandelbrot set. Arbitrary precision arithmetic can also be used to avoid overflow, which is an inherent limitation of fixed precision arithmetic. Similar to a five digit odometer's display which changes from 99999 to 00000, a fixed precision integer may exhibit wraparound if numbers grow too large to represent at the fixed level of precision. Some processors can instead deal with overflow by saturation, which means that if a result would be unrepresentable, it is replaced with the nearest representable value. (With 16 bit unsigned saturation, adding any positive amount to 65535 would yield 65535.) Some processors can generate an exception if an arithmetic result exceeds the available precision. Where necessary, the exception can be caught and recovered from—for instance, the operation could be restarted in software using arbitrary precision arithmetic. In many cases, the task or the programmer can guarantee that the integer values in a specific application will not grow large enough to cause an overflow. Such guarantees may be based on pragmatic limits: a school attendance program may have a task limit of 4,000 students. A programmer may design the computation so that intermediate results stay within specified precision boundaries. Some programming languages such as Lisp, Python, Perl, Haskell, Ruby and Raku use, or have an option to use, arbitrary precision numbers for all integer arithmetic. Although this reduces performance, it eliminates the possibility of incorrect results (or exceptions) due to simple overflow. It also makes it possible to guarantee that arithmetic results will be the same on all machines, regardless of any particular machine's word size. The exclusive use of arbitrary precision numbers in a programming language also simplifies the language, because a number is a number and there is no need for multiple types to represent different levels of precision.

Вопросы внедрения

Арифметика произвольной точности значительно медленнее, чем арифметика, использующая числа, которые полностью помещаются в регистры процессора, поскольку последние обычно реализуются аппаратно, а первые – программно. Даже если компьютеру не хватает аппаратной поддержки для определенных операций (таких как целочисленное деление или все операции с плавающей точкой) и вместо этого предоставляется программная реализация, она будет использовать размеры чисел, тесно связанные с доступными аппаратными регистрами: обычно одно или два слова. Существуют исключения: некоторые машины с переменной длиной слова 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) (см. нотацию «большое O»). Сравнение также очень простое: достаточно сравнивать старшие разряды (или машинные слова) до обнаружения различия. Сравнение остальных разрядов/слов не требуется. В худшем случае сложность составляет O(N), но обычно это происходит гораздо быстрее. Для умножения наиболее простые алгоритмы, используемые для умножения вручную (как учат в начальной школе), требуют O(N²) операций, но существуют алгоритмы умножения, достигающие сложности O(N log(N) log(log(N))), такие как алгоритм Шёнхаге — Штрассена, основанный на быстром преобразовании Фурье, а также алгоритмы с немного худшей сложностью, но иногда с лучшей производительностью на практике для небольших N. Умножение Каратсубы – один из таких алгоритмов. Подробнее о делении см. алгоритм деления. Список алгоритмов с оценками сложности приведен в статье о вычислительной сложности математических операций. Примеры на ассемблере x86 см. в разделе внешних ссылок.

Arbitrary precision arithmetic is considerably slower than arithmetic using numbers that fit entirely within processor registers, since the latter are usually implemented in hardware arithmetic whereas the former must be implemented in software. Even if the computer lacks hardware for certain operations (such as integer division, or all floating point operations) and software is provided instead, it will use number sizes closely related to the available hardware registers: one or two words only. There are exceptions, as certain variable word length machines of the 1950s and 1960s, notably the IBM 1620, IBM 1401 and the Honeywell 200 series, could manipulate numbers bound only by available storage, with an extra bit that delimited the value. Numbers can be stored in a fixed point format, or in a floating point format as a significand multiplied by an arbitrary exponent. However, since division almost immediately introduces infinitely repeating sequences of digits (such as 4/7 in decimal, or 1/10 in binary), should this possibility arise then either the representation would be truncated at some satisfactory size or else rational numbers would be used: a large integer for the numerator and for the denominator. But even with the greatest common divisor divided out, arithmetic with rational numbers can become unwieldy very quickly: 1/99 − 1/100 = 1/9900, and if 1/101 is then added, the result is 10001/999900. The size of arbitrary precision numbers is limited in practice by the total storage available, and computation time. Numerous algorithms have been developed to efficiently perform arithmetic operations on numbers stored with arbitrary precision. In particular, supposing that N digits are employed, algorithms have been designed to minimize the asymptotic complexity for large N.

The simplest algorithms are for addition and subtraction, where one simply adds or subtracts the digits in sequence, carrying as necessary, which yields an O(N) algorithm (see big O notation). Comparison is also very simple. Compare the high order digits (or machine words) until a difference is found. Comparing the rest of the digits/words is not necessary. The worst case is (N), but usually it will go much faster. For multiplication, the most straightforward algorithms used for multiplying numbers by hand (as taught in primary school) require (N^(2)) operations, but multiplication algorithms that achieve O(N log(N) log(log(N))) complexity have been devised, such as the Schönhage–Strassen algorithm, based on fast Fourier transforms, and there are also algorithms with slightly worse complexity but with sometimes superior real world performance for smaller N. The Karatsuba multiplication is such an algorithm. For division, see division algorithm. For a list of algorithms along with complexity estimates, see computational complexity of mathematical operations. For examples in x86 assembly, see external links.

Установленная точность

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

История

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

Библиотеки программного обеспечения

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