可施工点的坐标能准确表示吗?

对。

我强烈推荐 Introduction to constructions 这是一个很好的基本指南。

基本上你需要能够用 constructible numbers -合理的数字,或者A+B sqrt(c)形式的数字,其中A、B、c是先前创建的(参见该pdf的第6页)。这可以通过代数数据类型(例如 data C = Rational Integer Integer | Root C C C 在haskell中,根a b c=a+b sqrt(c))。但是,我不知道如何使用这种表示来执行测试。

两种可能的方法是:

• 可构造数是 algebraic numbers ,所以你可以用代数数。 所有代数数都可以用其为根的多项式表示。这些操作是可计算的,所以如果用多项式p表示数字a,用多项式q(p(a)=q(b)=0表示数字b,那么就可以找到多项式r,这样r(a+b)=0。在某些情况下,比如Mathematica, example . 参见: Computional algebraic number theory - chapter 4

• 使用Tarski的测试并表示数字。它很慢(大约是双指数的),但起作用:)示例:要表示sqrt(2),请使用公式x^2-2&x>0。你可以在那里写线的方程,检查点是否共线,等等。 A suite of logic programs, including Tarski's test

如果你转向 computable numbers 然后,平等、共同性等变得不可决定。

我认为唯一可能的方法是,如果你使用一个符号表示, 而不是直接表示坐标值——所以 避免试图将sqrt(2)等值强制为某种数字格式。你会 处理二进制中不可有限表示的无理数, 十进制或任何其他位置符号。

展开 吉姆·刘易斯 稍微回答一下,如果你想用精确的算术运算对整数上可构造的点进行运算,你需要能够对形式的表示进行运算:

a + b sqrt(c)

其中a、b和c是有理数,或者用上面给出的形式表示。 Wikipedia 有一篇关于什么观点是可构建的主题的相当不错的文章。

回答与这些表示完全相等的问题(如有必要建立共线性)是一个相当棘手的问题。

如果你试图比较你的观点的坐标,那么你就有问题了。先撇开线性关系不谈,先弄清楚两点是否相同如何?

假设一个给出了坐标,另一个是从其他坐标开始的罗盘直尺结构,你想确定它们是否是同一点。无论哪种方法都是欧几里得几何定理,它不是你可以测量的东西。你可以通过在坐标中发现一些差异来证明它们是不一样的(例如,通过计算每个坐标的小数点,直到你遇到差异为止)。但一般来说,要证明它们是相同的,不能用近似的方法。计算任意小数位数的某些展开式 1/sqrt(2) 和 sqrt(2)/2 你可以证明他们非常亲密,但你永远也不能证明他们是平等的。这需要代数(或几何)。

同样,为了证明三个点是共线的,你需要定理证明软件。用A、B、C三个点的构造表示它们,并试图证明“A、B、C是共线”定理。这是非常困难的-你的程序将证明一些定理而不是其他定理。更简单的方法是要求用户提供一个证明它们是线性的,然后验证(或反驳)该证明,但这可能不是您想要的。

一般来说,可构造点可能具有任意复杂的符号形式,因此必须使用符号表示来精确地处理它们。正如StephenCanon上面提到的,您经常需要A+B*sqrt(C)形式的数字,其中A和B是有理数,C是整数。这种形式的所有数字在算术运算下形成一个闭集。我已经写了 some C++ classes (请参见Rational_Radio1.h)如果您只需要这些数字,就可以使用它们。

也可以构造一些数,这些数是根式有理倍数的任意个项的和。当处理一个以上的半径时,这些数字在乘法和除法下不再是闭合的,因此需要将它们存储为可变长度的有理系数数组。然后,操作的时间复杂性将是术语数量的二次型。

更进一步,您可以构造任何给定数字的平方根,这样您就可能有嵌套的平方根。在这里,表示必须是树形结构来处理根层次结构。虽然很难实现,但原则上没有任何东西阻止您使用这些表示。我不确定可以构造哪些额外的数字,但在某一点之后,您的符号表示将具有足够的表现力来处理非常大的数字类。

补遗

找到这个 Google Books link .

如果网格轴是整数值的,那么答案是相当直接的,这些点不是完全共线就是不共线。

但是,通常情况下,我们使用实数(好的,浮点),然后在屏幕上绘制整数空间中存在的舍入值。在这种情况下,您别无选择,只能选择一个公差并使用它来确定共线性。保持小尺寸,用户永远不会知道区别。

实际上,你似乎在问,“计算机使用的普通数学(整数或浮点)能否完美地表示实数,而不存在舍入误差?”当然,答案是“不”。如果你想要理论上的正确性,那么你将陷入一个更困难的问题,那就是符号操作和编码相当于几何中的推论。(简而言之,我同意上面的史蒂夫·杰索普的观点。)

有些想法希望能有所帮助。

你所说的那种结构需要乘法和除法,这意味着为了保持精确性,你必须使用有理数,而有理数通常很容易在一个合适的大整数(即无界量)上实现。(公共lisp有这些内置的,必须有其他语言。)

现在,你需要表示任意数的平方根,这些必须混合在一起。

因此,一个数就是:一个有理数,一个有理数乘以一个有理数的平方根(或者,也可以只是一个有理数的平方根),或者一个数的和。为了证明任何东西,你必须把这些数字转换成某种规范的形式,尽管我可以马上计算出来,但这可能会很烦人,而且计算起来也很昂贵。

这当然意味着用户将被限制在合理的点上,不能使用任意的旋转,但这可能并不重要。

我建议不要试图把它说得非常准确。

第一个原因是你在这里问的,舍入误差,以及浮点计算的所有东西。

第二个问题是,当鼠标和屏幕使用整数时,必须对输入进行取整。所以,最初所有用户输入都是整数,而您的输出是整数。

此外,从可用性的角度来看,在另一个点的附近(例如,在一条线中)单击更容易,并且界面认为您正在单击该点本身。