Prime-counting function 1E+7 TO 1E+12

 投稿者：たろさ  投稿日：2017年 4月30日(日)16時21分52秒
  Paract BASIC 6n+k篩　は、6n+1,6n+5のnを素数+係数で篩う数値実験プログラムです。

1e8     5761455
2e8    11078937
3e8    16252325
4e8    21336326
5e8    26355867
6e8    31324703
7e8    36252931
8e8    41146179
9e8    46009215

1億stepで1万行あります。ので精度確認には最適だと思います。

主にπ(x)の精度確認を目的としたプログラム

!Paract BASIC 6n+k篩  1兆  4/30 1E7 step
DECLARE STRUCTURE struct1: 1 OF NUMERIC
DECLARE STRUCTURE struct2: 1 OF NUMERIC(78505)
DECLARE STRUCTURE struct3: 1 OF NUMERIC(1 TO 100001)
DECLARE STRUCTURE struct4: 4 OF NUMERIC
DECLARE SHARED sha OF struct2
DECLARE SHARED shb OF struct3
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 k=1000117
LET k3=78505
DECLARE EXTERNAL SUB prime
CALL prime(k,k3)
WAIT EVENT Ok5
LET S=1E7   !pi(1E12),37607912018
LET E=1E9   !pi(1E11),4118054813
LET ST=1E7
LET cc=S/ST+1
DECLARE EXTERNAL SUB sqprime
CALL sqprime(1,100001,k3)
DECLARE NUMERIC B(1 TO 100001)
WAIT EVENT Ok6
GET FROM shb TO B
START Part2
START PART3
START PART4
START PART5
START PART6
START PART7
START PART8
SEND TO mes2 FROM S,E,ST,CC
SEND TO mes3 FROM S,E,ST,CC
SEND TO mes4 FROM S,E,ST,CC
SEND TO mes5 FROM S,E,ST,CC
SEND TO mes6 FROM S,E,ST,CC
SEND TO mes7 FROM S,E,ST,CC
SEND TO mes8 FROM S,E,ST,CC
LET TOTAL=664579
DECLARE EXTERNAL FUNCTION cprime
!DECLARE NUMERIC X,Y,Z
LET FW=S+1E8-2E7
FOR I=S TO E-ST STEP ST
   LET k2=B(cc)
   LET L=cprime(I,I+ST/8,k2)
   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
   !PRINT I;I+ST;TOTAL;L!;cc
   !PRINT TOTAL
   IF I=FW THEN
      PRINT TOTAL
      LET FW=FW+1E8
   END IF
   LET cc=cc+1
NEXT I
END PARACT

PARACT PART2
OPTION ARITHMETIC NATIVE
DECLARE NUMERIC B(1 TO 100001)
GET FROM shb TO B
RECEIVE FROM mes2 TO X,Y,Z,G
LET S=X
LET E=Y
LET ST=Z
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
LET cc=G
FOR I=S TO E-ST STEP ST
   LET k2=B(cc)
   LET cc=cc+1
   LET L=cprime(I+ST/8,I+ST/4,k2)
   SEND TO met2 FROM L
NEXT I
END PARACT

PARACT PART3
OPTION ARITHMETIC NATIVE
DECLARE NUMERIC B(1 TO 100001)
GET FROM shb TO B
RECEIVE FROM mes3 TO X,Y,Z,G
LET S=X
LET E=Y
LET ST=Z
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
LET cc=G
FOR I=S TO E-ST STEP ST
   LET k2=B(cc)
   LET cc=cc+1
   LET L=cprime(I+ST/4,I+3*ST/8,k2)
   SEND TO met3 FROM L
NEXT I
END PARACT

PARACT PART4
OPTION ARITHMETIC NATIVE
DECLARE NUMERIC B(1 TO 100001)
GET FROM shb TO B
RECEIVE FROM mes4 TO X,Y,Z,G
LET S=X
LET E=Y
LET ST=Z
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
LET cc=G
FOR I=S TO E-ST STEP ST
   LET k2=B(cc)
   LET cc=cc+1
   LET L=cprime(I+3*ST/8,I+ST/2,k2)
   SEND TO met4 FROM L
NEXT I
END PARACT

PARACT PART5
OPTION ARITHMETIC NATIVE
DECLARE NUMERIC B(1 TO 100001)
GET FROM shb TO B
RECEIVE FROM mes5 TO X,Y,Z,G
LET S=X
LET E=Y
LET ST=Z
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
LET cc=G
FOR I=S TO E-ST STEP ST
   LET k2=B(cc)
   LET cc=cc+1
   LET L=cprime(I+ST/2,I+5*ST/8,k2)
   SEND TO met5 FROM L
