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 algorithms
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\).
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 [...]
Continued Fractions and Continuants
We will be considering continued fractions of the form
\[
a_0 + \displaystyle\frac{1}{a_1 + \displaystyle\frac{1}{\ddots + \displaystyle\frac{1}{a_{n-1} + \displaystyle\frac{1}{a_n}}}}
\]
where the \(a_k\)’s are real numbers called the partial quotients [...]
Computing the Greatest Common Divisor
The greatest common divisor of two integers is the largest positive integer that divides them both. This article considers two algorithms for computing gcd(u,v), the greatest common divisor of u and v [...]
Implementing Multiple-Precision Arithmetic, Part 2
Introduction This article is a follow-up to part 1 where multiple-precision addition, subtraction, and multiplication for non-negative integers was discussed. This article deals with division. Again, the theoretic foundation is based on Section 4.3.1, The Classical Algorithms, of The Art of Computer Programming, Volume 2, by Donald E. Knuth.
)