数学研发论坛

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

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

[复制链接]
 楼主| 发表于 2008-3-25 15:29:28 | 显示全部楼层
在没想到更好方法之前
俺封闭俺代码,不再优化
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-26 20:01:32 | 显示全部楼层
下面是测试在PIV上的测试结果(时间单位为毫秒,所有测试均取3次最小值)。

经过进一步的努力,在siftPrime4的基础上改出一个新的版本。主要修改如下,1. 关键部分使用汇编优化,2. 对将筛的过程中用的的素数表 改为压缩的字节数组。(新版所用的文件名为siftPrime5,调用其的测试函数为testSift5)。 在PM上,统计1亿,10亿的素数时,效果明显,大约提速10-15%,但在PIVCPU上,提速效果却不太明些。

np1p3p4p5
10000007.9791.6524.8970.897
1000000075.16412.43713.81511.026
100000000782.436143.780130.932132.868
10000000008257.1251711.7231546.2831599.733


大家可在你们的机器上测试,看看siftPrime5的表现如何。

siftPrime.rar

23.44 KB, 阅读权限: 20, 下载次数: 8, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

售价: 1 枚金币  [记录]

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-26 21:23:23 | 显示全部楼层
哦?
看不明白
p1这么低的时间是什么功能?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-26 21:40:22 | 显示全部楼层
       siftPrime1                siftPrime2                siftPrime3
     1亿   0.78秒                0.172秒                        0.125秒
    10亿   8.25秒                1.86秒                         1.547秒
    100亿  92.78秒                21.7秒                        18.4秒


p1:即 47# 提到的siftPrime1, 这个版本是最普通的算法,采用byte数组,没有使用任何技巧,所有速度很慢。
p1,p3,p4,p5 对应于 在main函数中 调用 testSift1,testSift3,testSift4,testSift5 这几个版本的执行结果.你可以将这几个函数调用分别打开,在你的电脑上测试一下,看看效果如何,下面是main函数的代码。
  1. int main(int argc, char* argv[])
  2. {
  3.         //testSift1();
  4.         //testSift3();
  5.         //testSift4();
  6.         testSift5();
  7.         return 0;
  8. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-26 21:42:50 | 显示全部楼层
声明 62# 中的5.164 应该75.164
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-26 21:44:36 | 显示全部楼层
呵呵
怪不得呢
你要不是写错了,就忒厉害了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-4 18:07:15 | 显示全部楼层
向楼上众高手学习。
62#的CPU是多少啊?
我的2*1.6G的CPU普通筛法用C语言是3900多毫秒,用汇编筛1亿的素数需要1600多毫秒。而您的P1只需0.78秒,快一倍。
不知道哪里出问题了。
你们这里讨论了“高级的分段筛法”太深奥了,看不明白。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-4 18:41:14 | 显示全部楼层
同样是普通筛法,我的程序太慢了,没法和P1比阿。liangbch能发下你的p1源吗可以么? 

#include <stdio.h>
#include <time.h>

unsigned long S [1562500] = {0};

unsigned long sieve ()
{
        unsigned long c0 = 0,i1,n1,i2,n2,i0,n0,m0;
        n1 = 3; i1 = 1;
        while ( n1 < 10000 )
        {
                n2 = n1 * n1;
                i2 = n2 >> 1;
                while ( i2 < 50000000 )
                {
                        i0 = i2 >> 5; n0 = S[i0];
                        m0 = 1 << (i2 & 0x1f);
                        if (!(n0 & m0))
                        {
                                S[i0] |= m0;
                                c0++;
                        }
                        i2 += n1;
                }
                i1++;
                i0 = i1 >> 5;
                n0 = S[i0];
                m0 = 1 << (i1 & 0x1f);
        while (n0 & m0)
        {
                        i1++;
                        m0 <<= 1;
                        if (m0 == 0)
                        {
                                i0++;
                                n0 = S[i0];
                                m0 = 1;
                        }
        }
            n1 = (i1 << 1) + 1;
        }
    return 50000000 - c0;
}

int main()
{
        clock_t t1 = clock(),t2;
        unsigned long c = sieve();
        t2 = clock();
        printf("%d --> time : %d\n",c,t2-t1);
    system("PAUSE");
    return 0;
}

/************************************************************
E:\worker>shai
5761455 --> time : 2230
Press any key to continue . . .
************************************************************/
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-7-4 20:10:44 | 显示全部楼层

呵呵
你先把算法作好了
再考虑汇编
算法不优秀
汇编白优化
主要考虑
分段大小不要超过CPU L2 Cache
段起始数字最好是几个小素数的倍数
则可预选存储部分筛结果而节约时间
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-5 09:09:51 | 显示全部楼层
...大家都是线性筛法么?
Sieve of Atkin比线性低一点点的筛法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-11-30 13:04 , Processed in 0.075280 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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