---
tag: 8Y4C6N09YQ
kind: definition
name: Arbitrary-precision arithmetic
msc: [65Y04, 68W30]
defines: AS00YM4X7F
uses: [0C4JS9RF5M, RTKRSC3KPH]
sources:
  - url: https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
---

## Definition

Fix an integer base $B \ge 2$, in practice a power of $2$ such as $2^{64}$.
In *arbitrary-precision arithmetic* an [[integer|0C4JS9RF5M]] $a$ is stored as a sign and a list of digits $(a_0, \ldots, a_{k-1})$.
Here $0 \le a_i < B$ and
$$\abs{a} = \sum_{i=0}^{k-1} a_i B^i,$$
where the length $k$ is not fixed in advance and grows as needed.
Arithmetic operations on such lists return the exact integer result in the same form.
Rational numbers are stored as pairs of such integers.
Real numbers are stored as [[floating-point|RTKRSC3KPH]] numbers $m \cdot 2^{e}$, where $m$ and $e$ are such integers and the precision $p$ is chosen by the user.

## Remarks

Example: with $B = 10$, the integer $123456780$ is the list $(0, 8, 7, 6, 5, 4, 3, 2, 1)$; adding $1$ changes only $a_0$, while adding $999999999$ produces a list of length $10$.
Non-example: IEEE binary64 arithmetic is not arbitrary-precision; its precision is fixed at $53$ bits, so $2^{53} + 1$ cannot be stored exactly.
Addition of two $k$-digit numbers costs $O(k)$ digit operations, schoolbook multiplication costs $O(k^2)$, and Karatsuba multiplication costs $O(k^{\log_2 3})$.