Paract BASIC 210n+k篩

 投稿者:たろさ  投稿日:2021年11月 8日(月)03時44分35秒
  !210n+k篩  8スレッド     2021/07/10
!
!#4360
!
!Paract BASIC 210n+k篩 Ver.12  500兆  5/9  (1E8) step
!
DECLARE STRUCTURE struct1: 1 OF NUMERIC
DECLARE STRUCTURE struct2: 1 OF NUMERIC(1536277)
DECLARE STRUCTURE struct4: 3 OF NUMERIC
DECLARE SHARED sha OF struct2
DECLARE MESSAGE mes2 OF struct4
DECLARE MESSAGE mes3 OF struct4
DECLARE MESSAGE mes4 OF struct4
DECLARE MESSAGE mes5 OF struct4
DECLARE MESSAGE mes6 OF struct4
DECLARE MESSAGE mes7 OF struct4
DECLARE MESSAGE mes8 OF struct4
DECLARE MESSAGE met2 OF struct1
DECLARE MESSAGE met3 OF struct1
DECLARE MESSAGE met4 OF struct1
DECLARE MESSAGE met5 OF struct1
DECLARE MESSAGE met6 OF struct1
DECLARE MESSAGE met7 OF struct1
DECLARE MESSAGE met8 OF struct1
PARACT PART1
OPTION ARITHMETIC NATIVE
LET t1=TIME
LET k=24494963
LET k3=1536277
DECLARE EXTERNAL SUB prime
CALL prime(k)
WAIT EVENT Ok5
LET S=1E8  !pi(1E12),37607912018
LET E=1E10  !pi(1E11),4118054813    (1E10)455052511
LET ST=1E8

START Part2
START PART3
START PART4
START PART5
START PART6
START PART7
START PART8
SEND TO mes2 FROM S,E,ST
SEND TO mes3 FROM S,E,ST
SEND TO mes4 FROM S,E,ST
SEND TO mes5 FROM S,E,ST
SEND TO mes6 FROM S,E,ST
SEND TO mes7 FROM S,E,ST
SEND TO mes8 FROM S,E,ST
LET TOTAL=5761455
DECLARE EXTERNAL FUNCTION cprime
!DECLARE NUMERIC X,Y,Z

FOR I=S TO E-ST STEP ST
   LET t0=TIME
   LET L=cprime(I,I+ST/8)
   RECEIVE FROM met2 TO X
   RECEIVE FROM met3 TO Y
   RECEIVE FROM met4 TO Z
   RECEIVE FROM met5 TO X1
   RECEIVE FROM met6 TO Y1
   RECEIVE FROM met7 TO Z1
   RECEIVE FROM met8 TO X2
   LET L=L+X+Y+Z+X1+Y1+Z1+X2
   LET TOTAL=TOTAL+L
   !IF MOD(I+ST,1E9)=0 THEN PRINT (I+ST)/1E9;TOTAL
   !PRINT TOTAL
   PRINT (I+ST)/1E8;TOTAL;L;
   LET TM=TIME-t0
   PRINT USING"###.###":TM;
   PRINT "秒"
NEXT I
LET TM=TIME-t1
PRINT USING"#####.##":TM;
PRINT "秒"
END PARACT

PARACT PART2
OPTION ARITHMETIC NATIVE
RECEIVE FROM mes2 TO S,E,ST
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
FOR I=S TO E-ST STEP ST
   LET L=cprime(I+ST/8,I+ST/4)
   SEND TO met2 FROM L
NEXT I
END PARACT

PARACT PART3
OPTION ARITHMETIC NATIVE
RECEIVE FROM mes3 TO S,E,ST
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
FOR I=S TO E-ST STEP ST
   LET L=cprime(I+ST/4,I+3*ST/8)
   SEND TO met3 FROM L
NEXT I
END PARACT

