数学研发网设为首页收藏本站

数学研发论坛

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

[讨论] 估计下找到10^100以上的一个四生素数的工作量

[复制链接]
发表于 2008-2-14 12:38:05 | 显示全部楼层
got,没有调试功能简单的错误都找不出来。
现在程序在使用
SQRTSMALLPRIMES=200
LIMIT_SIZE=10,000,000时就可以在比较合理的时间内找出10进制100位左右结果了:
游客,如果您要查看本帖隐藏内容请回复

程序运行中部分结果,看来缓冲区选择太大了,结果还在继续产生中。
其中每个输出数字n, {n-4,n-2,n+2,n+4}才是素数。
Call HugeCalc V8.0.0.0

Filter cost 34380ms
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 9829 4389 AFF9
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 9829 9BF9 A22F
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 9829 B44A 52BB
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 9829 C541 B9B5
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 9829 D11B A6D3
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A 0FAA EE63
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A 1CA3 EBE7
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A 31BC BEB9
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A 4878 8B29
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A 4BC0 3165
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A 518D 168F
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 12:43:43 | 显示全部楼层
呵呵第一次使用HugeCalc编程,查看了一下你的文档,然后直接修改你的例子产生的代码。
程序已经运行完了。总共287410s(呵呵,正好5分钟左右),算出14组数。
Call HugeCalc V8.0.0.0

Filter cost 34380ms
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 9829 4389 AFF9
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 9829 9BF9 A22F
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 9829 B44A 52BB
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 9829 C541 B9B5
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 9829 D11B A6D3
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A 0FAA EE63
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A 1CA3 EBE7
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A 31BC BEB9
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A 4878 8B29
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A 4BC0 3165
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A 518D 168F
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A A17A 99DD
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982A EE98 6321
Found n-4,n-2,n+2,n+4 where n is 0x 4720 15C7 CFAB 47C6 7498 B6F7 5DE7 8537 9C19
336C E833 5AA8 DF88 56E8 2CBC 3D72 ED7B 005A 982B 5866 F3DF
Total took 287410 ms
Press any key to continue . . .
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 12:45:22 | 显示全部楼层
不过不知道为什么,只使用一个CPU,是不是选项没有打开?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 12:54:14 | 显示全部楼层
上面忘了加前面部分筛选花的时间了,正好超过5分钟。
我又试着将SQRTSMALLPRIMES改成400(加大筛选范围),重新算一次快多了。
Call HugeCalc V8.0.0.0

