http://user.qzone.qq.com/414353346/blog/1288275811
http://numbers.computation.free.fr/Constants/TinyPrograms/tinycodes.pdf
:)
11# gracias
恩，后面那个资料我看过，所以才如此感兴趣，只是两年了，对于细节我又忘记了；但大概的思路我还有；
我是要问任意整数开m次方的那个收敛级数，这个问题我已经有了想法，就是如9楼所讨论的
若不限定b=1，更一般的情况就是，解关于正整数a,p,q,非0整数b 的不定方程：
a*q^m-(a-b)*N*p^m=0
其中N,m为正整数常数，p,q互质，a,b互质，|b|<a
给定一个不大的正整数N，当n=2，3，4，5，。。。时，上面那个不定方程的解（a,b,p,q）的通项怎么求出，并给出最佳解。
http://user.qzone.qq.com/414353346/blog/1288275811
http://numbers.computation.free.fr/Constants/TinyPrograms/tinycodes.pdf
:)
gracias 发表于 2011-4-24 11:07 http://bbs.emath.ac.cn/images/common/back.gif
谢谢你提供的关于这个算法的详细资料，认真看过后有种相见恨晚的感觉；
http://www.comlab.ox.ac.uk/research/pdt/ap/minutes/algprog-20031107.pdf
http://www.cs.umb.edu/~offner/files/pi.pdf
http://www.mathpropress.com/stan/bibliography/spigot.pdf
http://numbers.computation.free.fr/Constants/TinyPrograms/tinycodes.pdf
言归正传，继续思考这个不定方程的解法。。
5# plp626
谢谢楼主，有时间好好学下批处理。
本帖最后由 ▄︻┻═┳一‥ 于 2011-4-26 11:27 编辑
当m=2时，也就是开方的时候，用程序暴力搜索1000以内的所有整数解得到：
只是俺的这个程序算法太笨蛋了，运行了半天才得到这些
+------+------+------+------+
| N | a | p | q |
+------+------+------+------+
| 2 | 9 | 3 | 4 |
| 2 | 50 | 5 | 7 |
| 2 |289 | 17 | 24 |
| 3 | 4 | 2 | 3 |
| 3 | 49 | 7 | 12 |
| 3 |676 | 26 | 45 |
| 5 | 81 | 9 | 20 |
| 6 | 25 | 5 | 12 |
| 6 |243 | 9 | 22 |
| 7 | 64 | 8 | 21 |
| 8 | 9 | 3 | 8 |
| 8 | 50 | 5 | 14 |
| 8 |289 | 17 | 48 |
| 10 |361 | 19 | 60 |
| 11 |100 | 10 | 33 |
| 12 | 49 | 7 | 24 |
| 12 |676 | 13 | 45 |
| 13 |325 | 5 | 18 |
| 14 | 8 | 2 | 7 |
| 14 |225 | 15 | 56 |
| 15 | 16 | 4 | 15 |
| 15 |961 | 31 |120 |
| 18 | 50 | 5 | 21 |
| 18 |289 | 17 | 72 |
| 20 | 81 | 9 | 40 |
| 21 | 28 | 2 | 9 |
| 22 | 99 | 3 | 14 |
| 23 |576 | 24 |115 |
| 24 | 25 | 5 | 24 |
| 24 |243 | 9 | 44 |
| 27 | 4 | 2 | 9 |
| 27 | 49 | 7 | 36 |
| 27 |676 | 26 |135 |
| 28 | 64 | 4 | 21 |
| 30 |121 | 11 | 60 |
| 32 | 9 | 3 | 16 |
| 32 | 50 | 5 | 28 |
| 32 |289 | 17 | 96 |
| 33 | 12 | 2 | 11 |
| 33 |529 | 23 |132 |
| 34 | 18 | 3 | 17 |
| 35 | 36 | 6 | 35 |
| 39 |625 | 25 |156 |
| 40 |361 | 19 |120 |
| 42 |169 | 13 | 84 |
| 44 |100 | 5 | 33 |
| 45 | 81 | 3 | 20 |
| 48 | 49 | 7 | 48 |
| 48 |676 | 13 | 90 |
| 50 | 9 | 3 | 20 |
| 50 |289 | 17 |120 |
| 52 |325 | 5 | 36 |
| 54 | 25 | 5 | 36 |
| 54 |243 | 3 | 22 |
| 54 |755 |349 |938 |
| 55 | 45 | 3 | 22 |
| 56 |225 | 15 |112 |
| 57 | 76 | 2 | 15 |
| 58 |887 |959 |134 |
| 60 | 16 | 2 | 15 |
上面输出表面有些N在1000内还无解
猜想某些N也许在计算机的32位整数内无解。
看来这个级数对于N开m次方不具有通用性。
// 对于一个给定的浮点数，求一个一定范围内的p/q,使得p/q近似等于这个浮点数，有1种2分迭代法，可迅速逼近，下面给出c语言代码#include <stdlib.h>
#include <stdio.h>
#include <math.h>
typedef unsigned long DWORD;
void print_pq(double f,DWORD limit)
{
DWORD low_p,low_q,high_p,high_q,mid_p,mid_q;
//初始化low_q,low_q,high_p,high_q
low_q=DWORD(floor(f));
high_q=DWORD(ceil(f));
low_p=high_p=1;
mid_p=low_p+high_p;
mid_q=low_q+high_q;
while ( mid_p<limit )
{
printf("%u/%u=%.12f\n",mid_q,mid_p,double(mid_q)/double(mid_p) );
if ( double(mid_q)/double(mid_p) > f)
{
high_p=mid_p; high_q=mid_q;
}
else
{
low_p=mid_p; low_q=mid_q;
}
mid_p=low_p+high_p;
mid_q=low_q+high_q;
}
}
int main(int argc, char* argv[])
{
print_pq(sqrt(2),1000000); //求分子在1000000以内的sqrt(2)有理数逼近
return 0;
}
这里给出楼上代码的运行结果3/2=1.500000000000
4/3=1.333333333333
7/5=1.400000000000
10/7=1.428571428571
17/12=1.416666666667
24/17=1.411764705882
41/29=1.413793103448
58/41=1.414634146341
99/70=1.414285714286
140/99=1.414141414141
239/169=1.414201183432
338/239=1.414225941423
577/408=1.414215686275
816/577=1.414211438475
1393/985=1.414213197970
1970/1393=1.414213926777
3363/2378=1.414213624895
4756/3363=1.414213499851
8119/5741=1.414213551646
11482/8119=1.414213573100
19601/13860=1.414213564214
27720/19601=1.414213560533
47321/33461=1.414213562057
66922/47321=1.414213562689
114243/80782=1.414213562427
161564/114243=1.414213562319
275807/195025=1.414213562364
390050/275807=1.414213562382
665857/470832=1.414213562375
941664/665857=1.414213562372
18# liangbch
你说的可是最佳有理逼近？
那个是连分数，只是当分母超过 21亿的时候，就不好算了，要自己构造大数据类型做除法了。。。。
还是不如spigot算法 省事。。。