language-agnostic - 可构造点的坐标可以精确表示吗？

Question

我想编写一个程序，让用户可以像使用直尺和指南针一样绘制点、线和圆。那么我想能够回答这个问题，“这三点共线吗？”为了正确回答，我需要在计算点数时避免舍入错误。

这可能吗？我如何表示内存中的点？

(我查看了一些不寻常的数字库，但我没有找到任何声称提供精确算术和精确比较的东西，它们保证终止。)

Answer 1

是的。

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

基本上你需要能够计算 constructible numbers - 有理数或 a + b sqrt(c) 形式的数字，其中 a、b、c 是先前创建的(参见该 PDF 的第 6 页)。这可以通过代数数据类型来完成(例如，Haskell 中的 data C = Rational Integer Integer | Root C C C，其中 Root a b c = a + b sqrt(c))。但是，我不知道如何使用该表示进行测试。

两种可能的方法是:

可构造数是 algebraic numbers 的子集，因此您可以使用代数数。
所有的代数数都可以用多项式来表示，它们的根是多项式。这些操作是可计算的，所以如果你用多项式 p 表示一个数 a，用多项式 q 表示 b (p(a) = q(b) = 0)，那么就有可能找到一个多项式 r，使得 r(a+b ) = 0。这是在一些 CASes 中完成的，例如 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 ，然后相等、共线性等变得不可判定。