Conway超现实数算法及可视化工具：实现与应用

{|}--|}≥SoftwareX 9（2019）293原始软件出版物几乎超现实：朱莉娅的超现实算术马修·罗汉ARC数学统计前沿卓越中心（ACEMS），阿德莱德大学数学科学学院，阿德莱德，5005，澳大利亚ar t i cl e i nf o文章历史记录：2018年9月26日收到收到修订版，2019年1月17日接受，2019年a b st ra ct本文给出了一个关于Conway超实数的算法实现。它还提供了以图形可视化形式可视化复杂超现实的工具，并通过几个例子说明了它们的使用，以及对超现实理论的一个小贡献©2019作者由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本v0.1.1永久链接到代码/存储库使用的此代码版本https://github.com/ElsevierSoftwareX/SOFTX_2018_184法律代码许可MIT使用git的代码版本控制系统使用Julia、GraphViz的软件代码语言、工具和服务编译要求、操作环境依赖性Julia v0.6、v0.7、v1.0和GraphViz v2.38（用于可视化）如果有开发人员文档/手册https://github.com/mroughan/SurrealNumbers.jl问题支持电子邮件matthew. adelaide.edu.au1. 介绍超现实数是由约翰·康威（John Conway）发明的，并由克努特（Knuth）在《超现实数：两个前学生如何转向纯数学并找到完全的幸福》（Surreal Numbers：How Two Ex-Students Turned on toPure Mathematics and Found Total Happiness’）中命名它们之所以吸引人，是因为它们为我们所熟悉的所有数--实数、有理数、超实数和序数--提供了一个单一的结构，而这仅仅是使用了集合论。因此，它们提供了一个关于数字到底是什么的基本概念。 它们优雅而复杂的结构学习本身。超实数的定义是递归的：超实数x由两个超实数集合（分别称为左集合和右集合）的有序对组成，使得左集合中没有任何成员是右集合中的任何成员。 我们写x XL XR为这样一个超现实主义。递归的起点是（其中是空集E）。仔细阅读定义可以看出，电子邮件地址：matthew. adelaide.edu.au。https://doi.org/10.1016/j.softx.2019.03.005其中一个的元素不能≥另一个，因为没有元素，所以比较自动为真。我们称之为初始值0。然后，在“第一天”，第一代超现实可以创建，建立在0。第二天，我们创建了第二代，以此类推，每一个都有与传统数字一致的含义，关于标准的数学运算符，如加法。有很多关于超现实主义的作品，例如， [1- 6 ]。康威和许多后来的研究人员似乎主要感兴趣的是他们作为一个组成部分的组合博弈论[1]。一些研究旨在更深层次的分析问题。然而，这些作品一般没有详细研究数字本身。尽管该理论的某些组成部分很复杂，但除了一个小的基本集合之外，它们没有给出任何例子。但举例是教授复杂思想的关键手段。 我们需要他们，但我们没有。为什么不呢？这一不足源于计算的复杂性，但也源于难以想象结果。这里介绍的软件包通过超现实的实现和图论的可视化来解决这些问题。2352-7110/©2019作者。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx294M. Roughan/SoftwareX 9（2019）293=联系我们===2K2K2K我们在新的编程语言Julia [8]中实现了Julia应该是这个任务的理想选择，因为它允许动态类型，脚本和其他功能，这些功能使它可以轻松高效地使用，但同时允许开发超现实所需的严格类型定义，并且它的目标是非常高效。俗话说Julia也是免费和开源的。随着最近Julia 1.0的发布，了解它是否符合其炒作似乎很有趣。在这个项目中使用Julia的经验几乎是完全积极的。超现实算术涉及深度递归和复杂的内存使用，虽然我们没有一个很好的基准来比较，但代码的性能此外，与Julia的一些主要竞争对手相比，编写代码是一种更愉快的体验。例如，该语言具有一些优雅的功能，可以自动扩展函数的实用性，例如从标量到向量。通过朱莉娅，我们可以更详细地探索超现实的数字。除了这个设施的教育价值外，它还允许构建关于超现实的新假设，突出了计算机科学和数学之间的良性关系。我们在这里探索一个小例子最后，超现实的所有操作的深度递归使得它们在计算上具有挑战性。我们用一个乘法表来说明这一点，该乘法表显示了操作的计算成本增长的速度。这就提出了我们未来如何改进算法的问题。2. 超现实的数字有几个很好的教程或书籍的超现实数字-Fig. 1. 一个DAG描绘了1。每个框表示一个超现实的数字，其值在顶部部分中给出，左和右集合显示在左下和右下部分中，红色和蓝色箭头分别显示了到每个父窗体的链接。例如，序数），但这里我们只考虑具有有限表示S的超实数，即所谓的短数[10，Def 2.24]。这些超实数是一个重要而有用的子集，因为它们对应于二进数D，D是以下形式Xn，2K其中n和k是整数。更明确地说，每个短超现实都有一个具有相同值的二元实数[6，p.27]，并且每个二元实数都可以映射到一个短超现实。标准映射被称为Dali函数[3]，并由d：D→S递归定义，其中我们的团队|如果x=0，Bers，例如，[1特别是Tøndering [3]和Simons [6]，为超现实主义者提供了极好的免费介绍。一个超现实的数字与它的“形式”交织在一起这是最好d（x）d=efd（n− 1）|如果x= n，一个正整数，{\fnSimHei\bord1\shad1\pos（200，288）}|d（n+1）}， 如果x=n，是一个负整数r，重要的是，在许多文献中，如果x=n，则{d（n−1）<$d（n+1）}对于k>0，n为奇数。可以用有理数来解释我们能想到任何给定的有理数的形式p/ q，但2p/ 2qp/q，即，有两种形式具有相同的值。事实上，有无限多的有理数形式与任何给定的值。我们通常称之为同一个“数”。在这里，我们实现超现实的形式，因为它是在这些方面，康威的超现实算术运算符的定义。Keddie [9]称两种形式相同，如果它们是相同的（即，有相同的左和右集合），如果它们有相同的值，则相等。我们将用价值相等来区分这两种情况这个工具箱对二元数的限制可能看起来很重要，但是（a）二进制数在实数上是稠密的，（b）浮点数在计算机中被表示为二进制数。因此，短超现实是一个实用的子集。然而，并矢并不构成一个域，也就是说，乘法逆元并不存在于所有情况下，因此任意的除法是不可能的。由于每个数实际上是一个等价的形式类，我们通常需要更具体地说明我们所指的是哪种形式。大理的建筑是独特的，而且往往很重要，所以我们把这些超现实的形式称为规范形式，并将其定义为作为等价物，和同一性。一个等号将表示赋值。b{y将a}行置于数字上方，例如，d（1）d=ef1d=ef{0|}=={|} |∅我们用小写字母表示数字，用大写字母表示集合，X L和X R是x的左集合和右集合的约定，并将形式写成x= {X L|X R}。省略空集是很常见的，但我们更喜欢显式地写空集合，因为当. 回到有理数的类比，标准型类似于用最小值表示的有理数。术语，即，形式p/ q，其中p和q是没有任何公因数的整数。规范形式的其他示例包括写出复杂的序列传统算术的运算：比较、加法、乘法等都是为超现实形式定义的[1，3，6]。该工具包实现了所有常见操作，d（−1）d=efd（2）d=efd（1/2）d=ef−1=={|0}，2=={1|}，二分之一==第0个|1}，任意划分（原因见下文）。超现实形式的左集和右集可以是无限的，这导致了超现实数字的许多有趣方面（1 该工具包（v0.1.1）在MIT许可下发布，可在https://github.com/mroughan/SurrealNumbers.jl上获得。它适用于Julia 0.6，0.7和1.0，并已在各种版本的Linux和MacOS下进行了测试，并已除了Graphviz工具箱[7]之外，没有其他依赖关系，该工具箱仅用于生成图形的插图注意每一个都是根据先前的定义来定义的。达利结构为最简单的形式搭建了一个脚手架（对于一个给定的数字），但即使如此，它也会很快导致复杂的表达，因此我们需要一种方法来说明超现实的形式。我们这样做的图片，如图。1.一、该图将每个超现实显示为图形中的节点。特别是，它是一个连通的有向无环图（DAG），尽管DAG本身会丢失信息。该图将只指定父节点，而不是左节点，M. Roughan/SoftwareX 9（2019）293295{−|{\fnMicrosoftYaHei}≤ {−|个文件夹联系我们|}∈ ≤∈≤≤- ≤{−|联系我们联系我们{−|{\fnSimHei\bord1\shad1\pos（200，288）}|}=====≥≤∅⌊ ⌋===∅ ∅==≥= ∈ [+正确的父母。因此，在显示DAG时，我们为每个超现实数字显示一个框，顶部给出值，输入：x= {X L|X R}输出：m= mxm在左下和右下部分中示出的左组和右组i=0时（i+1）分别左、右父节点由红色和蓝色箭头表示。附加的示例示于图1中。二、第一种形式相当于零，即， 11.为了理解为什么它们是等价的，我们需要理解超实数的定义。 Conway [1]定义xy表示没有成员x LX L使得yx L，也没有成员y RY R使得y Rx。在这个例子中，y是，它只有空集，所以没有成员yR要处理，因此我们只需要注意，10看到110. 然后我们把这个关系翻转过来，看到也是0 1 1，把两个不等式结合起来，我们得到1 1 0。注意，在上面的计算中，我们不需要将自己限制在标准形（用上划线表示的那些），因为这些陈述对1和0的任何形式都是正确的，但是标准形和超实数（由一类形式组成，标准形只是其中之一）之间的区别是下面要注意的重要区别。图中的图表。图2（a）显示了一个值可以在形式结构中的多个位置重新出现：在这种情况下，值为0的超现实出现在DAG的顶部和底部。描述超现实形式的信息不是它的值，甚至不是它的子集的值，而是描述它的DAG的整个结构。所以图中的两个下一个例子，如图所示。2（b），给出了Dali构造3/2的DAG：三分之二==12== {|} |∅|我的天|}|}|-是的图图2（c）和（d）显示了由简单算术得出的3/2的另外两种构造。我们可以看到算术是如何迅速地增加了结果形式的复杂性。这里的一个核心目标是能够玩这样的算术，以获得更好的理解超现实的数字。从例子中我们可以看出，图是理解超现实形式的一种更好的方式，而不是一系列复杂的括号和空集。例如，我们可以看到，图2（a）、（b）和（c）中出现的1是相同的形式，但（d）中的1有两种不同的形式：一种是标准形式1（出现在图的底部附近），另一种出现在从顶部开始的第三行。3. 在Julia这项工作的目标是详细探索超现实的数字形式。在各种编程语言中有几种超现实的实现[11其中大部分都是不完整的。例如，大多数只处理整数，例如，[14，17]和/或有相当有限的设施[16]。也许最完整的是Mamane的Coq [13]，但这是为了证明超现实的性质，而不是探索数字本身。此外，这些软件包都没有试图可视化复杂的超现实输出。选择Julia作为编程语言的目的是为了有一个工具来探索超现实，因此解释语言是首选。然而，即使是最简单的操作的递归也意味着计算效率是一个问题。Julia声称提供了类似C的计算性能，以及适合探索的动态REPL（超现实数字似乎是对新语言的一个有趣的测试。而x2则i i + 1//指数搜索以形成边界区间端a2i; b2i+1 //对区间进行二进制搜索 2i，2i+1）对于j 1到i，做中点（a+b）/2，如果x是中点，则usingSurrealNumbersjulia>x0=SurrealShort（“0”，，）julia>x1 = SurrealShort（“1”，[x0]，）julia>x1_alt =convert（SurrealShort，1）julia>x1 == x1_altjulia>surreal2dag（x1）296M. Roughan/SoftwareX 9（2019）293×·×··×图二. DAG描绘了超现实数字的形式。 请注意，存在等效形式，例如，{|} |1}，在表单中。语句x1 == x1_alt测试两个alter- native构造是否相同;它返回true，因为两者都是规范的。最后一条语句创建DOT输出，以输入到GraphVis程序[7]，该程序可以对DAG的节点进行实现的某些方面可能是意想不到的。首先，Julia有一个Set类型，可用于根据定义实现表单，但SurrealShort结构使用超实数的排序数组。 这使得我们可以用O（NM）算法来代替比较操作，用O（1）操作的超现实（这里所说的顺序是在根级别的初始比较的数量，每个比较都需要递归计算，因此降低复杂性比看起来更重要）。比较经常被使用，因此加速这些结果会大大提高整体性能。其次，SurrealShort结构被实现为一个mu- table类型.当使用不可变类型时，Julia可以创建更快的代码，但是将哈希值放在类型本身中避免了（递归）每个表单多次计算哈希，这提高了我们测试中的性能。4. 超现实算术这项工作的目的至少部分是为了能够产生更多的超现实算术的例子。下面是一些小的例子：例如，julia>x =dali（1）+dali（1/2）julia>expand（x;level=2）给出以下结果（expand命令将其完整写入）1 + 1/2 =={0}}|}|我的天|}|}}，我的天|}|}|关于我们|}|}|{\fn黑体\fs19\bord1\shad1\1cHD8AFAF\4cHC08000\b0}}.这种表达的复杂性阻碍了我们的理解，因此我们在图中将形式显示为DAG。 2（c）.乘法同样可以探索，但这些变得更加复杂：例如julia>x = dali（2）* dali（2）julia>expand（x;level=2）导致2×2 == {{{{{{∅|{∅ |∅}} |{{∅|∅}|∅}} |{{{∅| ∅} |∅}|∅}} |{{{{∅|}|}|}|}}|{{{{{∅|}|}|}|}|}}|{\fn方正黑体简体\fs18\b1\bord1\shad1\3cH2F2F2F}.这是以前发表的最复杂的例子[19]。乘法的复杂性增长得非常快，所以没有看到更复杂的结果也就不足为奇了。我们可以在图3和表1中看到DAG形式的复杂性增加，图3显示了2 3，表1显示了简单乘法的示例，说明了计算时间的增长率。2例如，该表显示了根据节点和边的数量得到的DAG的大小，如s（）和e（）。分别 它们呈指数增长。该表还说明了结合缓存的DAG表示的重要性如果使用简单的递归进行计算，这将与将这些结构视为树相同通过这些递归将与跟踪从根节点到0的通过DAG的所有路径相同。这样的路径的数量由表中的p（）给出。记住，递归操作是根据其他递归操作定义的，因此这种增长意味着如果没有DAG表示，即使像3 3这样的计算也是不切实际的。我们可以在Haskell的超现实数包[15]中明确地看到这一点，它使用乘法的直接定义。Haskell代码实际上在最小的情况下更快，因为它避免了缓存开销，但计算负载增长得如此之快，以至于它无法计算3 3：尝试执行计算的进程增长到消耗80 GB RAM（此机器上单个进程的签名内存限制），2 使用Julia的@timed宏在运行在3.2 GHz的Linux Mint v18 Inteli7-6900 K计算机3 Julia和Haskell中的计算时间比较应该是这是因为（i）它们使用不同的计时机制（Julia使用@timed宏，Haskell使用criterion包[20]），以及（ii）Haskell使用惰性评估，因此为了查看性能，我们必须触发评估，在这种情况下，这会导致少量的开销不包括在内茱莉亚的密码M. Roughan/SoftwareX 9（2019）293297×+····++- -|个文件夹×表1超现实形式简单乘积的规模与计算特征。DAG的层代（或深度）g（）和大小（以节点数s（）表示）且给出边e（）。从图的根开始的路径数的计算在p（）中给出。计算时间（以秒为单位）和还报告了独特的超现实加法、乘法和构造运算。并不是所有的计算都会导致表单的构造，因为有些计算是“短路”的。x×y测量结果表单的大小时间（s）操作g（xy）s（xy）e（xy）p（xy）Julia Haskell [15]+ ×构造1×3 3 4 3 1 0.00001 0.000001 3 7 32× 3 12 45 82 625 0.00028 0.0004 83 9 693×3 31 737 2052 9.4E+10 0.13- 3419 10 31824×3 64 16958 64653 6.1E+27 120.5- 286358 14 2817755×3 115 430591 2094360 2.8E+37 102553.0- 22024924 18 21919195早期Julia直接实现乘法也遭遇了同样的命运，所以这不是编程语言的问题）。核心问题是，即使我们缓存计算结果，也有许多计算导致相同的超现实形式，但没有缓存。例如，在计算2 4时，我们得到了一个8的形式，它的祖先是5，但是在乘积中有多个不同的计算，得出了相同的5形式：5==（（3+（（2+ 2）+ −1））+ −1）==（2+（（1+（2+2））+ −（1+1）==（4+（（1+2）+ −（1+1）==（（3+（2+2））+ −（1+1））==（3+（（2+2）+ −（1+1）。缓存避免了多次执行，并且可以完全移动一些计算：例如，可交换性意味着我们可以在计算y时缓存y。使用交换性和其他技巧，我们节省了许多重复的计算，尽管必须小心，因为许多报告的超现实算术的性质是算术的值，而不是形式。例如，0的非0形式是超实数的加法恒等式，但不是形式的加法恒等式，这一事实现在可以用工具包快速验证。然而，即使上面所有的5的表达式都有相同的结果，我们也不能提前缓存，因为在执行计算之前，我们不知道结果。这是不是繁重的情况下上述，但作为规模的超现实形式图三. 2 3的形式。请注意，在这些中，我们经常看到表面上看起来相同的形式，例如，4 35出现了三次，但这些都是不是相同的形式，这是隐含在DAG从他们下降没有结果就被终结了乘法的唯一其他实现[11，14]使用相同的直接实现。具有讽刺意味的是，在编译和测试后阅读Haskell实现中的注释时，我们发现了这样一句话缓存允许我们重用子组件，从而更快地执行计算。缓存的有效性可以在表1的最后三列中看到4缓存multiplica-大大减少了他们的数量。然而，乘法是以这样一种方式定义的，它的输出然后在许多组合中用作求和的操作数，导致最终DAG中不同超现实形式的爆炸。因此，计算成本仍然增长非常迅速。问题的规模增长得如此之快，以至于很难进行基准测试，而且几乎没有什么可以比较的。乘法的唯一其他例子[11，14，15]都使用直接实现，它不能解决简单的情况，如3× 3（an4 操作数是使用操作符中内置的轻量级检测来计算的，这会产生少量额外开销。增加，在这种计算中的可能性的数量扩大戏剧性地。这导致了加法运算的爆炸，以及由此产生的计算危机。改善这种情况的一种方法是进一步利用超实数的代数规则，从它们的组成部分创建更大的结果表，但要比当前的表更有价值，它们需要超越2D，因此将存在超出本文范围的复杂内存/计算权衡。5. 讨论该实现的重点是DAG结构，我们最初仅将其用作可视化辅助工具，为了使计算有效，也是重要的。然而，还有其他我们关心的问题。特别是计算速度有时会与编写代码的容易性相权衡。在朱莉娅身上实施超现实主义的经验在很大程度上是积极的。Julia提供了人们对现代编程语言所期望的所有功能，以及一些附加功能，例如将函数自动扩展为数组操作。大多数语法对于Python、R或Matlab 等 语 言 经验 丰 富 的 人 来说 都 是 很 自 然 的最 接 近 的 是Matlab，但也有一些显着的差异（一旦接受）更自然。298M. Roughan/SoftwareX 9（2019）293（）× ==×±≤≃×≤==+为||+ ≤+（）+=+然而，也有一些负面影响。最值得注意的是Julia版本的变化，包括对核心语言的突破性变化。然而，随着1.0的发布，我们希望这些将停止。这些变化也带来了很大的改进。比较计算时间为35，这些减少了从39.9从Julia 0.6到1.0的过程缩短到28.5小时，这是一个非常大的改进。另一个可以改进的体验是添加更好的工具来了解内存使用情况。与许多这样的语言一样，Julia负责内存分配和垃圾收集。它提供了一些工具来了解使用了多少内存，但在复杂的情况下，这些工具可以提供更清晰的信息。这里的部分意图也是为了展示计算和数学之间的友好关系。计算机程序可以提供例子，这些例子引出假设，最终引出新的定理。一个这样的例子涉及超现实的生日算术。超现实的构造引出了生日的概念：取0表示出生在第0天，取1表示出生在第1天，以此类推，然后我们可以为所有的超现实指定一个生日我更喜欢“一代”这个词，而不是“生日”，因为它与父母和孩子的概念联系得更清楚。在上图中，它是从DAG的顶部到底部的最长路径的长度，即，它的深度。形式上，如果我们用X P X L表示x的父母X R，那么我们可以通过数学定义超实数形式x的生成/生日函数，g（x）supg（s）1、（1）s∈ XP其中g（0）=0。 根据g（·），超现实形式x比y更简单或更古老意味着g（x）

下载后可阅读完整内容，剩余1页未读，立即下载