A C# Library to Implement Stern-Brocot Trees

• Download source code - 3.4 KB

Introduction

Stern-Brocot trees are named after Moritz Stern and Achille Brocot who independently discovered them. A Stern-Brocot tree is an infinite, complete binary-search tree whose nodes stand in a one-to-one correspondence with the positive rational numbers, and it is used to find the closest rational approximation to an arbitrary floating-point number. The following figure, taken from Wikipedia, illustrates a partial 4-level Stern-Brocot tree.

The rationals stored in each node are caculated using the following simple rule. The value stored in the left child of a given parent node equals the value in the parent plus the rational on the vertical line to the left of the child. However, the additions are not performed in ordinary rational arithmetic, but simply by adding the corresponding numerators and denominators. For example, the rationals on the leftmost branch of the tree under the root are: (1+0)/(1+1) = 1/2, (1+0)/(2+1) = 1/3, (1+0)/(3+1) = 1/4. Likewise, the left child of the 2/3 parent node contains the rational (2+1)/(3+2) = 3/5. In the case of right children of parent nodes, they contain the rational of the parent plus the rational on the vertical line to their right. For example, the rationals on the rightmost branch of the tree under the root are: (1+1)/(1+0) = 2/1, (2+1)/(1+0) = 3/1, (3+1)/(1+0) = 4/1. Similarly, the right child of the 3/2 parent node contains the rational (3+2)/(2+1) = 5/3. The results of all these additions are called mediants. In general, given two rational numbers p1/n1 and p2/n2, their mediant is (p1 + p2)/(n1 + n2).

Implementation of Stern-Brocot Trees by a C# Library

The C# code to be described is largely based on the unmanaged C++ code written by Mircea Neacsu in 2016 and published in The Code Project on March 22 of 2021. (See Stern-Brocot Trees and their Applications.) For ease of reference, the names of all the functions in the C++ code have been maintained in the C# library, but there are several additional functions that are original. The library does not implement prime factorizations provided by the C++ code and used on demand. All the code of the library is defined within the namespace SBTlib.

Stern-Brocot Tree Nodes

The fundamental data structure for Stern-Brocot trees is defined by a class to implement its nodes. A node contains two integers _p and _q , corresponding to the numerator and denominator of a rational number, and references to its left and right children plus a reference to its parent. By definition, the parent of the root of the tree is null.

using System;

namespace SBTlib
{
   /// <summary>Class to implement a node in a Stern-Brocot tree. 
   /// </summary>
   public class SBTnode
   {
      public int _p, _q;
      public SBTnode left, right, parent;

      public SBTnode( SBTnode _parent )
      {
         _p = _q = 0;
         left = right = null;
         parent = _parent;
      }// SBTnode (constructor)
   } // SBTnode (class)
}// SBTlib (namespace)

Stern-Brocot Trees

The class to implement Stern-Brocot trees will be described in a stepwise fashion. The complete code is in the ZIP file attached to the article. To begin with, the class must provide a constructor.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Windows.Forms;

namespace SBTlib
{
   /// <summary>Class to implement Stern-Brocot trees for rational approximations
   ///          of floating-point (double) numbers.
   /// </summary>
   public class SBTree
   {
      SBTnode root;

      public SBTree()
      {
         Reset();
      }// SBTree (constructor)

