sqrt(d)用连分式公式展开问题

wsc810 · 发表于 2010-8-16 22:08:46

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

您需要登录才可以下载或查看，没有账号？欢迎注册

×

怎样判断某个数P是否是sqrt(d)用连分式公式展开时出现的P_{n+1}的值，有无简单的方法。该问题与因子分解密切相关，不知有无好的算法不通过展开直接计算判断。

qianyb · 发表于 2010-8-17 07:27:17

到现在为止，还没发现啊，如果有了，分解因数不就简单了

wayne · 发表于 2010-8-17 09:13:35

将 sqrt(d)*P_{n+1}四舍五入，设为N，看N是否满足下面的式子： $|\sqrt{d}-N/P_{n+1}|<1/P_{n+1}^2$

wsc810 · 发表于 2010-8-17 14:58:11

我用几个数验证了一下，结果的确正确，不知wayne是怎样得到上述结论的呢。而为什么又是四舍五入呢

wayne · 发表于 2010-8-18 11:23:58

4# wsc810 这不是我得出来的，书上肯定有的，关于近似分数的那点理论。

wsc810 · 发表于 2010-8-18 13:43:53

wayne,今天我找到了反例，取d=4185,P=2,你的公式是不是|sqrt(d)-N/P|<1/P^2,（我这边手机浏览公式解析不太正确）不信你展开看看，你的公式的出处在什么地方，能否贴上图看看。

wayne · 发表于 2010-8-18 14:01:29

6# wsc810 准确的来说，如果q_n/p_n是sqrt(d)的近似分数，那么不难推出： p_n * q_{n-1} - p_{n-1}*q_n =(-1)^(n-1) 由此，当n比较大时，我们可以放缩，就有|sqrt(d)-N/P|<1/P^2成立了

wsc810 · 发表于 2010-8-18 15:48:54

说来说去，咱们对P_n,Q_n的理解是不同的，难怪我找到了反例，我说的P_n,Q_n,是要求a_n时，得到的副产品，其中Q_n的值是如下pell方程式等号右边的值，即 p_{n-1}^2-d*q_{n-1}^2=(-1)^n*Q_n 而P_n是如下方程式等号右边的值。即 p_n*p_{n-1}-d*q_n*q_{n-1}=(-1)^n*P_n

账号		自动登录	找回密码
密码			欢迎注册

[讨论] sqrt(d)用连分式公式展开问题

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