Stern-Brocot tree

Stern-Brocot tree

__NOTOC__

In number theory, the Stern-Brocot tree is a method of listing all non-negative rational numbers (as well as a point representing infinity here represented formally as 1/0) in a tree structure. It was discovered independently by Moritz Stern (1858) and Achille Brocot (1860).

The tree may be created by an iterative process. It is easiest to describe as a list. Beginning with the list {0/1, 1/0} representing 0 and infinity respectively, one places between any two fractions the mediant of the fractions (the mediant of "a"/"c" and "b"/"d" is ("a" + "b")/("c" + "d")). The first few steps of this process yield:

* {0/1, 1/0}
* {0/1, 1/1, 1/0}
* {0/1, 1/2, 1/1, 2/1, 1/0}
* {0/1, 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1, 1/0}

This process can be represented as a tree where each row corresponds to the new numbers added at each step.

The tree is closely tied to the concept of simple continued fractions in canonical form. The value of any finite simple continued fraction in canonical form ["a"0; "a"1, "a"2, ..., "a""n"] can be found on the tree by starting at 1/1 and choosing the right path "a"0 times, then the left path "a"1 times, and continuing in this manner until choosing the right or left path (if "n" is even or odd respectively) "a""n" – 1 times. For example, 2/5 = [0; 2, 2] and is found by going left twice and right once.

The tree is also intimately related to the Farey sequence. Suppose we start with the endpoints 0/1 and 1/1 instead of 0/1 and 1/0. In this case the tree will contain all rational numbers between 0 and 1, inclusive. However, an in-order traversal of this tree up to a depth "n" does not in general yield the Farey sequence mathfrak F_n. This is because for "n" > 1, the mediant of two adjacent elements of mathfrak F_{n-1} is inserted between them in mathfrak F_n only if the denominator of the new fraction would be equal to "n". In particular, the part of the Stern-Brocot tree starting with 0/1 and 1/1 up to and including depth "n" will have 1 + 2 "n" elements, whereas mathfrak F_n including 0/1 and 1/1 has only 1 + sum_{k=1}^n varphi(k) elements.

Properties

* Every positive rational number can be found in this tree exactly once in lowest terms (i.e. the numerator and denominator are coprime)cite web | title=Stern Brocot-Tree | url=http://www.cut-the-knot.org/blue/Stern.shtml | accessdate=2008-09-03 | publisher=cut-the-knot.]

* The Stern-Brocot tree is an (infinite) binary search tree; that is, the rational numbers within it are sorted in natural order.

* If { frac{p_1}{q_1}, frac{p_2}{q_2}, ... frac{p_n}{q_n} } are all the rationals at the same depth in the Stern-Brocot tree, then sum_{k=1}^n frac{1}{p_kq_k} = 1.

Applications

Stern-Brocot trees can be used to convert floating-point numbers into rational numbers. By using a sort of binary search while constructing the tree and stopping once the desired precision is reached, floating-point numbers can be approximated to arbitrary precision. [Sedgewick and Wayne, "Introduction to Programming in Java". A Java implementation of this algorithm can be found [http://www.cs.princeton.edu/introcs/92symbolic/RationalApprox.java.html here] .]

References

External links

*
*


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Arbre de Stern-Brocot — En mathématiques, l arbre de Stern Brocot est une représentation de tous les rationnels strictement positifs, sous forme de fractions irréductibles. Il a été découvert presque simultanément par le mathématicien allemand Moritz Stern (en)… …   Wikipédia en Français

  • Moritz Abraham Stern — Born 29 June 1807(1807 06 29) Frankfurt …   Wikipedia

  • Binary tree — Not to be confused with B tree. A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. In computer science, a binary tree is a tree data structure in which each node has at… …   Wikipedia

  • Farey sequence — In mathematics, the Farey sequence of order n is the sequence of completely reduced fractions between 0 and 1 which, when in lowest terms, have denominators less than or equal to n , arranged in order of increasing size.Each Farey sequence starts …   Wikipedia

  • Continued fraction — Finite continued fraction, where a0 is an integer, any other ai are positive integers, and n is a non negative integer. In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the… …   Wikipedia

  • Minkowski's question mark function — Minkowski question mark function. ?(x) is on the left and ?(x) x is on the right. In …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Rounding — This article is about numerical rounding. For lip rounding in phonetics, see Labialisation. For other uses, see Rounding (disambiguation). Rounding a numerical value means replacing it by another value that is approximately equal but has a… …   Wikipedia

  • List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia

  • Viswanath's constant — A random Fibonacci sequence is a variant of the Fibonacci sequence, defined by the recurrence relation f n = plusmn; f n −1 plusmn; f n −2 with the signs chosen randomly. Viswanath s constant is a mathematical constant measuring how fast random… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”