PARACT PART4
OPTION ARITHMETIC NATIVE
RECEIVE FROM mes4 TO S,E,ST
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
FOR I=S TO E-ST STEP ST
   LET L=cprime(I+3*ST/8,I+ST/2)
   SEND TO met4 FROM L
NEXT I
END PARACT

PARACT PART5
OPTION ARITHMETIC NATIVE
RECEIVE FROM mes5 TO S,E,ST
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
FOR I=S TO E-ST STEP ST
   LET L=cprime(I+ST/2,I+5*ST/8)
   SEND TO met5 FROM L
NEXT I
END PARACT

PARACT PART6
OPTION ARITHMETIC NATIVE
RECEIVE FROM mes6 TO S,E,ST
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
FOR I=S TO E-ST STEP ST
   LET L=cprime(I+5*ST/8,I+3*ST/4)
   SEND TO met6 FROM L
NEXT I
END PARACT

PARACT PART7
OPTION ARITHMETIC NATIVE
RECEIVE FROM mes7 TO S,E,ST
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
FOR I=S TO E-ST STEP ST
   LET L=cprime(I+3*ST/4,I+7*ST/8)
   SEND TO met7 FROM L
NEXT I
END PARACT

PARACT PART8
OPTION ARITHMETIC NATIVE
RECEIVE FROM mes8 TO S,E,ST
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
FOR I=S TO E-ST STEP ST
   LET L=cprime(I+7*ST/8,I+ST)
   SEND TO met8 FROM L
NEXT I
END PARACT

EXTERNAL FUNCTION cprime(k4,k6)
OPTION ARITHMETIC NATIVE
DECLARE NUMERIC G(1536277) !素数
GET FROM sha TO G

DIM B(48)
DATA 1,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109
DATA 113,121,127,131,137,139,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209

MAT READ B
LET Q=210
LET U=IP(k6/Q)
LET W=IP(k4/Q)
LET kd=IP(U/11+11)
LET kp=IP(SQR(k6))

DIM D(0 TO U-W)

LET COUNT=0
FOR r=1 TO 48
   LET rr=B(r)
   MAT D = ZER
   LET MD=0
   LET t=5

   DO
      LET cca=0
      LET x=G(t)
      IF x^2>k6 THEN EXIT DO
      LET G1=INT(W/x)
      IF MOD(x-rr,Q)=0 THEN
         LET y=(x-rr)/Q
         GOTO 800
      ELSE

         FOR i=1 TO 48
            LET rv=B(i)
            IF MOD(x*rv+rr,Q)=0 THEN
               LET y=-(x*rv+rr)/Q
               GOTO 800
               EXIT FOR
            END IF
         NEXT i
      END IF

      IF x*G1+y < W THEN
         DO
            LET G1=G1+x
            IF x*G1+y => W THEN EXIT DO
         LOOP
      END IF

800       FOR f=G1 TO kd
             IF x*f+y < W THEN  GOTO 900
             IF x*f+y>U THEN GOTO 1000
             LET D(x*f+y-W)=1
