数学研发论坛

 找回密码
 欢迎注册
查看: 2083|回复: 26

[原创] 尺规作图正十一边形(或其他问题)

[复制链接]
发表于 2018-5-29 21:31:49 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
正十一边形尺规不可作出,不过先请大家看看这个视频:
尺规近似正十一边形
该方法用 $7561/3279*\sqrt{-3/5+\sqrt{2/5}}$ 近似 $cos({4\pi}/11)$ ,相对误差仅有 $3.455*10^-13$。

这玩意的理论基础是,用计算机搜索一定格式的几何数(只含有有理数与平方根的数),然后寻找其中最接近一个给定的超越数($cos({4\pi}/11)$)的,然后尺规做出来。
计算机搜索是能尽可能给出形式简洁的几何数的。但是,形式简洁的几何数不一定尺规易作,尺规易作的几何数不一定形式简洁。

问题:如何找到步骤尽可能少,但是尽可能精确的方案?

一些附加说明:
以下尺规作图操作视为一步:
1,过两点作直线
2,以一点为圆心,两点间距离为半径作圆
或者,还可以把以下比较常用的尺规操作也视为只需一步?
3,过一点作一直线的平行线或垂线
4,求两点的中点
另外,求直线与直线,或直线与圆,或圆与圆之间的交点视为零步。

