数学研发论坛

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

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

[复制链接]
发表于 2008-3-18 14:45:29 | 显示全部楼层
在siftPrime.h 中定义L2_CACHE,如果你的电脑L2_CACHE 不是512K,请试着修改为实际值。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-18 19:02:44 | 显示全部楼层
to liangbch:
由于我们的代码实际上都没有输出素数,tprime的也一样,所以我修改了一下你的代码,否则没有可比性
统计素数的个数而不输出素数表,而我的代码里有2种方式,一种是仅筛法和统计每分段的素数,另一种是保留所有的bit位数组,且统计所有素数个数,程序最后可以检验0-N任何一个数是否为素数,不过计算2-2^30两者相差仅0.2秒而已。

你的代码比我的稍快,不过最快的应该还是GxQcn的。

改进后,仅统计个数
sift prime from 2 to n
n=?(n=0 will exit)1073741824
Total 54400028 in 1073741824
It take 1656 ms
sift prime from 2 to n
n=?(n=0 will exit)2147483648
Total 105097565 in 2147483648
It take 3500 ms
  1. unsigned char bitcount_index_table[] =
  2. {
  3.         8, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4,
  4.         7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
  5.         7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
  6.         6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
  7.         7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
  8.         6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
  9.         6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
  10.         5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
  11.         7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
  12.         6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
  13.         6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
  14.         5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
  15.         6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
  16.         5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
  17.         5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
  18.         4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0
  19. };

  20. // 由于统计个数和你的是反的,要处理一下
  21. for (i=0;i<256;i++)
  22.     bitcount_index_table[i] = 8 - bitcount_index_table[i];

  23. static UINT64 GetPrimeFromSiftBuff2(const BYTE *siftBuff,UINT64 begin, UINT64 end,
  24.                                            UINT64 currCount, int mode)
  25. {
  26.         assert(begin % 30==0);
  27.         DWORD endIdx;
  28.                
  29.         DWORD i,j;
  30.         UINT64 pr=currCount;
  31.         const BYTE maskArray[]={1,2,4,8,16,32,64,128};
  32.         const BYTE remArray[]={1,7,11,13,17,19,23,29};

  33.         endIdx=(DWORD)((end-begin)/30-1);
  34.         if (mode==4)
  35.         {
  36.                 for (i=0;i<=endIdx;i++)
  37.                 {
  38.                         BYTE keyBYTE;
  39.                         keyBYTE = siftBuff[i];
  40.                         pr += bitcount_index_table[keyBYTE];
  41.                 }

  42.                 i=endIdx+1;
  43.                 for (j=0;j<8;j++)
  44.                 {
  45.                         DWORD tmp=MUL30(i)+(DWORD)begin + remArray[j];
  46.                         if (tmp>end)
  47.                                 break;
  48.                         if  ( siftBuff[i] & maskArray[j] )
  49.                         {
  50.                                 pr++;
  51.                         }
  52.                 }
  53.         }
  54.         else if (mode==8)
  55.         {
  56.                 for (i=0;i<=endIdx;i++)
  57.                 {
  58.                         BYTE keyBYTE;
  59.                         keyBYTE = siftBuff[i];
  60.                         pr += bitcount_index_table[keyBYTE];
  61.                 }

  62.                 i=endIdx+1;
  63.                 for (j=0;j<8;j++)
  64.                 {
  65.                         UINT64 tmp=(UINT64)i *30I64+ begin + (UINT64)remArray[j];
  66.                         if (tmp>end)
  67.                                 break;
  68.                         if  ( siftBuff[i] & maskArray[j] )
  69.                         {
  70.                                 pr++;
  71.                         }
  72.                 }
  73.         }
  74.         return pr;
  75. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-19 09:48:34 | 显示全部楼层
GxQcn没有公开算法, 所以谁也不知道其中的奥妙所在
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-19 10:00:32 | 显示全部楼层
他程序计时存在问题
如果是筛法时间不应该这么少
1亿最小时间大于0.01s
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-19 10:07:39 | 显示全部楼层
10亿应该不小于500 ms,  这是我见过的最快筛法
代码过于复杂没看懂
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-19 10:35:31 | 显示全部楼层
等俺封存了128乘再和你们混筛法
现在发问题速度太快了

:)
指不定哪天欠账太多被讨债
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-19 10:36:33 | 显示全部楼层
你到处开辟战场能不累吗
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-19 10:54:22 | 显示全部楼层
怕什么时候就忘记了
好多东西是一时兴起想起来的

反正这么多人觉得有意思就好了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-19 11:29:25 | 显示全部楼层
原帖由 无心人 于 2008-3-19 10:00 发表
他程序计时存在问题
如果是筛法时间不应该这么少
1亿最小时间大于0.01s

同感,我也觉得他的计时存在问题,如果是筛法时间不应该这么少。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-19 20:57:07 | 显示全部楼层
他计算素数个数应该是用的PI(X)函数,筛法是不可能的,反正只是统计,不比用筛法,这点分得很仔细,不过第一次用会吓一跳
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-11-29 21:21 , Processed in 0.087290 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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