900       NEXT f
1000       LET t=t+1

        LOOP

        FOR n=0 TO U-W
           LET ST=n+W
           IF D(n)=0 THEN
              IF Q*ST+rr>k4 AND Q*ST+rr<k6 THEN LET COUNT=COUNT+1
           END IF
        NEXT n
        LET L=L+6
     NEXT r
     LET cprime=COUNT
  END FUNCTION

  EXTERNAL SUB prime(k)
     OPTION ARITHMETIC NATIVE
     DECLARE NUMERIC G(1536277) !素数
     !エラトステネスの篩
     LET Fu=5633
     LET Fm=739
     DIM P(Fu)
     DIM A(Fm)
     MAT P=ZER
     MAT A=ZER
     LET A(1)=2
     LET H1=1
     FOR I=3 TO SQR(Fu) STEP 2
        IF P(I)=0 THEN
           FOR J=I*I TO Fu STEP I
              LET P(J)=1
           NEXT J
        END IF
     NEXT I
     FOR I=3 TO Fu STEP 2
        IF P(I)=0 THEN
           LET H1=H1+1
           LET A(H1)=I
        END IF
     NEXT I

     LET Q=6
     LET k7=k          !篩の計算範囲
     LET k5=IP(k7/Q)+1
     DIM Au(k5),Av(k5)

     MAT Au = ZER     !(6*n-1)
     MAT Av = ZER     !(6*n+1)

     FOR n=3 TO Fm
        LET Pu=A(n)
        IF Pu^2>=k THEN EXIT FOR
        IF MOD(Pu+1,Q)=0 THEN !(6*n-1)
           LET ru=(Pu+1)/Q
           FOR i=1 TO k5
              IF Pu*i+ru>k5 THEN EXIT FOR
              LET Au(Pu*i+ru)=1
           NEXT i
        END IF

        IF MOD(Pu-1,Q)=0 THEN
           LET ru=(Pu-1)/Q
           FOR i=1 TO k5
              IF Pu*i-ru>k5 THEN EXIT FOR
              LET Au(Pu*i-ru)=1
           NEXT i
        END IF

        IF MOD(Pu+1,Q)=0 THEN !(6*n+1)
           LET ru=(Pu+1)/Q
           FOR i=1 TO k5
              IF Pu*i-ru>k5 THEN EXIT FOR
              LET Av(Pu*i-ru)=1
           NEXT i
        END IF

        IF MOD(Pu-1,Q)=0 THEN
           LET ru=(Pu-1)/Q
           FOR i=1 TO k5
              IF Pu*i+ru>k5 THEN EXIT FOR
              LET Av(Pu*i+ru)=1
           NEXT i
        END IF
     NEXT n

     LET G(1)=2
     LET G(2)=3
     LET cz=2
     FOR n=1 TO k5
        IF 6*n-1>k7 THEN GOTO 100
        IF Au(n)=0 THEN
           LET cz=cz+1
           LET G(cz)=6*n-1
        END IF
100    IF 6*n+1>k7 THEN EXIT FOR
       IF Av(n)=0  THEN
          LET cz=cz+1
          LET G(cz)=6*n+1
       END IF
    NEXT n
    PUT TO sha FROM G
    SIGNAL Ok5
END SUB


Paract BASIC プログラム 210n+k篩

1億ループ 1億間の素数の個数を数えます。

計算結果

2  11078937  5317482    .141秒
3  16252325  5173388    .109秒
4  21336326  5084001    .094秒
5  26355867  5019541    .187秒
6  31324703  4968836    .125秒
7  36252931  4928228    .109秒
8  41146179  4893248    .125秒
9  46009215  4863036    .110秒
10  50847534  4838319    .144秒

途中省略

90  411523195  4363605    .297秒
91  415885628  4362433    .312秒
92  420243162  4357534    .314秒
93  424603409  4360247    .305秒
94  428958595  4355186    .308秒
95  433311792  4353197    .316秒
96  437663672  4351880    .375秒
97  442014876  4351204    .312秒
98  446362736  4347860    .314秒
99  450708777  4346041    .376秒
100  455052511  4343734    .312秒
   25.93秒


動作環境
Intel Core i7 -8565U    mouse m-Book MB-R500 ノート PC
Intel COre i7 -10700K   自作パソコン
Intel Core i9 -11900KF 自作パソコン

Windows Version
Microsoft Windows 10 (10.0) Professional 64-bit

Paract BASIC Ver. 2.1.2.4 Rev.2   (2021.06.19)

Lazarus fpc-3.2.2-win64
lazarus-2.2.0RC1-fpc-3.2.2-win64.exe               2021-07-08 199.7 MB
lazarus-2.2.0RC1-fpc-3.2.2-cross-i386-win32-win64.exe 2021-07-08  55.1 MB
 

戻る