可构造点的坐标可以精确表示吗?

问题描述

我想编写一个程序，让用户可以像用直尺和圆规一样绘制点、线和圆.然后我希望能够回答这个问题，这三个点是共线的吗?"为了正确回答，我需要在计算分数时避免舍入误差.

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

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

解决方案

是的.

我强烈推荐Introduction to constructions，这是一本很好的基础指南.p>

基本上，您需要能够使用 可构造数 进行计算 - 要么是有理数，要么是有理数，或 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)).但是，我不知道如何使用该表示执行测试.

两种可能的方法是:

• 可构造数是代数数的子集，因此您可以使用代数数.所有代数数都可以用以它们为根的多项式来表示.这些操作是可计算的，所以如果你用多项式 p 表示数字 a，用多项式 q (p(a) = q(b) = 0) 表示数字 b，那么就有可能找到一个多项式 r，使得 r(a+b) = 0.这是在一些 CAS 中完成的，例如 Mathematica，example.另见:计算代数数论 - 第 4 章

• 使用 Tarski 的测试并表示数字.它很慢(双指数左右)，但有效:) 示例:要表示 sqrt(2)，请使用公式 x^2 - 2 &&x > 0.您可以在那里为线编写方程，检查点是否共线等.请参阅 一套逻辑程序，包括塔斯基的测试

如果你转向可计算数，那么相等性、共线性等就变得不可判定了.p>

I'd like to write a program that lets users draw points, lines, and circles as though with a straightedge and compass. Then I want to be able to answer the question, "are these three points collinear?" To answer correctly, I need to avoid rounding error when calculating the points.

Is this possible? How can I represent the points in memory?

(I looked into some unusual numeric libraries, but I didn't find anything that claimed to offer both exact arithmetic and exact comparisons that are guaranteed to terminate.)

解决方案

Yes.

I highly recommend Introduction to constructions, which is a good basic guide.

Basically you need to be able to compute with constructible numbers - numbers that are either rational, or of the form a + b sqrt(c) where a,b,c were previously created (see page 6 on that PDF). This could be done with algebraic data type (e.g. data C = Rational Integer Integer | Root C C C in Haskell, where Root a b c = a + b sqrt(c)). However, I don't know how to perform tests with that representation.

Two possible approaches are:

• Constructible numbers are a subset of algebraic numbers, so you can use algebraic numbers.All algebraic numbers can be represented using polynomials of whose they are roots. The operations are computable, so if you represent a number a with polynomial p and b with polynomial q (p(a) = q(b) = 0), then it is possible to find a polynomial r such that r(a+b) = 0. This is done in some CASes like Mathematica, example. See also: Computional algebraic number theory - chapter 4

• Use Tarski's test and represent numbers. It is slow (doubly exponential or so), but works :) Example: to represent sqrt(2), use the formula x^2 - 2 && x > 0. You can write equations for lines there, check if points are colinear etc. See A suite of logic programs, including Tarski's test

If you turn to computable numbers, then equality, colinearity etc. get undecidable.

这篇关于可构造点的坐标可以精确表示吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！