## 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.$

### Hosting and Status for the Numbers Project

The Numbers Project has been lying dormant for a while, but it still very much alive. Following this site’s new name, it is now named Kanooth Numbers. The hosting of the project has also been moved from Sourceforge to GitHub, see the new home for the source code. Several of the posts related to the [...]

### Fast Evaluation of Fibonacci Numbers

The integer sequence 0, 1, 1, 2, 3, 5, 8, 13, … is well known as the Fibonacci sequence. It is easily defined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$.

To compute $F_n$ you could use this definition directly, but that leads to a highly inefficient algorithm that is both recursive and which uses a number of additions which grows exponentially with n.

### Evaluation of Powers

How do you efficiently compute xn for a positive integer n? Take x15 as an example. You could take x and repeatedly multiply by x 14 times. A better way to do it, however, is this:

### Computing the Integer Binary Logarithm

The binary logarithm, or the logarithm to the base 2, of a number x > 0 is the number y = log2 x such that 2y = x. This article looks at how we can determine the integer part of the binary logarithm using integer arithmetic only. Naturally, the binary logarithm is especially easy to [...]

### Bitwise Operators and Negative Numbers

When representing integers using a fixed number of bits, negative numbers are typically represented using two’s complement. If using n bit numbers, the two’s complement of a number x with 0 ≤ x < 2n is (-x) mod 2n = 2n – x. But what do you do if you want to work with unbounded/multiple-precision [...]