Posts tagged algorithms

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.