尺规作图正十一边形（或其他问题）

Ickiverar

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

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

问题：如何找到步骤尽可能少，但是尽可能精确的方案？

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

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

Ickiverar

下面我来谈谈我的思路。
迫真尺规作图计划～搜索策略（最终版）：
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) 的四个点。

Ickiverar

一些说明：
程序实现时考虑了浮点数的误差（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。

Ickiverar

在 3# 所述参数下，程序因电脑内存不足被强制终止了。
修改了两项参数：
1. 两点距离小于 10^-13 时判断为重复点（原为 10^-11 ）。
2. 限制画布大小为 (-2,2)*(-2,2)（原为 (-3,3)*(-3,3) ），这样可以限制有效点的个数，降低内存使用。
重新运行程序。
递归结果为：
构造出了 126208333229 个点，其中 301676867 个是有效的。
用时 258879.993191 秒。

wayne

就是要找出 满足加减乘除，开平方运算的代数数。
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}\]

wayne

$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  $

mathe

点是二维的信息，在计算机里面保存不是很方便。
我们知道只要找到线段长度接近我们的目标值比如$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$中某个数据充分接近，就可以得到一种不错的结果。

zeroieme

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 ...

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

wangfeizaaq

zeroieme 发表于 2018-7-15 11:39
是否存在更接近的多重根号或者多平方根数之和近似呢？

请教各位，方程t^5+t^4-4t^3-3t^2+3t+1=0怎么根式求解啊？谢谢

Ickiverar

感谢各位捧场。
wayne提出的方法可以立即得到相当精确的代数近似，但这个问题毕竟不是纯粹数学问题，数字的大小还是很重要的。
mathe的思路和我差不多，不过化为一维问题后，求解复杂度确实大大减少了（从 O(N^(3/2)) 降到了 O(N) ）。代价是得到的方法要花更多的尺规步骤（一个代数步骤往往需要多步尺规作图）。

我认为这个问题的难度在于，它不仅关心结果多么近似（连分数展开即能无限近似），还要关心尺规作图复杂度。
所以我才想出了递归尺规作图暴力搜索的方法。
而2L中我所总结的七种基本作图步骤，以及剪枝策略，都是经过思考定下来的。
（比如我否定了1L中提出的将“作两点中点”视为基本步骤的想法，因为经过实验，这个操作会产生大量很糟糕的点。）
而该方法的精度也是相当受限的，拿我的电脑算 1 个月，估计能给出二十几步内 10^-18 误差的结果。再提高精度就得不偿失了（指数时空复杂度）。
总感觉这个问题没有什么好的解决方法。