33,007
社区成员
发帖
与我相关
我的任务
分享53 位回文平方数
回文平方数的记录原来是 Pete Leadbetter May 20, 2001 的:
64897400105515621177314682^2 = 4211672540455378958718869999688178598735540452761124 (52位).
我昨天找到了一个 53 位的回文平方数:
122063831551139898460740721^2 = 14899578972945056149893218681239894165054927987599841
用的机器是 DELL PRECISION 9200 DUAL QUADCORE 2.33 GHZ, C++, 算法用了八个 CORE. 不过还没算完所有 52 位数, 所以八个 CORE对找到这个数作用不大.
其他的一些回文数记录在:
http://www.worldofnumbers.com/palrecs.htm
用兴趣的可以试试. 不过简单的不算: 1 0000000 .... 1 ^2 很多是回文数, 1 000099..000 .... 1 ^2 也不少.
64897400105515621177314682^2 = 4211672540455378958718869999688178598735540452761124 (52位).
我昨天找到了一个 53 位的回文平方数:
122063831551139898460740721^2 = 14899578972945056149893218681239894165054927987599841
用的机器是 DELL PRECISION 9200 DUAL QUADCORE 2.33 GHZ, C++, 算法用了八个 CORE. 不过还没算完所有 52 位数, 所以八个 CORE对找到这个数作用不大.
其他的一些回文数记录在:
http://www.worldofnumbers.com/palrecs.htm
用兴趣的可以试试. 不过简单的不算: 1 0000000 .... 1 ^2 很多是回文数, 1 000099..000 .... 1 ^2 也不少.
...全文
请发表友善的回复…
发表回复
szcoder1102 2008-04-14
- 打赏
- 举报
***************************************************************************
思想决定行动，交流产生力量。
程序员在深圳QQ群大集
专业分类:
程序员在深圳JAVA群4247660
程序员在深圳c++群15195967
程序员在深圳.NET群Ⅱ:12203296
程序员在深圳TCP/IP协议栈开发:16956462
程序员在深圳JS & AJAX群:12578377
程序员在深圳英语学习群:23864353
深序员在深圳VB:11055959
程序员在深圳c++Ⅱ17409451
程序员在深圳c++群15195967
程序员在深圳嵌入式开发群37489763
程序员在深圳移动开发群31501597
程序员在深圳创业群33653422
不限专业分类:
高级群:17538442
第三群:2650485
第二群:7120862
第五群:29537639
第四群:28702746
第六群:10590618
第七群:10543585
第八群:12006492
第九群:19063074
第十群:2883885
第十一群:25460595
第十二群:9663807
深圳程序员QQ群联盟成立两年多，拥有三十个以上的QQ群,人数达两千多人,有30%以上的成员的经验丰富
的老手,包括国内外顶级大公司的成员（如微软、IBM,SUN，华为）、国内著名高校和研究院成员，和有
丰富实践经验的高级程序(包括参加过上亿元的项目的架构师),有很热爱技术的成员(包括自己写过嵌入
式操作系统),还有少数女程序员。
现推介如下QQ群,如有兴趣速速加入:深程高级群:17538442（此群不欢迎新手，已经在深圳工作的，月薪
6K以下的不欢迎）c++:15195967 .NET:12203296 mobile:31501597嵌入式:37489763 JAVA:4247660
——————————————————————————————————————————
希望大家不要认为群能给你送来什么，这只是一个平台,让同等水平的程序员有个交流的机会或许能得到
一点信息或许能带来一点启发。
有人说常聊QQ的人肯定技术不怎么样，但其实很多技术高朋友不需要做一些简单的重复劳动所以还是有
时间聊天的。
*****************************************************************************
思想决定行动，交流产生力量。
程序员在深圳QQ群大集
专业分类:
程序员在深圳JAVA群4247660
程序员在深圳c++群15195967
程序员在深圳.NET群Ⅱ:12203296
程序员在深圳TCP/IP协议栈开发:16956462
程序员在深圳JS & AJAX群:12578377
程序员在深圳英语学习群:23864353
深序员在深圳VB:11055959
程序员在深圳c++Ⅱ17409451
程序员在深圳c++群15195967
程序员在深圳嵌入式开发群37489763
程序员在深圳移动开发群31501597
程序员在深圳创业群33653422
不限专业分类:
高级群:17538442
第三群:2650485
第二群:7120862
第五群:29537639
第四群:28702746
第六群:10590618
第七群:10543585
第八群:12006492
第九群:19063074
第十群:2883885
第十一群:25460595
第十二群:9663807
深圳程序员QQ群联盟成立两年多，拥有三十个以上的QQ群,人数达两千多人,有30%以上的成员的经验丰富
的老手,包括国内外顶级大公司的成员（如微软、IBM,SUN，华为）、国内著名高校和研究院成员，和有
丰富实践经验的高级程序(包括参加过上亿元的项目的架构师),有很热爱技术的成员(包括自己写过嵌入
式操作系统),还有少数女程序员。
现推介如下QQ群,如有兴趣速速加入:深程高级群:17538442（此群不欢迎新手，已经在深圳工作的，月薪
6K以下的不欢迎）c++:15195967 .NET:12203296 mobile:31501597嵌入式:37489763 JAVA:4247660
——————————————————————————————————————————
希望大家不要认为群能给你送来什么，这只是一个平台,让同等水平的程序员有个交流的机会或许能得到
一点信息或许能带来一点启发。
有人说常聊QQ的人肯定技术不怎么样，但其实很多技术高朋友不需要做一些简单的重复劳动所以还是有
时间聊天的。
*****************************************************************************
tianjiao85 2008-03-21
- 打赏
- 举报
看不懂楼上们在聊什么，
快快加油，加油，早点成为N人。
快快加油，加油，早点成为N人。
huzhenqi2008 2008-03-02
- 打赏
- 举报
1/21/2008 {2 * 9941 * 11029737483712545657221}
27 digits: 219293240651172832756867922 Non-Palindrome =>
53 digits: 48089525395293201014489455855498441010239259352598084 Palindrome
1/21/2008 {31 * 548501 * 80778076662386102939}
28 digits: 1373512530649258635292477609 Non-Palindrome =>
55 digits: 1886536671850530641991373196913731991460350581766356881 Palindrome
27 digits: 219293240651172832756867922 Non-Palindrome =>
53 digits: 48089525395293201014489455855498441010239259352598084 Palindrome
1/21/2008 {31 * 548501 * 80778076662386102939}
28 digits: 1373512530649258635292477609 Non-Palindrome =>
55 digits: 1886536671850530641991373196913731991460350581766356881 Palindrome
sepnic 2008-02-29
- 打赏
- 举报
mark
rover___ 2008-02-19
- 打赏
- 举报
研究下
royeleo 2008-02-18
- 打赏
- 举报
mark
Michael_MJ 2008-02-15
- 打赏
- 举报
[請務必保持幽默]
OO
laneease 2008-02-15
- 打赏
- 举报
我这机子也就看看记录了 呵呵
JiangHongTao 2008-02-15
- 打赏
- 举报
mark
kingmax54212008 2008-02-14
- 打赏
- 举报
mark
ptwcj 2008-02-14
- 打赏
- 举报
mark
candy110 2008-02-13
- 打赏
- 举报
学习 看看:)
seamanhy 2008-02-13
- 打赏
- 举报
mark
回家再看
回家再看
freeman11me 2008-02-12
- 打赏
- 举报
mark
wuyi8808 2008-02-12
- 打赏
- 举报
袁老大都出来了，震惊中...
yaos 2008-02-11
- 打赏
- 举报
怪俺表述不严密
我说是根据上面的算法
的概率
我说是根据上面的算法
的概率
mathe 2008-02-11
- 打赏
- 举报
基本就是约等于随意给个63位数，是平方数的概率。估计计算机花上100万亿年的时间就可以砸死一只小蜜蜂
yaos 2008-02-11
- 打赏
- 举报
如果轮大锤砸蜜蜂的方法
（或者文雅的方式，叫概率算法）
你估计随意迭代出一个回文数，是平方数的概率是多少？
比如63位的
（或者文雅的方式，叫概率算法）
你估计随意迭代出一个回文数，是平方数的概率是多少？
比如63位的
DarkTerminator 2008-02-10
- 打赏
- 举报
o
r
z
r
z
mathe 2008-02-10
- 打赏
- 举报
算法其实不复杂，就是如何有效率的实现比较麻烦。
算法时间复杂度是O(10^(N/4))而不是O(N*10^(N/4)) (对于N位数)
因为假设总共有d层计算，那么其中第k层需要计算10^k次，总共需要1+10+10^2+...+10^d=(10^(d+1)-1)/9次，（其中d约为N/4)
至于是一次计算多位还是一位，没有什么区别。就是一次直接计算N/4位时间复杂度都是一样。
而计算中一些可能可以优化的机会应该是尽量减少乘法的次数。
比如将n = n' * 10 + k代入的时候，(k=0,1,...,9)
可以先只计算k=0的情况,这种情况比较简单
A''=A*100,B''=B*10,C''=C
而对于其它的k,从k到k+1的情况很简单，我们分别将n和n+1代入公式，求差可以得到2*A*n+(A+B),这个差值不需要任何乘法。
此后，对于每个k,我们需要计算C''%10,这个计算通常编译器可以自动转化为一次乘法运算（甚至可以计算转化为移位，不过对于这里，继续转化为移位运算应该没有好处),
所以这里我们还是至少需要一次乘法运算，我想不出更多的优化机会。
此后，我们需要计算n'的最高位，这个分析感觉比上面的要复杂，但是我感觉很可能同上面的过程类似，不如一次性针对所有可能的n'的最高位一次性计算出来（当然，通常可能有一半左右的数据是非法的），然后我们需要一个长度为10的数组将最高位和最低位的数据对应起来。
算法时间复杂度是O(10^(N/4))而不是O(N*10^(N/4)) (对于N位数)
因为假设总共有d层计算，那么其中第k层需要计算10^k次，总共需要1+10+10^2+...+10^d=(10^(d+1)-1)/9次，（其中d约为N/4)
至于是一次计算多位还是一位，没有什么区别。就是一次直接计算N/4位时间复杂度都是一样。
而计算中一些可能可以优化的机会应该是尽量减少乘法的次数。
比如将n = n' * 10 + k代入的时候，(k=0,1,...,9)
可以先只计算k=0的情况,这种情况比较简单
A''=A*100,B''=B*10,C''=C
而对于其它的k,从k到k+1的情况很简单，我们分别将n和n+1代入公式，求差可以得到2*A*n+(A+B),这个差值不需要任何乘法。
此后，对于每个k,我们需要计算C''%10,这个计算通常编译器可以自动转化为一次乘法运算（甚至可以计算转化为移位，不过对于这里，继续转化为移位运算应该没有好处),
所以这里我们还是至少需要一次乘法运算，我想不出更多的优化机会。
此后，我们需要计算n'的最高位，这个分析感觉比上面的要复杂，但是我感觉很可能同上面的过程类似，不如一次性针对所有可能的n'的最高位一次性计算出来（当然，通常可能有一半左右的数据是非法的），然后我们需要一个长度为10的数组将最高位和最低位的数据对应起来。
加载更多回复（53）