Filter cost 42145ms
Found n-4,n-2,n+2,n+4 where n is 0x 75A9 4010 2C19 E028 A536 41BE 101B 31C3 4208
318A F342 C8B1 FADF 2FFC 597A 4CEC 1B1E 891C 44E7 2DB4 1105
Found n-4,n-2,n+2,n+4 where n is 0x 75A9 4010 2C19 E028 A536 41BE 101B 31C3 4208
318A F342 C8B1 FADF 2FFC 597A 4CEC 1B1E 891C 44E7 4684 5DCF
Found n-4,n-2,n+2,n+4 where n is 0x 75A9 4010 2C19 E028 A536 41BE 101B 31C3 4208
318A F342 C8B1 FADF 2FFC 597A 4CEC 1B1E 891C 44E7 4A1E 6C41
Found n-4,n-2,n+2,n+4 where n is 0x 75A9 4010 2C19 E028 A536 41BE 101B 31C3 4208
318A F342 C8B1 FADF 2FFC 597A 4CEC 1B1E 891C 44E7 68D0 A1D1
Found n-4,n-2,n+2,n+4 where n is 0x 75A9 4010 2C19 E028 A536 41BE 101B 31C3 4208
318A F342 C8B1 FADF 2FFC 597A 4CEC 1B1E 891C 44E7 6D24 3B0D
Found n-4,n-2,n+2,n+4 where n is 0x 75A9 4010 2C19 E028 A536 41BE 101B 31C3 4208
318A F342 C8B1 FADF 2FFC 597A 4CEC 1B1E 891C 44E7 9D9D F0CB
Found n-4,n-2,n+2,n+4 where n is 0x 75A9 4010 2C19 E028 A536 41BE 101B 31C3 4208
318A F342 C8B1 FADF 2FFC 597A 4CEC 1B1E 891C 44E8 3DE3 F8EB
Found n-4,n-2,n+2,n+4 where n is 0x 75A9 4010 2C19 E028 A536 41BE 101B 31C3 4208
318A F342 C8B1 FADF 2FFC 597A 4CEC 1B1E 891C 44E8 57F4 7B6B
Found n-4,n-2,n+2,n+4 where n is 0x 75A9 4010 2C19 E028 A536 41BE 101B 31C3 4208
318A F342 C8B1 FADF 2FFC 597A 4CEC 1B1E 891C 44E8 96B0 91E1
Found n-4,n-2,n+2,n+4 where n is 0x 75A9 4010 2C19 E028 A536 41BE 101B 31C3 4208
318A F342 C8B1 FADF 2FFC 597A 4CEC 1B1E 891C 44E9 03EC AE75
Found n-4,n-2,n+2,n+4 where n is 0x 75A9 4010 2C19 E028 A536 41BE 101B 31C3 4208
318A F342 C8B1 FADF 2FFC 597A 4CEC 1B1E 891C 44E9 0795 2543
Total took 177493 ms
Press any key to continue . . .
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 13:01:18 | 显示全部楼层
呵呵,有运行了一次,结果运气不好,遇上无解了。
本来想继续加大SQRTSMALLPRIMES现在看来不适合,因为遇上这种情况,如果真要找到一下个解,只能重新从下一块区域开始筛选
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 13:08:07 | 显示全部楼层
实际计算表明j继续增加SQRTSMALLPRIMES对速度影响不大
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 13:19:29 | 显示全部楼层
原帖由 mathe 于 2008-2-14 12:45 发表
不过不知道为什么,只使用一个CPU,是不是选项没有打开?


不是的。多核仅被应用于FNT算法中,即只有内部大数乘法达到一定规模时才会被用到。
其它算法,任务不易切分,且不便线程池的控制,所以就没用多线程。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 13:36:25 | 显示全部楼层
原帖由 gxqcn 于 2008-2-14 13:19 发表


不是的。多核仅被应用于FNT算法中,即只有内部大数乘法达到一定规模时才会被用到。
其它算法,任务不易切分,且不便线程池的控制,所以就没用多线程。

同意,是我考虑不周全。看来对于这道题目,可以简单在后面寻找素数的循环上加上openmp的标记,可以通过并行提高计算速度

上载一个预编译后的代码,不过运行需要能够找到郭老大的HugeCalc.dll(输出为十六进制数)
p4.zip (70.9 KB, 下载次数: 3)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 13:57:19 | 显示全部楼层
备注:本帖于 2008-02-15 19:30 最后修正!

