Jas*_*rff 11 language-agnostic math geometry numbers
我想编写一个程序,让用户可以用直尺和指南针绘制点,线和圆.然后我希望能够回答这个问题,"这三个点是否共线？" 要正确回答,我需要在计算点时避免舍入误差.
这可能吗？我怎样才能代表记忆中的点？
(我查看了一些不寻常的数字库,但我没有找到任何声称提供精确算术和确保终止的精确比较的内容.)
我认为唯一可行的方法是使用符号表示,而不是尝试直接表示坐标值 - 因此您必须避免尝试将sqrt(2)之类的值强制转换为某种数字格式.您将处理无法用二进制,十进制或任何其他位置表示法进行有限表示的无理数.
是.
我强烈推荐构造简介,这是一个很好的基本指南.
基本上你需要能够用可构造的数字来计算- 数字是合理的,或者是a + b sqrt(c)形式,其中a,b,c是先前创建的(参见该PDF的第6页).这可以用代数数据类型完成(例如data C = Rational Integer Integer | Root C C C在Haskell中,其中Root abc = a + b sqrt(c)).但是,我不知道如何使用该表示执行测试.
两种可能的方法是:
可构造数字是代数数字的子集,因此您可以使用代数数字.所有代数数都可以用它们是根的多项式来表示.这些操作是可计算的,所以如果你用多项式p表示数字a,用多项式q(p(a)= q(b)= 0)表示b,那么就有可能找到一个多项式r,使得r(a + b) )= 0.这在一些像Mathematica这样的例子中完成.另见:计算代数数论 - 第4章
使用Tarski的测试并代表数字.它很慢(双指数左右),但工作:)示例:表示sqrt(2),使用公式x ^ 2 - 2 && x> 0.你可以在那里写线的方程,检查点是否是共线等请参阅一套逻辑程序,包括Tarski的测试
如果你转向可计算的数字,那么平等,共线等会变得不可判定.
为了稍微扩展Jim Lewis的答案,如果你想对具有精确算术的整数构造的点进行操作,你需要能够对表格的表示进行操作:
a + b sqrt(c)
其中a,b和c是有理数,或上述形式的表示. 维基百科有一篇相当不错的文章,关于哪些要点是可构造的.
用这种表示来回答确切平等的问题(必要时建立共线性)是一个相当棘手的问题.
如果您尝试比较各点的坐标,那么您就遇到了问题.暂且不考虑共线性,如何计算出两个点是否相同？
假设一个人已经给出了坐标,另一个是从某些其他坐标开始的罗盘直尺构造,你想确定它们是否是相同的点.无论哪种方式都是欧氏几何的定理,它不是你可以测量的东西.您可以通过发现它们的坐标中的某些差异来证明它们不相同(例如,通过计算每个的小数位,直到遇到差异).但总的来说,证明它们是相同的,不能通过近似方法来完成.计算多位小数,你喜欢的一些扩展的1/sqrt(2)和sqrt(2)/2,可以证明他们是非常接近的,但你永远不会证明他们是平等的.这需要代数(或几何).
同样,要显示三个点是共线的,您将需要定理证明软件.用它们的结构表示点A,B,C,并试图证明定理"A,B和C是共线的".这很难 - 你的程序将证明一些定理而不是其他定理.更容易的是要求用户提供他们是共线的证明,然后验证(或反驳)该证据,但这可能不是你想要的.