      /// <summary>Initialize the root node and its children. 
      /// </summary>
      public void Reset()
      {
         root = new SBTnode( null );

         root._p = root._q = 1;
         Grow( root );
      }// Reset

The C++ code does not contain a class for the trees because the nodes are implemented by means of a struct. The SBTree class constructor simply calls function Reset to initialize (or re-initialize) the root of the tree. The parent of the root is set to null, the numerator and denominator of the root are set to 1, and function Grow is called to initialize the root’s children.

/// <summary>Add left and right children to a node.
/// </summary>
/// <param name="node">Node to which the children will be added.
/// </param>
private void Grow( SBTnode node )
{
   // Add left child.

   SBTnode left = new SBTnode( node );

   node.left = left;
   if ( node._p == 1 ) // Node on left tree boundary == 1 / (n + 1).
   {
      left._p = 1;
      left._q = node._q + 1;
   }
   else // Node is mediant of parent and previous node.
   {
      SBTnode previous = Previous( node );

      left._p = node._p + previous._p;
      left._q = node._q + previous._q;
   }

   // Add right child.

   SBTnode right = new SBTnode( node );

   node.right = right;
   if ( node._q == 1 ) // Node on right tree boundary == (n + 1) / 1.
   {
      right._q = 1;
      right._p = node._p + 1;
   }
   else // Node is mediant of parent and next node.
   {
      SBTnode next = Next( node );

      right._p = node._p + next._p;
      right._q = node._q + next._q;
   }
}// Grow

It is important to observe that, being infinite binary-search trees, Stern-Brocot trees are not implemented in full. They grow as needed during the search for a rational approximation to a floating-point number. That is the purpose of function Grow.

The following two functions Previous and Next are used when growing left and right children nodes are mediants of their parent and, respectively, their previous or next node.

/// <summary>Return node to the left.
/// </summary>
/// <param name="node">An SBTnode.
/// </param>
/// <returns>Node to the left.
/// </returns>
private SBTnode Previous( SBTnode node )
{
   Debug.Assert( node.parent != null );

   while ( node.parent.right != null && node.parent.right != node )
   {
      node = node.parent;
   }
   return node.parent;
}// Previous

/// <summary>Return node to the right.
/// </summary>
/// <param name="node">An SBTnode.
/// </param>
/// <returns>Node to the right.
/// </returns>
private SBTnode Next( SBTnode node )
{
   Debug.Assert( node.parent != null );

   while ( node.parent.left != null && node.parent.left != node )
   {
      node = node.parent;
   }
   return node.parent;
}// Next

The C++ code computes the rational approximation to a floating-point number in its main function. Since the C# code implements a library, there cannot be a Main function. Therefore, it provides a function to compute the approximation.

// The following function must return the numerator and
// denominator of the rational approximation.

/// <summary>Approximate a number with a given precision.
/// </summary>
/// <param name="x">Number to approximate.</param>
/// <param name="n">Precision in number of decimal places.
/// </param>
/// <returns>An instance of {Results}.
/// </returns>
public Results Approximate( double x, int n )
{
   if ( NotPositive( x ) )
   {
      MessageBox.Show(
         String.Format( "SBTree.Approximate: argument 'x' (== {0}) must be positive.",
                        x ) );

      return new Results( 0, 1, x, 0.0, new List<Tuple<int,int,double>>() );
   }
   else
   {
      double epsilon = Math.Pow( (double)10.0, (double)( -n ) );
      double approx = (double)1.0;
      List<Tuple<int, int, double>> sequence = new List<Tuple<int, int, double>>();

      // Call {Reset} if this function is to be used repeatedly.

      SBTnode current = root; // Starting point is the tree root.

      do
      {
         // Record current approximation.
         sequence.Add( new Tuple<int, int, double>( current._p, current._q, approx ) );

         // Move left or right.
         if ( x > approx )
         {
            current = current.right;
         }
         else
         {
            current = current.left;
         }
         // Grow the children of {current} node.
         Grow( current );

         // Update the approximation.
         approx = (double)current._p / (double)current._q;

      } while ( Math.Abs( x - approx ) > epsilon );

      return new Results( current._p, current._q, x, approx, sequence );
   }
}// Approximate

Function Approximate first checks whether the floating-point number is not positive. If so, it displays an appropriate MessageBox and returns an empty sequence of approximations.

      private bool NotPositive( double x )
      {
         string str = x.ToString();

         return str.StartsWith( "-" ) || str.Equals( "0" );
      }// NotPositive
   }// SBTree (class)
}// SBTlib (namespace)

