找回密码
 欢迎注册
楼主: 无心人

[讨论] 10秒内计算出1亿素数表, 不输出

[复制链接]
 楼主| 发表于 2008-3-17 13:47:57 | 显示全部楼层
有兴趣做极大素数间隔么?
我就测试过PII 400
1200亿/小时
计算到10^12
如果按你程序速度
可达到25000亿/小时
可在40000000小时内内计算到10^20的极大素数间隔
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-17 14:23:34 | 显示全部楼层
n年前写过一个筛法求素数的程序,基本思想是这样的:
  用数组arr( unsigned char arr[LEN])的每一个bit 表示 0 -- (LEN-1)*30+29 之间的数是否是素数,1表示是素数,0:表示是合数,具体的表示方法为:
   arr[i]的bit0:表示 30*i+1
   arr[i]的bit1:表示 30*i+7
   arr[i]的bit2:表示 30*i+11
   arr[i]的bit3:表示 30*i+13
   arr[i]的bit4:表示 30*i+17
   arr[i]的bit5:表示 30*i+19
   arr[i]的bit6:表示 30*i+23
   arr[i]的bit7:表示 30*i+29

   因为除了2,3,5以外,任何素数都可表示成上述8种形式之一,故上述表示法不会遗漏。

基本方法:
    在筛之前,将所有bit都初始化为1,然后将表示合数的bit清0.
      
优点:每一个BYTE将表示30个数,采用分段筛法,在L2 cache 不变的情况下,每次能够筛的数比通常的方法增加了30倍,降低了内存读和写的次数,因此能够大大提高速度。

今晚试着重新实现一下该算法,看看速度如何。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-17 15:06:33 | 显示全部楼层
我觉得并不比不压缩的字节表示快
也应该慢于位数组
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-17 15:20:22 | 显示全部楼层

回复 21# 的帖子

目前最大素数间隔好像是1400多, 要破这个记录有点难。
除非将筛法改为针对prime gap 问题,并采用分布式计算
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-17 15:31:18 | 显示全部楼层

回复 23# 的帖子

实际测试表明位压缩要快不少, 虽然操作耗时但CPU的带宽增加7倍(比位数组)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-17 15:40:46 | 显示全部楼层
位压缩能快很多,当然我认为原因是Cache,而不是算法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-17 16:01:10 | 显示全部楼层
这个题目本来就是如何优化对内存的访问问题。而且对于不同的机器(L1/L2cache,内存大小不同)得出的结果都会不同
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-17 16:51:36 | 显示全部楼层
看了一下tprime的java代码,发现和我的非常接近,不过还是稍微有点区别

第一个,我们都用了类似的block,分段是按block来的,我称之为循环节,因为在做筛法的时候,筛2,3,5,7,11等的时候(2这里我们就不筛了),bit数组里是循环的,除了头几个字节要特殊处理以外。不过由于早几年我的CPU赛扬900的L2 Cache只有128KB,所以只做了3,5,7,11的block,循环中第一个开始筛的素数是13,差你的不少,因为现在CPU L2 Cache大了很多;

我们的bit数组其实是一样的,你的代码中MOVE=5,让我纳闷了很久,后来才想起来,可能Java的Char是双字节的,其实在C/C++里,MOVE应该=4,也是一个字节表示16数;

实际开始筛的时候,你的代码好像是做了6*K+1, 6*K+5的筛,而我做的是30*K+1, 30*K+7, 30*K+11, 30*K+13, 30*K+17, 30*K+19, 30*K+23, 30*K+29的筛,如果你也做30*K+N的筛应该可以更快。我的代码又长又丑,写得不是很好,也有很多改进的地方,不好意思公开。

对于liangbch大哥提的一个字节表示30个数,看起来不错,不知道实现起来怎么样
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-17 17:03:30 | 显示全部楼层
我在java版本上尝试过模30,测试效果不好,
代码中你注意到没有, 那段代码被我注了
相反在C++中速度提升20%, 更大的模如210, 2310, 30030是可以尝试的
估计性能提升不大。block 应不超过L2 的 2/3 性能最好
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-18 14:42:40 | 显示全部楼层
我的程序完成了,源代码见附件。在我的电脑(PIV2.6G,768M RAM)筛2-2^31,需5.6秒(9楼的程序需要30秒)筛2-10亿之间的所有素数,需要2.5秒。

   shine可否测试一下,比你的程序如何。

siftPrime.rar

11.78 KB, 下载次数: 95, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-28 20:39 , Processed in 0.050230 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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