数学研发论坛

 找回密码
 欢迎注册
楼主: medie2005

[讨论] K-Smith numbers

[复制链接]
发表于 2008-11-28 11:34:03 | 显示全部楼层
我想那个时间,是他无法承受的了
能连续30天计算一个问题的
只有我和mathe能

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-28 11:34:43 | 显示全部楼层


如果优化到1秒内能扫描一个亿
我不介意再挂30天
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-28 11:59:37 | 显示全部楼层
这个太夸张了。这个程序已经很优化了,再将其速度提高30倍,几乎是不可能的。

   还有,也可以不用连续运行30天。在运行过程中,定期将运行的中间数据(上下文)保存到文件。这个程序在运行时,如果没有发现程序上下文文件,则从开头运行。否则,将最近的上下文数据从文件载入,从上次运行点接着运行。这个做法,我在那个查孪生小素因子数种已经试用过了,效果很好(可随时中断).
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-28 17:01:34 | 显示全部楼层
有的算法是无法保存状态的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-28 17:59:30 | 显示全部楼层
怎么不可以,好像没有这样的例子吗?笔记本电脑的运行状态都可以整个保存到硬盘上。

以计算smith数为例,需要记录的数据有以下几个部分

  1. 素数表,当然如果素数比较多,则可以不保存,在下次计算时重新生成。
  2. 10000以内的数的数字和。
  3.上次筛出的最近的10个smith数。
  4.上次筛的范围。如上次从begin 筛到end,那么这次则从end+1 开始筛。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-28 20:19:56 | 显示全部楼层
你没考虑非正常中断的情况

另外,比如树等高级结构很难保存
除非用标准库
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-29 15:05:03 | 显示全部楼层
I have a suggestion. We're looking for K-Smith numbers no more than $10^12$ and Yao has a plenty of machines and it is better we could find an efficient distributed algortihm.
For each machine, in the initialization phase, it could find all primes no more than $10^6$
And the compute should also compute sum of digits of all primes less than $10^6$ in advance.
initialized a mapping m[..] so that m[p] to be sum of digits of p.
Now a machine will try to find all K-smith numbers in the range [U,V].
For each number in the range, calculate the sum of digits of the number and save it in an integer array sum[U..V], and create another array x[U..V] which is initialized to the number itself.
Next, for each prime p in the list.
    for(t=p;t<=V;t*=p){
          s=(U/t )*t; if(s<U)s+=t;
         for(;s<=V;s+=t){sum-=m[p];x/=p;}
    }

After that, we could scan the array sum and x by
  for(t=U;t<=V;t++){
     if(sum[t]<0)continue;
    if(sum[t]==0){
          if(x==1) output(t);
    }else{
         if(x>1){
              if(sum of digits of x is sum[t]) output(t);
        }
   }
}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-29 15:12:38 | 显示全部楼层
Since multiplication is faster the divid, we could initialize array x to be 1 and in the first loop, replace x/=p by x*=p
In the second loop, the if(x==1) is changed to if(x==s) and
  if(x>1)  if(sum of digits of x is sum[t])
   changed to
  if(x<s) if(sum of digits of s/x is sum[t])
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-29 15:21:26 | 显示全部楼层
It seems liangbch has used the algorithm. So the only suggestion is use * instead of /.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-29 15:33:03 | 显示全部楼层
mathe 的算法描述有漏洞,
  1.   
for(;s<=V;s+=t){sum-=m[p];x/=p;}

    如果x能够被p整除,要一直除下去,直到不能整除为止。 如60/2=30, 继续除以2, 30/2=15。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-3-1 02:43 , Processed in 0.055201 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表