Navigation Bar

Calculators: Convergents

Back to Calculator Index

 

Introduction

(2019/08/20) Convergents are a sequence of rational numbers, which increasingly better approximate a given number. The number can be a rational number, in which case the sequence ends with the given value; or, a real number like an irrational root or transcendental constant, in which case the sequence continues infinitely.

In short, this lets you approximate a complicated ratio by multiplying and dividing with relatively small integers.

 

 

Calculator

Enter a number (in decimal format "123.456" or floating point "1.234e6"), or a ratio (two numbers, separated by a "/").

Ratio to approximate A =
Maximum number of iterations N =
Maximum numerator or denominator max(h, k) =
Numerator h =
 
Denominator k =
 
Approximated Ratio h / k =
 
Sequence of Convergents
---

 

Discussion

Examples where this might arise:

On the other hand, where an incremental, repetitive, or real-time ratio is required, it is often better to employ Bresenham's line algorithm to generate a rounded or dithered sequence. The most familiar application of this algorithm is in drawing graphical lines (a ratio in spacial dimensions), however the same algorithm, applied over time (a ratio of value over time—a rate) rather than space, is simply an NCO or DDS. Delta-sigma modulation is also a related topic.

Continued Fractions

This is a wonderful bit of arithmetic. It's a shame it's not taught earlier in school; it relates to lots of beautiful number-theoretic and analytic mathematics. By stacking fractions infinitely, one can construct any real number. By building a tree of every possible combination of fractions, one can construct, not just the entire real number line, but a superset called the surreals. Obivously—infinities aren't very practical, but since they get arbitrarily close to real numbers (and zero and infinity), and progressively closer in a sequence, they are very useful indeed.

This probably sounds complicated and overwhelming...

Continued Fraction

Relax: just evaluate it starting from the bottom-right. Do exactly what the formula says: Take a calculator and punch in the highest (nth) term. Take the reciprocal (1/x). Add the next term (an-1). Take the reciprocal. And so on, until you add the zeroeth term. Voila, you're done! (Alternately, for those of you accustomed to RPN calculators, the whole stack can be entered in one go.)

Conversely, to calculate the simple continued fraction of a number, simply: subtract the whole (integer) part of the number (write it down); then take the reciprocal (of the remainder); then repeat these steps. If the reciprocal eventually becomes whole, that means you're done: the number was a rational number, and you've taken it completely apart. If the sequence repeats, it's probably an irrational square root; if it continues erratically, it's probably something else (or, you're just pulling up rounding errors). Which, speaking of rounding errors: you may sometimes get a crazy answer for a final step (for example, the 14th step for "1.618"). This is a side effect of the floating point arithmetic used; just ignore the last step.

What's the simplest continued fraction? Alternately, have you ever wondered if there exists a number where the fractional part looks the same whether "right side up" or (1/x)? If you take a calculator and repeatedly type in: +, 1, (1/x), ..., you get something like 1.618... Indeed, if you use that description as a word problem, you get the relation: x + 1 = 1 / x, which has the solution x = ±(1 + √5) / 2, better known as φ, the golden ratio.

Which brings up another interesting property of continued fractions. You know you've reached a good stopping point when one of the terms is unusually large. φ is the worst possible number to approximate with a rational number: it has the smallest possible terms, all ones, so the convergence is as slow as it can be. In contrast, the 5th term of π's continued fraction is very large—292, a sign that the proceeding terms approximate π extremely well. Indeed, stopping the sequence at this point gives the famous 355/113, good to 6 decimal places!

 

Back to Calculator Index

 

Copyright Notice