Given that exact comparisons of floating-point numbers (especially comparisons with 0.0) are not reliable, function NotPositive converts the floating-point number to a string and checks whether the number was negative or 0.0.

Function Approximate keeps a record of the succesive approximations using a sequence of triples defined as List<Tuple<int, int, double>>, where the first two elements are the numerator and denominator of a rational number and the third is the corresponding floating-point approximation. When the approximation sequence converges, the function returns an instance of class Results containing information about the final result and the sequence of triples. The C++ code does not have code equivalent to this class.

using System;
using System.Collections.Generic;

namespace SBTlib
{
   /// <summary>Class to encapsulate the results of a rational appproximation. 
   /// </summary>
   public class Results
   {
      int numerator, denominator;

      double number, approx, error;

      List<Tuple<int,int,double>> sequence;

      public Results( int p, int q, double x, double _approx, 
                      List<Tuple<int,int,double>> _sequence )
      {
         numerator = p;
         denominator = q;
         number = x;
         approx = _approx;
         error = x - _approx;
         sequence = _sequence;
      }// Results (constructor)

      public int Numerator { get { return numerator; } }
      public int Denominator { get { return denominator; } }

      public void Display( int decPlaces )
      {
         if ( sequence.Count > 0 )
         {
            Console.WriteLine( "\nRational approximation to {0}\nwith {1} decimal places:\n",
                               number, decPlaces );

            string formatStr
               = "{0,4}/{1,4} == {2," 
                 + ( decPlaces + 5 ).ToString() + ":F" + decPlaces.ToString() + "}";

            foreach ( Tuple<int, int, double> tuple in sequence )
            {
               Console.WriteLine( formatStr, tuple.Item1, tuple.Item2, tuple.Item3 );
            }

            Console.WriteLine( "\nFinal result:\n" );
            Console.WriteLine( formatStr, numerator, denominator, approx );
            Console.WriteLine();
         }
      }// Display
   }// Results (class)
}// SBTlib (namespace)

Class Results provides a function Display to display the results on a command-prompt window when used by a console application.

Implementing the Library

The ZIP file contains three files that implement the library: SBTnode.cs, SBTree.cs, and Results.cs. In Visual Studio, create a new Visual C# Class Library with the name SBTlib. In the Solution Explorer, right-click on the default class name chosen by Visual Studio (usually Class1.cs), re-name it as SBTnode.cs and copy the code from file SBTnode.cs. Right-click on the solution name and select Add->New Item. In the menu that appears, select Class, name it SBTree.cs and copy the code from file SBTree.cs. In the Solution Explorer, right-click on References and select Add Reference. Select the .NET tab and add a reference to the library System.Windows.Forms. Right-click on the solution name and select Add->New Item. In the menu that appears, select Class, name it Results.cs and copy the code from file Results.cs. Build the solution and the bin\Debug directory will contain the library file SBTlib.dll.

Testing the Library

The following simple console application, also included in the attached ZIP file as Program.cs, can be used to test the library. The code defines a single SBTree and contains four test cases. The first two tests provide valid floating-point numbers and the last two provide invalid numbers.

using System;

using SBTlib;

namespace TestSBTlib
{
   class Program
   {
      static void Main( string[] args )
      {
         SBTree tree = new SBTree();
         Results results;

         results = tree.Approximate( 3.14159265359, 6 );
         results.Display( 6 );

         tree.Reset();

         results = tree.Approximate( 0.56, 6 );
         results.Display( 6 );

         tree.Reset();
         results = tree.Approximate( 0.0, 6 );
         results.Display( 6 );
         tree.Reset();
         results = tree.Approximate( -5.67, 6 );
         results.Display( 6 );
      }
   }
}

Observe the calls to function SBTree.Reset between successive tests.

