实现 Stern-Brocot 树的 C# 库
5.00/5 (3投票s)
在 C# 中实现 Stern-Brocot 树
引言
Stern-Brocot 树以 Moritz Stern 和 Achille Brocot 的名字命名，他们独立发现了这些树。Stern-Brocot 树是一个无限的、完整的二叉搜索树，其节点与正有理数一一对应，并用于找到任意浮点数的最接近有理近似值。以下图表取自维基百科，展示了一个部分的4级 Stern-Brocot 树。
存储在每个节点中的有理数使用以下简单规则计算。给定父节点的左子节点中存储的值等于父节点中的值加上子节点左侧垂直线上的有理数。然而，这些加法不是以普通有理数算术执行，而是简单地通过添加相应的分子和分母。例如，根节点下树最左侧分支上的有理数是：(1+0)/(1+1) = 1/2，(1+0)/(2+1) = 1/3，(1+0)/(3+1) = 1/4。同样，2/3 父节点的左子节点包含有理数 (2+1)/(3+2) = 3/5。对于父节点的右子节点，它们包含父节点中的有理数加上它们右侧垂直线上的有理数。例如，根节点下树最右侧分支上的有理数是：(1+1)/(1+0) = 2/1，(2+1)/(1+0) = 3/1，(3+1)/(1+0) = 4/1。同样，3/2 父节点的右子节点包含有理数 (3+2)/(2+1) = 5/3。所有这些加法的结果称为中介数。通常，给定两个有理数 p1/n1 和 p2/n2，它们的中介数是 (p1 + p2)/(n1 + n2)。
通过 C# 库实现 Stern-Brocot 树
将要描述的 C# 代码主要基于 Mircea Neacsu 于 2016 年编写并于 2021 年 3 月 22 日发布在 The Code Project 上的非托管 C++ 代码。（请参阅 Stern-Brocot 树及其应用。）为便于参考，C++ 代码中所有函数的名称都保留在 C# 库中，但有一些额外的函数是原创的。该库不实现 C++ 代码提供并按需使用的素因子分解。库的所有代码都在 SBTlib 命名空间中定义。
Stern-Brocot 树节点
Stern-Brocot 树的基本数据结构由一个类定义，用于实现其节点。一个节点包含两个整数 _p 和 _q，分别对应于有理数的分子和分母，以及对其左右子节点和其父节点的引用。根据定义，树的根节点的父节点为 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 树
实现 Stern-Brocot 树的类将逐步描述。完整代码在文章随附的 ZIP 文件中。首先，类必须提供一个构造函数。
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
C++ 代码不包含树的类，因为节点是通过 struct 实现的。SBTree 类构造函数简单地调用 Reset 函数来初始化（或重新初始化）树的根节点。根节点的父节点设置为 null，根节点的分子和分母设置为 1，并调用 Grow 函数来初始化根节点的子节点。
/// <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
重要的是要观察到，作为无限二叉搜索树，Stern-Brocot 树没有完全实现。它们在搜索浮点数的有理近似值时按需增长。这就是 Grow 函数的目的。
以下两个函数 Previous 和 Next 用于在增长左右子节点时，这些子节点是它们的父节点以及它们的前一个或下一个节点的中介数。
/// <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
C++ 代码在其主函数中计算浮点数的有理近似值。由于 C# 代码实现了一个库，因此不能有 Main 函数。因此，它提供了一个函数来计算近似值。
// 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
Approximate 函数首先检查浮点数是否为非正数。如果是，它会显示一个适当的 MessageBox 并返回一个空的近似序列。
private bool NotPositive( double x )
{
string str = x.ToString();
return str.StartsWith( "-" ) || str.Equals( "0" );
}// NotPositive
}// SBTree (class)
}// SBTlib (namespace)
鉴于浮点数的精确比较（尤其是与 0.0 的比较）不可靠，NotPositive 函数将浮点数转换为 string 并检查该数字是负数还是 0.0。
Approximate 函数使用定义为 List<Tuple<int, int, double>> 的三元组序列记录连续的近似值，其中前两个元素是有理数的分子和分母，第三个是相应的浮点近似值。当近似序列收敛时，函数返回一个包含最终结果和三元组序列信息的 Results 类实例。C++ 代码没有与此等效的类。
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)
Results 类提供了一个 Display 函数，用于在控制台应用程序使用时在命令提示符窗口中显示结果。
实现库
ZIP 文件包含三个实现库的文件：SBTnode.cs、SBTree.cs 和 Results.cs。在 Visual Studio 中，创建一个名为 SBTlib 的新 Visual C# 类库。在解决方案资源管理器中，右键单击 Visual Studio 选择的默认类名（通常是 Class1.cs），将其重命名为 SBTnode.cs 并从文件 SBTnode.cs 复制代码。右键单击解决方案名称并选择添加->新项。在出现的菜单中，选择类，将其命名为 SBTree.cs 并从文件 SBTree.cs 复制代码。在解决方案资源管理器中，右键单击引用并选择添加引用。选择 .NET 选项卡并添加对库 System.Windows.Forms 的引用。右键单击解决方案名称并选择添加->新项。在出现的菜单中，选择类，将其命名为 Results.cs 并从文件 Results.cs 复制代码。构建解决方案，bin\Debug 目录将包含库文件 SBTlib.dll。
测试库
以下简单的控制台应用程序，也包含在附件的 ZIP 文件中作为 Program.cs，可用于测试该库。代码定义了一个单一的 SBTree 并包含四个测试用例。前两个测试提供有效的浮点数，后两个提供无效的数字。
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 );
}
}
}
请注意连续测试之间对 SBTree.Reset 函数的调用。
要使用此代码，请创建一个控制台应用程序并将其命名为 TestSBTlib。在解决方案资源管理器中，右键单击引用并选择添加引用。选择浏览选项卡，导航到库的 bin\Debug 目录并选择上一节中生成的 SBTlib.dll 文件。从文件 Program.cs 复制代码。构建解决方案并在不调试的情况下启动它。前两个测试产生如下图所示的结果：
最后两个测试生成了以下两图所示的 MessageBox 窗口，并且命令提示符窗口中没有显示任何结果。
库的实际应用
作为库使用的第二个简单示例，考虑一个处理量子计算的应用程序（作者目前正在研究）。任何量子计算系统随时间的状态都由包含概率幅（或仅概率）的数组表示。每个数组对应于一个特定的时间瞬间。关于量子计算系统和概率幅的进一步讨论超出了本文的范围。重要的一点是，概率可以指定为有理数（明确的分子和分母）或分数（0.0 到 1.0 之间的浮点数）。为了处理这两种表示，方便定义一个如下的类。
该类有四个 private 数据成员：一个 Stern-Brocot 树的实例 (SBTree)，两个用于有理数分子和分母的 int 成员，以及一个用于等效于有理数的分数的 double 成员。因此，该类维护概率值的两种表示。
class Probability
{
private SBTree tree = new SBTree();
private int _numerator,
_denominator;
private double _fraction;
第一个构造函数处理第一种表示。它接收两个参数，分子和分母，并生成第二种表示。
/// <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)
第二个构造函数处理第二种表示。它接收一个分数概率值，然后使用 SBTree.Approximate 函数计算近似该分数的有理数，前提是它不等于两个平凡值 0.0 或 1.0（这些值由静态实用程序类中的函数识别）。从近似值中，可以设置第一种表示的组件。每次第二个构造函数需要计算近似值时，它都会调用 SBTree.Reset 函数来重新初始化其 private 数据成员树。
/// <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)
最后，该类提供了三个 get 属性和两个函数，用于将概率转换为短 string 和长 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)
上一节中第二个有效测试用例的结果对应于此类的第二个构造函数对概率值 0.56 的近似。
结论
本文讨论了实现 Stern-Brocot 树的 C# 库的实现、测试和实际使用。该库可用于任何需要正浮点数任意精度、有理数近似值的托管代码 Visual Studio 应用程序。
历史
- 2021年4月30日：初始版本