- 注册时间
- 2007-12-27
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 40098
- 在线时间
- 小时
|
楼主 |
发表于 2024-10-5 10:51:49
|
显示全部楼层
寻找最小的2的幂的前n位和$\pi$的前n位相同。
我们假设$2^m$是一个$h$位整数，那么需要它满足条件\(\lfloor10^{n-1}\pi\rfloor\lt\frac{2^m}{10^{h-n}}\lt \lfloor10^{n-1}\pi\rfloor+1\)
也可以两边取对数，变成\(\lg(\lfloor10^{n-1}\pi\rfloor)-(n-1)\lt \{m\lg(2)\}\lt \lg(\lfloor10^{n-1}\pi\rfloor+1)-(n-1)\), 其中$\{x\}$代表$x$的小数部分。
也就是我们需要寻找一个整数m，使得\(m\lg(2)\)的小数部分正好落在某个很小的范围$(e_1,e_2)$之内。
记集合
\(S_2(r,e)=\{m \in Z| 1\le m \le r ; \{m\lg(2)\}\le e \} \cup \{m \in Z| 1\le m \le r ; \{m\lg(2)\}\ge 1-e \}\)
\(S_1(r,e)=\{m \in Z| 1\le m \le r ; e_1-e\le\{m\lg(2)\}\le e_1+e \} \)
如果\(S_2(r,e)\)中存在两个元素$m_1,m_2$,使得\(\{m_1\lg(2)\} \lt \frac12, \{m_2 \lg(2)\} \gt \frac12\), $m = \min\{m_1,m_2\}$
那么对于任意元素\( m \in S_2(r+\min\{m_1,m_2\},e)\), 必然要么\(m \in S_2(r,e)\),要么\(m -m_1 \in S(r,e)\)或\(m-m_2 \in S(r,e)\)
于是我们知道\(S_2(r+\min\{m_1,m_2\},e) \subset S_2(r,e) \cup S_2(r,e)+m_1\cup S_2(r,e)+m_2\)
同理可以知道\(S_1(r+\min\{m_1,m_2\},e) \subset S_1(r,e) \cup S_1(r,e)+m_1\cup S_1(r,e)+m_2\)
于是初始时我们可以选择合适的初始r,e,穷举$S_2(r,e),S_1(r,e)$.
然后每次迭代过程，从$S_2(r,e)$选择合适的$m_1,m_2$ ，那么然后就可以选择新的r为\(r+\min\{m_1,m_2\}\), 并且选择新的较小的e使得新的集合\(S_2(r,e)\)大小合适（选择较小的e可以减小集合的大小，但是要确保集合里面存在可选择的$m_1,m_2$;选择太小的e可能会导致某一边缺元素)
然后利用上面的包含关系得出对于\(S_2,S_1\)的候选元素，再利用实际值计算出两个集合。
实际计算中由于可能存在计算误差，可以对数据进行量化处理，比如一种比较好的方案可以事先将每个浮点数乘上一个非常大的整数M并且仅保留整数部分
比如假设\(\lfloor M\lg(2)\rfloor = a\),那么我们知道\(a\lt M \lg(2) \lt a+1\), \(ma \lt m M\lg(2) \lt ma+m\), \({ma \pmod M} \lt M\{m\lg(2)\} \lt {ma+m \pmod M}\)
所以如果我们发现对于某个m,(ma,ma+m)都落在我们期望的范围内，那么就是找到的一个合法解；但是如果全落在期望范围外，那么不是合法解；而如果和期望范围相交，那么说明计算精度不够，我们需要选择更大的M进行计算。
|
评分
-
查看全部评分
|
IP卡
狗仔卡
发表于 2024-10-4 16:13:08
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡
发表于 2024-10-4 22:10:51