参考 mathe 的代码,略作了些修改(省却了小素数的搜索过程):
  1. // HugeCalcDemo.cpp : Defines the entry point for the console application.
  2. //

  3. // Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
  4. //  Win32 Debug:    Debug Multithreaded DLL
  5. //  Win32 Release:  Multithreaded DLL

  6. // 以下代码源自 mathe 的,略有修改

  7. #include <time.h>
  8. #include <iostream>
  9. using namespace std;
  10. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"  // 公共接口
  11. #include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h"   // 10进制系统
  12. #include "../../../HugeCalc_API/CppAPI/Include/HugeIntX.h"  // 16进制系统

  13. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
  14. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )

  15. #if 1
  16.     #define _Test_HI
  17.     #define integer CHugeInt
  18. #else
  19.     #define _Test_HX
  20.     #define integer CHugeIntX
  21. #endif

  22. #define SMALLPRIMES 0x1000000

  23. #define LIMIT_SIZE 10000000UL
  24. #define RANGE (LIMIT_SIZE<<5)
  25. UINT32 mask[LIMIT_SIZE];
  26. #define SET_MASK(x)  (mask[(x)>>5] |= 1UL<<((x)&31))
  27. #define IS_SET(k,i)  (mask[k]&(1UL<<(i)))

  28. int main(int argc, char* argv[])
  29. {
  30.     cout << "Call " << HugeCalc::GetVer() << endl << endl;

  31.     if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel())
  32.     {
  33.         cout << endl << "警告:您未通过 HugeCalc.dll 的许可认证!" \
  34.             << endl << endl << "解决方案可选下列方案之一:" \
  35.             << endl << "    一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行;" \
  36.             << endl << "    二、或请在 HugeCalc.chm 中进行注册(一劳永逸)。" \
  37.             << endl << endl;
  38.         system( "pause" );
  39.         return (-1);
  40.     }

  41.     // 初始化
  42.     HugeCalc::EnableTimer( TRUE );
  43.     HugeCalc::ResetTimer();

  44.     // 下面这条语句可以不必调用,HugeCalc 初始化时内部已执行该过程
  45.     // HugeCalc::SeedRandom(time(NULL));

  46.     integer hugeStart;
  47. #ifdef _Test_HI
  48. #if 0
  49.     hugeStart.Random(100);
  50. #else
  51.     ( hugeStart = 1 ).DecLShift( 100 );
  52. #endif
  53. #else
  54.     hugeStart.Random(335);
  55. #endif

  56.     CONST UINT32 spcount = HugeCalc::GetPrimePi( SMALLPRIMES ) - 3;//skip prime 2,3,5
  57.     UINT32 * sptable = new UINT32[ spcount ];
  58.     HugeCalc::GetPrimeList( sptable, spcount, 7, SMALLPRIMES );

  59.     UINT32 i,k,m,s,p,v,h;
  60.     CONST UINT32 filter_list[] = { 0, 2, 6, 8 };

  61.     memset( mask, 0, sizeof(mask) );

  62.     m = hugeStart%30;
  63.     hugeStart += (11>=m) ? (11-m) : (41-m); //After the normalization, hugeStart%30==11

  64.     for(k=0;k<spcount;k++){
  65.         p = sptable[k];
  66.         m = hugeStart%p;
  67.         v = HugeCalc::InvertMod(30,p);
  68.         for(i=0;i<sizeof(filter_list)/sizeof(filter_list[0]);i++){
  69.             s = filter_list[i]+m;
  70.             s = ( p >= s ) ? ( p - s ) : ( p*2 - s );
  71. #if ( SMALLPRIMES <= 0xFFFF )
  72.             ( s *= v ) %= p; //hugeStart+s*30+filter_list[i]==0 (mod p)
  73. #else
  74.             s = (UINT32)( UInt32x32To64( s, v ) % p ); // 同上
  75. #endif
  76.             for(h=s;h<RANGE;h+=p){
  77.                 SET_MASK(h);//Filter hugeStart+h*30
  78.             }
  79.         }
  80.     }

  81.     delete []sptable;

  82.     cout << "Filter cost "<< HugeCalc::GetTimer( TIMER_UNIT_ms ) << "ms" <<endl;
  83.     HugeCalc::ResetTimer();


  84.     UINT32 tcount=0, gcount=0;

  85.     s = 0;
  86.     for(k=0;k<LIMIT_SIZE;k++){
  87.         for(i=0;i<32;i++){
  88.             if(!IS_SET(k,i)){//hugeStart+i*30 may be a candidate
  89.                 ++tcount;
  90.                 hugeStart += s;
  91.                 if( (s =0, hugeStart.TestPrimality(1)!=COMPOSITE ) &&
  92.                     (s-=2, (hugeStart+=2).TestPrimality(2)!=COMPOSITE) &&
  93.                     (s-=4, (hugeStart+=4).TestPrimality(3)!=COMPOSITE) &&
  94.                     (s-=2, (hugeStart+=2).IsPrime()) &&
  95.                     (s+=2, (hugeStart-=2).IsPrime()) &&
  96.                     (s+=4, (hugeStart-=4).IsPrime()) &&
  97.                     (s+=2, (hugeStart-=2).IsPrime())){
  98.                     //Output the candidate;
  99.                     cout<< HugeCalc::GetTimerStr(FT_HHMMSS_ms) << "  No." << ++gcount \
  100.                         << "  Found (n,n+2,n+6,n+8) where n is "
  101. #ifdef _Test_HI
  102.                         << hugeStart.GetStr( FS_NORMAL ) <<endl;
  103. #else                   // 下面语句可将16进制大数直接以10进制数格式输出
  104.                         << hugeStart.GetStrRadix( 10, NULL, FS_NORMAL ) <<endl;
  105. #endif
  106.                }
  107.             }

  108.             s += 30;
  109.         }
  110.     }

  111.     cout << "Total test "<<tcount<<" Numbers, get "<<gcount<<" numbers"<<endl;

  112.     system( "pause" );
  113.     return 0;
  114. }
