可构造点的坐标可以精确表示吗? [英] Can coordinates of constructable points be represented exactly?

问题描述

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

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

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

解决方案

是的.

我强烈推荐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.

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