## Posts tagged numbers project

Let us consider short division, by which we mean a multiple-digit number $u = (u_{m-1} \ldots u_1 u_0)_b$ divided by a single digit $v$ (see, e.g., post on number representation). We will assume $m \geq 1$, $u_{m-1} \neq 0$ and $0 < v < b$. We are interested in a quotient $q = \lfloor u/v […] ### Basic Multiple-Precision Multiplication After addressing multiple-precision addition and subtraction, we now turn to multiplication of two multiple-precision numbers. Once again, we use the number representation and notation introduced earlier. Several algorithms exist for doing multiple-precision multiplication. This post will present the basic, pencil-and-paper-like method. Basically, it consists of two parts: Multiplying a number by a single digit and […] ### Multiple-Precision Subtraction We now turn to multiple-precision subtraction for non-negative integers. The algorithm is very similar to that of multiple-precision addition, but some minor differences make it worth while considering subtraction separately. We consider two n-digit numbers, \(u=(u_{n-1} \ldots u_1 u_0)_b$ and $v=(v_{n-1} \ldots v_1 v_0)_b$, with $n \geq 1$ (see a previous post on the number […]

This post will cover a basic addition algorithm for multiple-precision non-negative integers. The algorithm is based upon that presented in Section 4.3.1, The Classical Algorithms, of The Art of Computer Programming, Volume 2, by Donald E. Knuth. The notation and bounds used in this post were presented in a previous post.

We consider adding two n-digit numbers with $n \geq 1$, $u=(u_{n-1} \ldots u_1 u_0)_b$ and $v=(v_{n-1} \ldots v_1 v_0)_b$.

### Multiple-Precision Number Representation

Let us consider a common way to represent non-negative integers. An integer $u \geq 0$ will be represented in radix $b \geq 2$ using the notation $u = (u_{n-1} \ldots u_1 u_0)_b = \sum_{k=0}^{n-1} u_k b^k, \quad 0 \leq u_k \leq b-1.$