Arbitrary-precision arithmetic

This product was added to computer science because of the content, defects on the quality assurance side of the editor. This is done to bring the quality of the articles from the computer science subject area to an acceptable level. Help us to eliminate the substantive shortcomings of this article and take part you in the discussion! ( )

The long integer arithmetic deals with the calculation with figures which have a very high number to be processed in places.

In the conventional computer arithmetic limits the length of the data word that can be accommodated in the arithmetic unit of the processor, the length of the numbers can be expected to arise. In the today's computers are typically 32 or 64 bits. This hardware feature is reflected in the range of primitive numeric data types that provide the programming languages ​​available, and offer the maximum space for unsigned integers from -2,147,483,648 to 2,147,483,647, respectively, for 64- bit machines, of - 9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. For floating-point plays mostly limiting the accuracy, less the value range, a role.

Applications

Applications of high-precision arithmetic are, for example:

  • If you need accurate calculation with large numbers, such as in cryptography or, in many applications of faculties and binomial coefficients;
  • If numbers like Pi or other mathematical constants are to be determined on as many digits of precision;
  • When simulating systems whose behavior so sensitive on the initial conditions dependent (so-called butterfly effect ) that the limited accuracy of ordinary arithmetic makes the result unusable;
  • If programming languages ​​are implemented that can automatically tolerate the defection of variables.

Implementation

In the long integer arithmetic now is not the processor architecture, but the amount of available memory the scope within which arbitrarily long numbers can be processed. In some modern programming languages ​​-precision arithmetic is installed by default, but are in other libraries. Computer algebra systems support ( in addition to the symbolic mathematics, with which it is not to be confused ) has always been well -precision arithmetic.

In the implementation of efficient mathematical algorithms are in the foreground in order to minimize the computation time.

A method in computing with large numbers very frequently used is the sequential execution of individual computational steps with smaller numbers. So you can divide, for example, the digits of a 1024 - digit binary number to sixteen 64- digit binary expect and do it on a smaller processor.

Addition and subtraction

In addition and subtraction of long numbers the individual binary digits separated blocks are added or subtracted and pass a carry.

Multiplication

In the multiplication, there are already a variety of approaches for algorithms such as the Karatsuba algorithm or Schönhage - road algorithm. There is a presumption that the barrier in the complexity can not be beaten.

Programming languages

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

  • Common Lisp: The ANSI Common Lisp standard supports high-precision arithmetic ( integer, rational and complex numbers).
  • C #: System.Numerics.BigInteger from NET Framework 4.0.
  • Cold Fusion: the predefined function PrecisionEvaluate () function calculates one or more string expressions dynamically from left to right with decimal arithmetic.
  • D: standard library std.bigint
  • Dart: The built-in data type int supports long integer arithmetic.
  • Erlang: The built-in integer data type support long integer arithmetic.
  • Go: The standard library supports big -precision arithmetic for integers ( type int ) and rational numbers (Type Council).
  • Haskell: The built-in integer data type support long integer arithmetic and the standard module Data.Ratio supports rational numbers.
  • ISLISP: The ISO / IEC 13816:1997 (E) ISLISP standard supports high-precision arithmetic for integers.
  • J: Built-in extended precision
  • Java: class java.math.BigInteger (integer), Class java.math.BigDecimal (decimal)
  • JavaScript: The library gwt -math defines an interface for java.math.BigDecimal, and the library BigInt support long integer arithmetic for integers.
  • OCaml: the library Num supports long integer arithmetic for whole and rational numbers.
  • Perl: The pragmas bignum and bigrat allow BigNum and BigRational support for Perl.
  • PHP: The module BC Math support long integer arithmetic.
  • Pike: The built-in type int automatically changes from machine-oriented representation of integers to long integer arithmetic, when a value can not be represented in machine-oriented representation.
  • Python: The built-in type int ( 3.x) / long (2.x ) supports high-precision arithmetic. (But exponential, square root, etc. no trigonometric functions ) The class Decimal decimal of the standard library has user-definable precision and some mathematical functions. More high-precision arithmetic for floating point numbers is made possible with the libraries " mpmath " and " bigfloat " of third parties.
  • Racket: The built-in exact numbers using high-precision arithmetic. For example: ( expt 10 100 ) produces the expected (large ) result. Exacte numbers also support rational numbers so produced ( / 3 4) 3/4.
  • REXX: Variants inclusive Open Object Rexx and NetRexx
  • Ruby: The built-in integer type Bignum support long integer arithmetic. The BigDecimal class from the standard library BigDecimal supports long integer arithmetic.
  • Scheme: R5RS allowed, and R6RS requires support that whole and rational numbers long integer arithmetic.
  • Scala: class BigInt and BigDecimal class.
  • Seed7: BigInteger and bigRational.
  • Smalltalk: variants including Squeak, Smalltalk / X, GNU Smalltalk, Dolphin Smalltalk, etc.
  • Standard ML: The optional built-in structure IntInf implemented INTEGER and supports high-precision arithmetic for integers.
498609
de