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 [...]
Posts tagged numbers project
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 [...]
Multiple-Precision Addition
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. \]
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 [...]