我对这个问题有一些朴素的思路,不过需要用到编程。我觉得这可能是一个编程竞赛类问题。

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-7-5 14:48:59 | 显示全部楼层
下面我来谈谈我的思路。
迫真尺规作图计划~搜索策略(最终版):
1 使用递归进行限制深度的深度优先搜索,遍历一切可能的尺规作图方式,给出一切可能得到的不同的点。
2.以下7种基本操作均视为1步:
2.1.构造两线交点
2.2.构造线与圆的交点
2.3.构造圆与圆的交点
2.4.过两点构造直线
2.5.过一点构造一条线的垂线
2.6.过一点构造一条线的平行线
2.7.以一点为圆心,两点间距离为半径构造圆
3.深度搜索剪枝策略:
3.1.构造点,线,圆时,与当前图上已有的点,线,圆不得重合。
3.2.构造圆时所用的半径长度,或构造线时所用的两点距离,或构造平行线时的点线距离,不得过短。
3.3.构造两图形交点时,在交点上,两图形切线的夹角不得过小。
3.4.限定画布大小,不构造画布外的点。
3.5.如果要构造点,该点必与之前最后一次构造的线或圆有关。否则,可以在构造那线或圆之前就构造该点,将得到重复的局面。
3.6.深度搜索的最后一层仅构造点,因为构造了线或圆也无法为点数做出贡献。
3.7.对每一步递归做出的图进行hash,以kdtree的形式将同层(除最后两层外)所有图形的hash记录下来。每次作图完毕后将新图形的hash与记录比较,若有相同hash的记录,说明是重复局面,不再对该局面进行递归计算。
4.将每次构造的有效点的位置在内存中以kdtree的形式记录下来。每次构造出点,都要与记录进行比较,只有不重复的点是有效的。同时在磁盘中线性记录有效点的尺规作法。kdtree中保存有磁盘记录的编号,以便查找。
5.在一切点对中挑选出迫真点对,即距离与目标数相差小于事先给定值的点对。在对点进行排序后,该过程可加速至O(N^(3/2))。
6.首先使用double精度进行递归作图与搜索迫真点对以确保计算速度。然后对迫真数对,从磁盘中读取尺规作法,使用任意精度浮点数进行复盘,并求出精确距离及误差。
7.为了节省内存,由于起始图(仅有两点(-1/2,0), (1/2,0))是有x和y方向的镜像对称性的,故仅记录x>=0和y>=0的有效点,这样可以节省4倍内存。计算迫真点对时,需考虑从每个点(x,y)获得的座标为(x,y), (x,-y), (-x,-y), (-x,y) 的四个点。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-7-5 14:51:15 | 显示全部楼层
一些说明:
程序实现时考虑了浮点数的误差(10^-13),故判断浮点数是否重复,是否相等都只需在该误差内成立。
两点距离小于10^-11*即判断为重复点。考虑到画布大小(3x3),对10亿个不同的随机点发生至少1次误判的可能性是万分之0.17。(*将在下一次更新时将该值修改为10^-13)
目前正在运行深度上限12层的递归,已经记录了3亿以上的有效点,内存使用达到10GB(而我的电脑内存只有16G,本来按照对浅层递归的外推,估计大约只有2.2亿个点的,失算了)。
本次递归所用的参数如下:
最短作图距离(见2# 3.2):0.15
最小求交正弦(见2# 3.3):0.2
画布大小(见2# 3.4):(-3,3)*(-3,3)

第一个目标是作出正十一边形,选取了以下9个非几何数作为迫真目标:
2sin(pi/11)
cos(4pi/11)
1-cos(4pi/11)
2sin(2pi/11)
sin(2pi/11)
cos(6pi/11)+1
1-cos(6pi/11)
2sin(3pi/11)
sin(3pi/11)
收集迫真点对时,要求点对距离与上述数字之一的差小于10^-12。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-7-9 10:04:37 | 显示全部楼层
在 3# 所述参数下,程序因电脑内存不足被强制终止了。
修改了两项参数:
1. 两点距离小于 10^-13 时判断为重复点(原为 10^-11 )。
2. 限制画布大小为 (-2,2)*(-2,2)(原为 (-3,3)*(-3,3) ),这样可以限制有效点的个数,降低内存使用。
重新运行程序。
递归结果为:
构造出了 126208333229 个点,其中 301676867 个是有效的。
用时 258879.993191 秒。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-7-14 09:27:28 | 显示全部楼层
就是要找出 满足加减乘除,开平方运算的代数数。
Mathematica有一个函数比较有意思,能直接返回结果,很不巧,精度比$7561/3279*\sqrt{-3/5+\sqrt{2/5}}$ 更高,高了1000倍.
  1. RootApproximant[Cos[4 Pi/11], 2]
复制代码


\[\frac{\sqrt{33412510403}-114247}{165001} = \cos(\frac{4\pi}{11})  -1.27...\cdot10^{-16}\]

点评

在我看来,7561和3279绝对不会需要80步那么多  发表于 2018-7-18 13:11
尺规作图是另外一个问题.  发表于 2018-7-18 12:58
33412510403,你想想尺规怎么做出来这种数字吧。7561和3279已经花了我80步了。  发表于 2018-7-18 10:09
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-7-14 10:08:02 | 显示全部楼层
$2 \cos (\frac{4 \pi }{11})$是$1+3 t-3 t^2-4 t^3+t^4+t^5 = 0$ 的根。而$(97757+\sqrt{2598437161})/179016$ 是 $19434-97757 t+89508 t^2=0$的根。其中, $(97757+\sqrt{2598437161})/179016 = 2 \cos (\frac{4 \pi }{11}) -5.1735*10^{-16}$

所以,问题一般化之后,就是给定一个高阶的$n$次多项式方程$p_n(t)$,我们如何找到最佳的低阶的$m$次多项式方程$p_m(t)$,使得该方程的根与原方程的根误差很小。这里就是 $n=5,m=2$

也就是 $1+3 t-3 t^2-4 t^3+t^4+t^5 =0 $,同时$\epsilon$很小, $ a (t+\epsilon)^2+b (t+\epsilon) +c =0  $
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-7-14 11:17:20 | 显示全部楼层
点是二维的信息,在计算机里面保存不是很方便。
我们知道只要找到线段长度接近我们的目标值比如$cos(pi/11)$即可。
为了计算上的方便,我们假设有一下三种基本操作
i)给定长度a和b,计算出长度$a+b$或$a-b$,(对于长度大于1的,我们改为记录$a+b-1$,这样可以保证所有的结果都在(0,1)区间
ii)给定长度a,做出$a/2$
iii)给定长度a,做出长度$\sqrt(a)$
然后我们如果能够从数据1出发,反复通过的上面三种基本操作尽量少的次数,
得出一个尽量接近目标值的数值,就可以构造出一种步数可以比较少的几何作图方案
为了达到$10^-14$的精度,那么我们需要在(0,1)上产生大概$10^14$个数据才行,这个在现在计算机水平是不可接受的。
但是我们可以先产生$10^7$个数据,然后对于其中每个数据,求目标值和它的差或和,然后查询这个和或差是否和$10^7$中某个数据充分接近,就可以得到一种不错的结果。

点评

给定长度a,可以做\(t*a\),t为有理数。  发表于 2018-7-14 18:17
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-7-15 11:39:33 | 显示全部楼层
wayne 发表于 2018-7-14 10:08
$2 \cos (\frac{4 \pi }{11})$是$1+3 t-3 t^2-4 t^3+t^4+t^5 = 0$ 的根。而$(97757+\sqrt{2598437161})/179 ...

是否存在更接近的多重根号或者多平方根数之和近似呢?

点评

应该存在的。自由度大较大,枚举起来比较费劲  发表于 2018-7-15 21:49
好吧,肯定可以无限接近。关键是定义一个“尺规复杂度”函数,评价给定的表达式用尺规作出的难度。  发表于 2018-7-15 15:58
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-7-15 21:06:53 | 显示全部楼层
zeroieme 发表于 2018-7-15 11:39
是否存在更接近的多重根号或者多平方根数之和近似呢?

请教各位,方程t^5+t^4-4t^3-3t^2+3t+1=0怎么根式求解啊?谢谢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-7-18 10:44:49 | 显示全部楼层
感谢各位捧场。
wayne提出的方法可以立即得到相当精确的代数近似,但这个问题毕竟不是纯粹数学问题,数字的大小还是很重要的。
mathe的思路和我差不多,不过化为一维问题后,求解复杂度确实大大减少了(从 O(N^(3/2)) 降到了 O(N) )。代价是得到的方法要花更多的尺规步骤(一个代数步骤往往需要多步尺规作图)。

我认为这个问题的难度在于,它不仅关心结果多么近似(连分数展开即能无限近似),还要关心尺规作图复杂度。
所以我才想出了递归尺规作图暴力搜索的方法。
而2L中我所总结的七种基本作图步骤,以及剪枝策略,都是经过思考定下来的。
(比如我否定了1L中提出的将“作两点中点”视为基本步骤的想法,因为经过实验,这个操作会产生大量很糟糕的点。)
而该方法的精度也是相当受限的,拿我的电脑算 1 个月,估计能给出二十几步内 10^-18 误差的结果。再提高精度就得不偿失了(指数时空复杂度)。
总感觉这个问题没有什么好的解决方法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-11-13 15:05 , Processed in 0.063861 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表