NEXT I
END PARACT

PARACT PART6
OPTION ARITHMETIC NATIVE
DECLARE NUMERIC B(1 TO 100001)
GET FROM shb TO B
RECEIVE FROM mes6 TO X,Y,Z,G
LET S=X
LET E=Y
LET ST=Z
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
LET cc=G
FOR I=S TO E-ST STEP ST
   LET k2=B(cc)
   LET cc=cc+1
   LET L=cprime(I+5*ST/8,I+3*ST/4,k2)
   SEND TO met6 FROM L
NEXT I
END PARACT

PARACT PART7
OPTION ARITHMETIC NATIVE
DECLARE NUMERIC B(1 TO 100001)
GET FROM shb TO B
RECEIVE FROM mes7 TO X,Y,Z,G
LET S=X
LET E=Y
LET ST=Z
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
LET cc=G
FOR I=S TO E-ST STEP ST
   LET k2=B(cc)
   LET cc=cc+1
   LET L=cprime(I+3*ST/4,I+7*ST/8,k2)
   SEND TO met7 FROM L
NEXT I
END PARACT

PARACT PART8
OPTION ARITHMETIC NATIVE
DECLARE NUMERIC B(1 TO 100001)
GET FROM shb TO B
RECEIVE FROM mes8 TO X,Y,Z,G
LET S=X
LET E=Y
LET ST=Z
DECLARE EXTERNAL FUNCTION cprime
DECLARE NUMERIC L
LET cc=G
FOR I=S TO E-ST STEP ST
   LET k2=B(cc)
   LET cc=cc+1
   LET L=cprime(I+7*ST/8,I+ST,k2)
   SEND TO met8 FROM L
NEXT I
END PARACT

EXTERNAL FUNCTION cprime(k4,k6,k2)
OPTION ARITHMETIC NATIVE
DECLARE NUMERIC G(78505) !素数
GET FROM sha TO G
DIM B(2)   !素数の最小値7から
DATA 1,5
MAT READ B
LET Q=6
LET U=INT(k6/Q)
LET W=INT(k4/Q)
LET kD=INT(k6/30)
LET M7=W

DIM D(0 TO U-M7)
LET COUNT=0
FOR r=1 TO 2
   LET rr=B(r)
   MAT D = ZER

   FOR t=3 TO k2
      LET x=G(t)
      LET G1=INT(W/x)

      IF MOD(x+rr,Q)=0 THEN
         LET y=-(x+rr)/Q
         GOTO 70
      END IF

      IF MOD(x-rr,Q)=0 THEN
         LET y=(x-rr)/Q
         GOTO 70
      END IF

70       FOR f=G1 TO kD
            IF x*f+y<W THEN GOTO 80
            IF x*f+y>U THEN GOTO 90
            LET D(x*f+y-M7)=1
80       NEXT f
90    NEXT t

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

EXTERNAL SUB prime(k,k2)
   OPTION ARITHMETIC NATIVE
   DECLARE NUMERIC G(78505) !素数
   !エラトステネスの篩
   LET Fu=1013 !5633
   LET Fm=170  !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 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

  EXTERNAL  SUB sqprime(SA,SB,k2)
    OPTION ARITHMETIC NATIVE
    DECLARE NUMERIC G(78505) !素数
    GET FROM sha TO G
    DECLARE NUMERIC B(1 TO 100001)
    LET x=1E7
    LET x1=x
    FOR i=1 TO k2-1
       LET v=G(i)^2
       LET vi=G(i+1)^2
       LET vv=vi-v
       IF x =< v THEN
          CALL sqrp(1)
          IF vv>=x1 THEN
             LET vt=INT(vv/x1)
             CALL sqrp(vt)
          END IF
       END IF
    NEXT i

    SUB sqrp(vo)
       FOR ns=1 TO vo
          LET C=C+1
          LET X=X+x1
          IF C>=SA AND SB>=C THEN
             LET B(c)=i+1
          END IF
       NEXT ns
    END SUB
    PUT TO shb FROM B
    SIGNAL Ok6
END SUB

----------------------------------------------
私のPCでは

1E+7 TO 1E+12  間では誤差は見られませんでした。

計算時間　1時間5分2.7秒

1時間切れる?  挑戦中

http://blogs.yahoo.co.jp/donald_stinger

  

戻る