To use the code, create a console application and name it TestSBTlib. In the Solution Explorer, right-click on References and select Add Reference. Select the Browse tab, navigate to the bin\Debug directory of the library and select the file SBTlib.dll generated in the previous section. Copy the code from file Program.cs. Build the solution and start it without debugging. The first two tests produce the results shown in the following figure:

The last two tests produce the MessageBox windows shown in the following two figures, and no resuts are displayed in the command-prompt window.

Practical Use of the Library

As a second simple example of the use of the library, consider an application dealing with quantum computing (which the author is presently working on). The states of any quantum computational system through time are represented by arrays containing probability amplitudes (or just probabilities). Each array corresponds to a particular instant of time. Any further discussion of quantum computational systems and probability amplitudes is beyond the scope of this article. The important point is that a probability can be specified either as a rational number (explicit numerator and denominator) or as a fraction (a floating-point number between 0.0 and 1.0). To handle those two representations, it is convenient to define a class as follows.

The class has four private data members: an instance of a Stern-Brocot tree (SBTree), two int members for the numerator and the denominator of a rational number, and a double member for the fraction equivalent to the rational number. Thus the class maintains both representations of a probability value.

class Probability
{
   private SBTree tree = new SBTree();

   private int _numerator,
               _denominator;
   private double _fraction;

The first constructor handles the first representation. It receives two arguments, the numerator and the denominator, and generates the second representation.

/// <summary>Create an instance of Probability class, using
///          the explicit arguments if the first is positive
///          and the second is not 0.
/// </summary>
/// <param name="numerator">Numerator of a rational number.</param>
/// <param name="denominator">Denominator of a rational number.
/// </param>
public Probability( int numerator, int denominator = 1 )
{
   _numerator = 0;
   _denominator = 1;

   if ( numerator >= 0 && denominator > 0 )
   {
      _numerator = numerator;
      _denominator = denominator;
   }
   _fraction = (double)_numerator / (double)_denominator;
}// Probability (constructor)

The second constructor handles the second representation. It receives a fractional probability value, and then uses the SBTree.Approximate function to compute the rational number that approximates the fraction if it is not equal to either of the two trivial values 0.0 or 1.0 (those values are identified by functions from a static utility class). From the approximation, the components of the first representation can be set. Every time the second constructor needs to compute an approximation, it calls function SBTree.Reset to reinitialize its private data member tree.

/// <summary>Create an instance of Probability class when
///          the numerator and denominator are unknown.
/// </summary>
/// <param name="fraction">Fractional probability.
/// </param>
public Probability( double fraction )
{
   _fraction = fraction;

   if ( Util.IsZero( fraction ) )
   {
      _numerator = 0; _denominator = 1;
   }
   else if ( Util.IsOne( fraction ) )
   {
      _numerator = 1; _denominator = 1;
   }
   else
   {
      tree.Reset();

      Results results = tree.Approximate( fraction, 6 );

      _numerator = results.Numerator;
      _denominator = results.Denominator;
   }
}// Probability (constructor)

Finally, the class provides three get properties and two functions to convert the probability to a short string and to a long string.

   // Get-properties.

   public int Numerator { get { return _numerator; } }
   public int Denominator { get { return _denominator; } }
   public double Fraction { get { return _fraction; } }

   public override string ToString()
   {
      return String.Format( "{0,2}/{1}", _numerator, _denominator );
   }// ToString

   public string ToLongString()
   {
      return String.Format( "{0} (== {1,4:F2})", ToString(), _fraction );
   } // ToLongString
} // Probability (class)

The results from the second valid test case in the previous section correspond to the approximation of the probability value 0.56 by the second constructor of this class.

Conclusion

This article has dealt with the implementation, testing, and practical use of a C# library implementing Stern-Brocot trees. The library can be used by any managed-code Visual Studio application requiring the arbitrary-precision, rational-number approximation of positive floating-point numbers.

History

• 30^th April, 2021: Initial version