数学研发论坛

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

[擂台] 素数分解

[复制链接]
 楼主| 发表于 2008-6-26 08:11:23 | 显示全部楼层
找到问题所在了,是函数is_list开始多了一行
if(aver>=0xFFFFFFFFLL)aver=0xFFFFFFFF;
整个程序运行挺快,应该不到一分钟,不过没有找到任何结果.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-26 08:14:27 | 显示全部楼层
看来需要一个分段筛素数的代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-26 08:15:47 | 显示全部楼层


我记得本论坛有
你仔细找下

不过不要太复杂的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-26 08:32:16 | 显示全部楼层
我的想法是实际上上面代码中只有俩部分计算需要素数列表,也就是计算sumMF和sumMS部分.与其开始保存了所有素数的列表,不如俩部分都动态生成,比如保存两个长度为1,000,000左右大小范围内的素数,分别在当前iMF和iMS指向的数据附近(这两个指针移出范围时计算一下段数据).这样,每一段素数我们需要筛选两次,但是可以避免使用大量内存的问题.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-26 08:43:17 | 显示全部楼层

回复 19# mathe 的帖子

不知问题出在哪里了?
我这里估计无法调试,因为内存太小了。

粗看了遍代码,有以下几点供参考:
  • is_list(..)函数可以精简为
    1. bool is_list(int num, unsigned long long sum)
    2. {
    3.     unsigned long long aver=sum/num;
    4.     if(aver>=0xFFFFFFFFLL)aver=0xFFFFFFFF;
    5.     integer sump(aver);
    6.     sump.NextPrime(sump);
    7.     integer start(sump),end(sump);
    8.     int i;

    9.     for(i=0;i<num/2;i++){
    10.         sump+=start.PreviousPrime(start);
    11.         sump+=end.NextPrime(end);
    12.     }

    13.     if(sump<integer(sum)){
    14.         while(sump<integer(sum)){
    15.             sump-=start;
    16.             sump+=end.NextPrime(end);
    17.             start.NextPrime(start);
    18.         }
    19.     }else{
    20.         while(sump>integer(sum)){
    21.             sump-=end;
    22.             sump+=start.PreviousPrime(start);
    23.             end.PreviousPrime(end);
    24.         }
    25.     }
    26.     return sump==integer(sum);
    27. }
    复制代码
    在帮助文档中对此用法有特别交代说明,其实该用法你在“int prevc,nextc;”语句前已用了一次
  • “if(aver>=0xFFFFFFFFLL)aver=0xFFFFFFFF;”——这句用意何在?
    如果是想限定素数仅用32bits以内的,其后的代码直接用plist里的数据效率更佳
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-26 08:44:08 | 显示全部楼层


这个问题怎么说呢
感觉找到答案主要在于运气
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-26 08:45:15 | 显示全部楼层
编辑了半天帖子,等提交后才知道你们已经知道问题所在了。

不过,我也对那句感到不解和疑惑。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-26 08:45:50 | 显示全部楼层
原帖由 gxqcn 于 2008-6-26 08:43 发表
不知问题出在哪里了?
我这里估计无法调试,因为内存太小了。

粗看了遍代码,有以下几点供参考:
  • is_list(..)函数可以精简为bool is_list(int num, unsigned long long sum)
    {
        unsigned long long ave ...

  • 我已经找到问题了,就在你列出的第2点这句代码上.原先代码之用于搜索32比特以内范围的数,所以有了这句,后来修改以后忘了删除这句了
    毋因群疑而阻独见  毋任己意而废人言
    毋私小惠而伤大体  毋借公论以快私情
     楼主| 发表于 2008-6-26 08:47:14 | 显示全部楼层
    原帖由 无心人 于 2008-6-26 08:44 发表


    这个问题怎么说呢
    感觉找到答案主要在于运气

    从计算速度来看,问题不是很大,结合分段筛划上较长时间应该能够解决这个问题的
    毋因群疑而阻独见  毋任己意而废人言
    毋私小惠而伤大体  毋借公论以快私情
     楼主| 发表于 2008-6-26 08:58:30 | 显示全部楼层
    原帖由 gxqcn 于 2008-6-26 08:43 发表
    不知问题出在哪里了?
    我这里估计无法调试,因为内存太小了。

    粗看了遍代码,有以下几点供参考:
  • is_list(..)函数可以精简为bool is_list(int num, unsigned long long sum)
    {
        unsigned long long ave ...

  • 说明一下:
    i)开始我采用start.NextPrime(start);这种用法,不过有点不放心这种用法是否可以(毕竟输入输出在同一个地址),帮助文件里面没有说明.此外,帮助中应该还要说明函数NextPrime()会修改*this,然后返回*this;
    ii)is_list函数的性能不重要,因为被调用次数极少
    毋因群疑而阻独见  毋任己意而废人言
    毋私小惠而伤大体  毋借公论以快私情
    您需要登录后才可以回帖 登录 | 欢迎注册

    本版积分规则

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

    GMT+8, 2019-3-26 08:10 , Processed in 0.046654 second(s), 14 queries .

    Powered by Discuz! X3.4

    © 2001-2017 Comsenz Inc.

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