数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › 估计下找到10^100以上的一个四生素数的工作量 ...
1234567下一页
返回列表 发新帖
楼主: 无心人

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

[复制链接]
mathe
发表于 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
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 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 . . .
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-2-14 12:45:22 | 显示全部楼层
不过不知道为什么，只使用一个CPU,是不是选项没有打开？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 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 . . .
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-2-14 13:01:18 | 显示全部楼层
呵呵，有运行了一次，结果运气不好，遇上无解了。
本来想继续加大SQRTSMALLPRIMES现在看来不适合，因为遇上这种情况，如果真要找到一下个解，只能重新从下一块区域开始筛选
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-2-14 13:08:07 | 显示全部楼层
实际计算表明j继续增加SQRTSMALLPRIMES对速度影响不大
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-2-14 13:19:29 | 显示全部楼层
原帖由 mathe 于 2008-2-14 12:45 发表
不过不知道为什么，只使用一个CPU,是不是选项没有打开？


不是的。多核仅被应用于FNT算法中，即只有内部大数乘法达到一定规模时才会被用到。
其它算法，任务不易切分，且不便线程池的控制，所以就没用多线程。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-2-14 13:36:25 | 显示全部楼层
原帖由 gxqcn 于 2008-2-14 13:19 发表


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

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

上载一个预编译后的代码，不过运行需要能够找到郭老大的HugeCalc.dll(输出为十六进制数）
p4.zip (70.9 KB, 下载次数: 3)
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-2-14 13:57:19 | 显示全部楼层
备注：本帖于 2008-02-15 19:30 最后修正！

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

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

  8. // 以下代码源自 mathe 的，略有修改

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

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

  20. #if 1
  21.     #define _Test_HI
  22.     #define integer CHugeInt
  23. #else
  24.     #define _Test_HX
  25.     #define integer CHugeIntX
  26. #endif

  28. #define SMALLPRIMES 0x1000000

  30. #define LIMIT_SIZE 10000000UL
  31. #define RANGE (LIMIT_SIZE<<5)
  32. UINT32 mask[LIMIT_SIZE];
  33. #define SET_MASK(x)  (mask[(x)>>5] |= 1UL<<((x)&31))
  34. #define IS_SET(k,i)  (mask[k]&(1UL<<(i)))

  36. int main(int argc, char* argv[])
  37. {
  38.     cout << "Call " << HugeCalc::GetVer() << endl << endl;

  40.     if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel())
  41.     {
  42.         cout << endl << "警告：您未通过 HugeCalc.dll 的许可认证！" \
  43.             << endl << endl << "解决方案可选下列方案之一：" \
  44.             << endl << "    一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
  45.             << endl << "    二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。" \
  46.             << endl << endl;
  47.         system( "pause" );
  48.         return (-1);
  49.     }

  51.     // 初始化
  52.     HugeCalc::EnableTimer( TRUE );
  53.     HugeCalc::ResetTimer();

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

  58.     integer hugeStart;
  59. #ifdef _Test_HI
  60. #if 0
  61.     hugeStart.Random(100);
  62. #else
  63.     ( hugeStart = 1 ).DecLShift( 100 );
  64. #endif
  65. #else
  66.     hugeStart.Random(335);
  67. #endif

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

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

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

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

  81.     for(k=0;k<spcount;k++){
  82.         p = sptable[k];
  83.         m = hugeStart%p;
  84.         v = HugeCalc::InvertMod(30,p);
  85.         for(i=0;i<sizeof(filter_list)/sizeof(filter_list[0]);i++){
  86.             s = filter_list[i]+m;
  87.             s = ( p >= s ) ? ( p - s ) : ( p*2 - s );
  88. #if ( SMALLPRIMES <= 0xFFFF )
  89.             ( s *= v ) %= p; //hugeStart+s*30+filter_list[i]==0 (mod p)
  90. #else
  91.             s = (UINT32)( UInt32x32To64( s, v ) % p ); // 同上
  92. #endif
  93.             for(h=s;h<RANGE;h+=p){
  94.                 SET_MASK(h);//Filter hugeStart+h*30
  95.             }
  96.         }
  97.     }

  99.     delete []sptable;

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


  105.     UINT32 tcount=0, gcount=0;

  107.     s = 0;
  108.     for(k=0;k<LIMIT_SIZE;k++){
  109.         for(i=0;i<32;i++){
  110.             if(!IS_SET(k,i)){//hugeStart+i*30 may be a candidate
  111.                 ++tcount;
  112.                 hugeStart += s;
  113.                 if( (s =0, hugeStart.TestPrimality(1)!=COMPOSITE ) &&
  114.                     (s-=2, (hugeStart+=2).TestPrimality(2)!=COMPOSITE) &&
  115.                     (s-=4, (hugeStart+=4).TestPrimality(3)!=COMPOSITE) &&
  116.                     (s-=2, (hugeStart+=2).IsPrime()) &&
  117.                     (s+=2, (hugeStart-=2).IsPrime()) &&
  118.                     (s+=4, (hugeStart-=4).IsPrime()) &&
  119.                     (s+=2, (hugeStart-=2).IsPrime())){
  120.                     //Output the candidate;
  121.                     cout<< HugeCalc::GetTimerStr(FT_HHMMSS_ms) << "  No." << ++gcount \
  122.                         << "  Found (n,n+2,n+6,n+8) where n is "
  123. #ifdef _Test_HI
  124.                         << hugeStart.GetStr( FS_NORMAL ) <<endl;
  125. #else                   // 下面语句可将16进制大数直接以10进制数格式输出
  126.                         << hugeStart.GetStrRadix( 10, NULL, FS_NORMAL ) <<endl;
  127. #endif
  128.                }
  129.             }

  131.             s += 30;
  132.         }
  133.     }

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

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

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

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

截屏如下：

四生素数

四生素数
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-2-14 14:02:43 | 显示全部楼层
十进制计算我觉得应该慢一些，这也是为什么我要选择16进制计算。可以计算完了将计算结果再转化为10进制数。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1234567下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-4-19 10:19 , Processed in 0.046238 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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