Long number arithmetic

This article was due to content flaws on the quality assurance side of the computer science editorial added. This is done in order to bring the quality of the articles from the subject area of ​​computer science to an acceptable level. Help to eliminate the shortcomings in this article and take part in the discussion !  ( + )

The high-precision arithmetic is concerned with the calculation with numbers where a very large number to be processed in places.

A computer has built-in instructions to do math with small numbers extremely quickly. The range of these "small" numbers is typically ± 2 billion (for 32- bit computers) or ± 9  trillion (for 64-bit computers). Everything that goes beyond that, the computer can no longer calculate by itself, but needs programs specially written for this purpose that define the calculation rules for large numbers.

In addition to calculating with whole numbers, most computers have built-in instructions for floating point numbers . These are numbers that consist of a fixed number of digits, but where the comma can be anywhere. Typically, floating point numbers have 16 digits of precision . Here, too, there are applications that have to calculate more precisely, so that the built-in calculation commands are not sufficient.

Applications

The calculation of the circle number based on the Srinivasa-Ramanujan formula results in an approximate fraction with an 80-digit numerator after 9 iterations

Applications of long number arithmetic are e.g. B .:

• When large numbers have to be calculated precisely, for example in cryptography or in many applications of faculties and binomial coefficients ;
• When numbers such as pi or other mathematical constants are to be determined with as many digits as possible, with approximate fractions with multi-digit counters and denominators being converted into decimal numbers;
• If one simulates systems whose behavior depends so sensitively on the initial conditions (so-called butterfly effect ) that the limited accuracy of ordinary arithmetic makes the result unusable;
• When programming languages ​​are implemented that can automatically tolerate the overflow of variables .

implementation

To calculate with long numbers, computers use the same techniques as those used for written addition and subtraction . You break down large numbers into their digits, then calculate the partial results and then put the partial results together to form the final result. The only difference is that people usually calculate with the 10 digits from 0 to 9, but computers use larger "digits" from 0 to 2 billion, 9 trillion or even 170 quintillion, since they already have built-in commands for these digit sizes.

In long number arithmetic, it is not the processor architecture, but the size of the available working memory that sets the scope within which numbers of any length can be processed. In some modern programming languages ​​long number arithmetic is built in as standard, in others libraries are available for this. Computer algebra systems have always supported long-number arithmetic (in addition to symbolic mathematics , with which it should not be confused).

During the implementation, the most efficient mathematical algorithms possible are in the foreground in order to minimize the calculation times.

Addition and subtraction

If n is the word length of the processor, then the summands starting with the least significant word (bits 0 to n-1) are added to add long numbers. Any carry that occurs is stored in the carry bit of the processor and included in the addition of the next most significant word (bits n to 2n-1). This continues until all words have been processed.

The subtraction is done analogously. In the event of a negative result, the carry bit remains set after the operation has been completed and the difference is shown in two's complement.

multiplication

When it comes to multiplication, there are already a wide variety of approaches for algorithms, such as the Karazuba algorithm or the Schönhage-Strassen algorithm . There is the assumption that the barrier can not be undercut in terms of complexity . ${\displaystyle O(n\cdot \log(n))}$

Programming languages

Programming languages ​​that support long number arithmetic, either as built-in functionality or as part of the standard library:

• Common Lisp : The ANSI Common Lisp standard supports long number arithmetic (whole, rational and complex numbers).
• C # : System.Numerics.BigInteger , from .NET Framework 4.0
• ColdFusion : the built-in function PrecisionEvaluate () computes one or more string expressions dynamically from left to right using decimal arithmetic.
• D : standard library std.bigint
• Dart : The built-in data type int supports long number arithmetic.
• Erlang : The built-in data type integer supports long number arithmetic.
• Go : The standard library big supports long number arithmetic for integers (type Int ) and rational numbers (type Rat ).
• Haskell : The built-in data type integer supports long number arithmetic and the standard module Data.Ratio supports rational numbers.
• Icon : Supports LIA (Large Integer Arithmetic). B. roots, faculties, binomial coefficients u. Ä. Can be calculated with any number of digits.
• ISLISP : The ISO / IEC 13816: 1997 (E) ISLISP standard supports long number arithmetic for integers.
• J : Built-in extended precision
• Java : class java.math.BigInteger (integer), class java.math.BigDecimal (decimal)
• JavaScript : The built-in data type BigInt supports long number arithmetic. For older versions: The gwt-math library defines an interface for java.math.BigDecimal, and the BigInt library supports long number arithmetic for whole numbers.
• OCaml : The Num library supports long number arithmetic for whole and rational numbers.
• Perl : The pragmas bignum and bigrat enable BigNum and BigRational support for Perl.
• PHP : The BC Math module supports long number arithmetic.
• Pike : The built-in type int automatically changes from the machine-level representation of integers to long-number arithmetic as soon as a value cannot be represented in the machine-level representation.
• Python : The built-in type int (3.x) / long (2.x) supports long number arithmetic. The class Decimal standard library decimal has user-definable accuracy and some mathematical functions (exponential, square root, etc. but no trigonometric functions). More long number arithmetic for floating point numbers is made possible with the "mpmath" and "bigfloat" libraries from third-party providers.
• Racket : The built-in exact numbers use long number arithmetic. Eg: (expt 10 100) produces the expected (large) result. Exact numbers also support rational numbers, so produces (/ 3 4) 3/4.
• REXX : Variants including Open Object Rexx and NetRexx
• Ruby : The built-in integer type Bignum supports long number arithmetic. The BigDecimal class from the bigdecimal standard library supports long number arithmetic.
• Scheme : R ⁵ RS allows, and R ⁶ RS requires whole and rational numbers to support long number arithmetic.
• Scala : Class BigInt and Class BigDecimal .
• Seed7 : bigInteger and bigRational .
• Smalltalk : Variants including Squeak , Smalltalk / X , GNU Smalltalk , Dolphin Smalltalk etc.
• Standard ML : The optionally built-in structure IntInf implements INTEGER and supports long number arithmetic for integers.
• TeX ( typesetting system ): extension packages bigintcalc and xint .

Standalone Programs

• For example, ARIBAS outputs exact faculties and carries out (less exact) primality tests under UNIX , Linux , MS-DOS , MS Windows and on the Atari ST .

Individual evidence

1. ↑ Otto Forster : ARIBAS by O. Forster. Mathematics Faculty of the Ludwig Maximilians University Munich , January 26, 2010, accessed on May 31, 2018 .