Posts tagged algorithms

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 [...]

Full story »

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 [...]

Full story »

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.

Full story »

Implementing Multiple-Precision Arithmetic, Part 1

This article is the first in a series dealing with algorithms for multiple-precision arithmetic. The goal is to present both a theoretical foundation with high-level algorithm descriptions (based on Section 4.3.1, The Classical Algorithms, of The Art of Computer Programming, Volume 2, by Donald E. Knuth) and a portable C++ implementation of the algorithms. The theory and high-level algorithms will be quite universal and generic, whereas the presented code will be just one way to implement the algorithms in a specific programming language.

Full story »