复制代码
大家可以将它复制覆盖原 \HugeCalc\testDLL\src\ANSI_C++\ansi_c++.cpp,再编译即可。

在我的蹩脚机器上运行结果如下:
  1. Call HugeCalc V8.0.0.0

  2. Filter cost 68254ms
  3. 00:00:07.194  No.1  Found (n,n+2,n+6,n+8) where n is 100000000000000000000000000
  4. 00000000000000000000000000000000000000000000000000000000000000001053594241
  5. 00:00:07.370  No.2  Found (n,n+2,n+6,n+8) where n is 100000000000000000000000000
  6. 00000000000000000000000000000000000000000000000000000000000000001069468231
  7. 00:00:16.808  No.3  Found (n,n+2,n+6,n+8) where n is 100000000000000000000000000
  8. 00000000000000000000000000000000000000000000000000000000000000002439435571
  9. 00:00:23.487  No.4  Found (n,n+2,n+6,n+8) where n is 100000000000000000000000000
  10. 00000000000000000000000000000000000000000000000000000000000000003413496841
  11. 00:00:25.334  No.5  Found (n,n+2,n+6,n+8) where n is 100000000000000000000000000
  12. 00000000000000000000000000000000000000000000000000000000000000003681511741
  13. 00:00:31.152  No.6  Found (n,n+2,n+6,n+8) where n is 100000000000000000000000000
  14. 00000000000000000000000000000000000000000000000000000000000000004552552081
  15. 00:00:37.123  No.7  Found (n,n+2,n+6,n+8) where n is 100000000000000000000000000
  16. 00000000000000000000000000000000000000000000000000000000000000005435223751
  17. 00:00:38.937  No.8  Found (n,n+2,n+6,n+8) where n is 100000000000000000000000000
  18. 00000000000000000000000000000000000000000000000000000000000000005692544401
  19. 00:00:44.441  No.9  Found (n,n+2,n+6,n+8) where n is 100000000000000000000000000
  20. 00000000000000000000000000000000000000000000000000000000000000006496820491
  21. 00:00:55.114  No.10  Found (n,n+2,n+6,n+8) where n is 10000000000000000000000000
  22. 000000000000000000000000000000000000000000000000000000000000000008049785491
  23. 00:00:57.931  No.11  Found (n,n+2,n+6,n+8) where n is 10000000000000000000000000
  24. 000000000000000000000000000000000000000000000000000000000000000008455204681
  25. 00:00:58.478  No.12  Found (n,n+2,n+6,n+8) where n is 10000000000000000000000000
  26. 000000000000000000000000000000000000000000000000000000000000000008532272461
  27. 00:01:02.213  No.13  Found (n,n+2,n+6,n+8) where n is 10000000000000000000000000
  28. 000000000000000000000000000000000000000000000000000000000000000009077484631
  29. Total test 51248 Numbers, get 13 numbers
  30. 请按任意键继续. . .
复制代码
速度快得惊人!

截屏如下:

四生素数

四生素数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 14:02:43 | 显示全部楼层
十进制计算我觉得应该慢一些,这也是为什么我要选择16进制计算。可以计算完了将计算结果再转化为10进制数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2017-7-26 18:35 , Processed in 0.275045 second(s), 21 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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