Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

When I left you, I was but the pupil. Now, I am the master. -- Darth Vader


devel / comp.lang.forth / Re: Sieve of Atkin

SubjectAuthor
* Sieve of AtkinMarcel Hendrix
+* Re: Sieve of AtkinJan Coombs
|+* Re: Sieve of AtkinMarcel Hendrix
||`* Re: Sieve of Atkindxforth
|| `* Re: Sieve of AtkinMarcel Hendrix
||  +- Re: Sieve of AtkinMarcel Hendrix
||  `* Re: Sieve of Atkinnone
||   `* Re: Sieve of AtkinMarcel Hendrix
||    +* Re: Sieve of AtkinAnton Ertl
||    |`* Re: Sieve of AtkinMarcel Hendrix
||    | `- Re: Sieve of AtkinAnton Ertl
||    `* Re: Sieve of AtkinAnton Ertl
||     `* Re: Sieve of AtkinMarcel Hendrix
||      `* Re: Sieve of AtkinMarcel Hendrix
||       `- Re: Sieve of AtkinMarcel Hendrix
|`* Re: Sieve of AtkinJali Heinonen
| +- Re: Sieve of AtkinMarcel Hendrix
| `* Re: Sieve of AtkinJan Coombs
|  `- Re: Sieve of AtkinJali Heinonen
`* Re: Sieve of AtkinJali Heinonen
 `* Re: Sieve of AtkinMarcel Hendrix
  +* Re: Sieve of AtkinJali Heinonen
  |`* Re: Sieve of AtkinMarcel Hendrix
  | `* Re: Sieve of AtkinJali Heinonen
  |  `* Re: Sieve of AtkinMarcel Hendrix
  |   `* Re: Sieve of AtkinJali Heinonen
  |    +- Re: Sieve of AtkinMarcel Hendrix
  |    `* Re: Sieve of AtkinMarcel Hendrix
  |     `- Re: Sieve of AtkinJali Heinonen
  +- Re: Sieve of AtkinAnton Ertl
  +* Re: Sieve of AtkinAnton Ertl
  |+* Re: Sieve of Atkinnone
  ||`- Re: Sieve of AtkinAnton Ertl
  |`- Re: Sieve of AtkinHans Bezemer
  `- Re: Sieve of Atkinnone

Pages:12
Sieve of Atkin

<5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17929&group=comp.lang.forth#17929

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:6214:626:b0:45a:d14a:eb54 with SMTP id a6-20020a056214062600b0045ad14aeb54mr7411826qvx.126.1653051205044;
Fri, 20 May 2022 05:53:25 -0700 (PDT)
X-Received: by 2002:ac8:5cca:0:b0:2f9:ca3:f35e with SMTP id
s10-20020ac85cca000000b002f90ca3f35emr7751097qta.432.1653051204888; Fri, 20
May 2022 05:53:24 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Fri, 20 May 2022 05:53:24 -0700 (PDT)
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:bd09:77ff:a220:87b7;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:bd09:77ff:a220:87b7
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
Subject: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Fri, 20 May 2022 12:53:25 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 1190
 by: Marcel Hendrix - Fri, 20 May 2022 12:53 UTC

Apparently the fastest possible Sieve (in the limit).
https://www.baeldung.com/cs/prime-number-algorithms .

Unfortunately, the pseudo-code (?) is somewhat ambiguous.

-marcel

Re: Sieve of Atkin

<20220520164842.3d49149a@t530>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17932&group=comp.lang.forth#17932

 copy link   Newsgroups: comp.lang.forth
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: jan4comp...@murray-microft.co.uk (Jan Coombs)
Newsgroups: comp.lang.forth
Subject: Re: Sieve of Atkin
Date: Fri, 20 May 2022 16:48:42 +0100
Organization: A noiseless patient Spider
Lines: 15
Message-ID: <20220520164842.3d49149a@t530>
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="9338985a7668a5ecb101607f5679c78a";
logging-data="28276"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18FC7SR8P5+6912jGlb6+qoSyoatuv5YCQ="
Cancel-Lock: sha1:DJY0WN/IrxcyAC7G7l9zH5bCGF8=
X-Newsreader: Claws Mail 3.17.3 (GTK+ 2.24.32; x86_64-pc-linux-gnu)
 by: Jan Coombs - Fri, 20 May 2022 15:48 UTC

On Fri, 20 May 2022 05:53:24 -0700 (PDT)
Marcel Hendrix <mhx@iae.nl> wrote:

> Apparently the fastest possible Sieve (in the limit).
> https://www.baeldung.com/cs/prime-number-algorithms .
>
> Unfortunately, the pseudo-code (?) is somewhat ambiguous.

The explanation is good, thanks. This seems to work, how's your python?

This is the optimized implementation proposed by Zsolt KOVACS:
from:
https://stackoverflow.com/questions/21783160/sieve-of-atkin-implementation-in-python

Re: Sieve of Atkin

<5697422a-9791-480d-a136-c56dc7a2fa28n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17935&group=comp.lang.forth#17935

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:622a:391:b0:2f9:2bbb:b847 with SMTP id j17-20020a05622a039100b002f92bbbb847mr706820qtx.439.1653097289042;
Fri, 20 May 2022 18:41:29 -0700 (PDT)
X-Received: by 2002:a37:c01:0:b0:6a3:4aaa:1e21 with SMTP id
1-20020a370c01000000b006a34aaa1e21mr3971849qkm.378.1653097288903; Fri, 20 May
2022 18:41:28 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Fri, 20 May 2022 18:41:28 -0700 (PDT)
In-Reply-To: <20220520164842.3d49149a@t530>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:bcd7:ba5b:c99b:c958;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:bcd7:ba5b:c99b:c958
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com> <20220520164842.3d49149a@t530>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <5697422a-9791-480d-a136-c56dc7a2fa28n@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Sat, 21 May 2022 01:41:29 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2805
 by: Marcel Hendrix - Sat, 21 May 2022 01:41 UTC

On Friday, May 20, 2022 at 5:48:44 PM UTC+2, Jan Coombs wrote:
> On Fri, 20 May 2022 05:53:24 -0700 (PDT)
[..]
> This is the optimized implementation proposed by Zsolt KOVACS:
> from:
> https://stackoverflow.com/questions/21783160/sieve-of-atkin-implementation-in-python

Optimized? Maybe according to Python standards...

(*
* LANGUAGE : ANS Forth with extensions
* PROJECT : Forth Environments
* DESCRIPTION : Sieve of Atkin, fastest Sieve O(n)
* CATEGORY : Example
* AUTHOR : Marcel Hendrix
* LAST CHANGE : 02:27:42, May 21, 2022, Marcel Hendrix
*)

NEEDS -miscutil

REVISION -sieveofatkin "--- Sieve of Atkin Version 0.01 ---"

PRIVATES

0 VALUE P
0 VALUE sz
#16384 VALUE limit
CREATE sieve PRIVATE limit 1+ ALLOT

: SieveOfAtkin ( -- )
sieve limit 1+ ERASE
HERE TO P 2 , 3 , 2 TO sz
limit SQRT 2+
1 DO limit SQRT 2+
1 DO J SQR 4 * I SQR + >S
S limit <= S #12 MOD DUP 1 = SWAP 5 = OR AND IF sieve S + DUP C@ NOT SWAP C! ENDIF -S
J SQR 3 * I SQR + >S
S limit <= S #12 MOD 7 = AND IF sieve S + DUP C@ NOT SWAP C! ENDIF -S
J SQR 3 * I SQR - >S
J I > S limit <= AND S #12 MOD #11 = AND IF sieve S + DUP C@ NOT SWAP C! ENDIF -S
LOOP
LOOP
limit SQRT 1+ 5 DO sieve I + C@ IF limit 2+ I SQR DO sieve I + C0! J SQR +LOOP ENDIF LOOP
limit 1+ 5 DO sieve I + C@ IF I , 1 +TO sz ENDIF LOOP
P sz ;

: PSHOW ( addr u -- ) CR 0 ?DO @+ . LOOP DROP ;

:ABOUT CR ." Try: SieveOfAtkin PSHOW " ;

NESTING @ 1 = [IF] .ABOUT -sieveofatkin [THEN]

DEPRIVE

(* End of Source *)

-marcel

Re: Sieve of Atkin

<t69hm8$1bib$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17936&group=comp.lang.forth#17936

 copy link   Newsgroups: comp.lang.forth
Path: i2pn2.org!i2pn.org!aioe.org!7AktqsUqy5CCvnKa3S0Dkw.user.46.165.242.75.POSTED!not-for-mail
From: dxfo...@gmail.com (dxforth)
Newsgroups: comp.lang.forth
Subject: Re: Sieve of Atkin
Date: Sat, 21 May 2022 12:10:15 +1000
Organization: Aioe.org NNTP Server
Message-ID: <t69hm8$1bib$1@gioia.aioe.org>
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<20220520164842.3d49149a@t530>
<5697422a-9791-480d-a136-c56dc7a2fa28n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="44619"; posting-host="7AktqsUqy5CCvnKa3S0Dkw.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
X-Notice: Filtered by postfilter v. 0.9.2
Content-Language: en-GB
 by: dxforth - Sat, 21 May 2022 02:10 UTC

On 21/05/2022 11:41, Marcel Hendrix wrote:
> On Friday, May 20, 2022 at 5:48:44 PM UTC+2, Jan Coombs wrote:
>> On Fri, 20 May 2022 05:53:24 -0700 (PDT)
> [..]
>> This is the optimized implementation proposed by Zsolt KOVACS:
>> from:
>> https://stackoverflow.com/questions/21783160/sieve-of-atkin-implementation-in-python
>
> Optimized? Maybe according to Python standards...
>
> (*
> * LANGUAGE : ANS Forth with extensions
> *)

"ANS Forth" ? Perhaps according to your standards :)

Re: Sieve of Atkin

<4efed8c0-d736-42dd-9627-0913aece17edn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17937&group=comp.lang.forth#17937

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:6214:19c2:b0:462:230:dbd8 with SMTP id j2-20020a05621419c200b004620230dbd8mr8198561qvc.114.1653120025907;
Sat, 21 May 2022 01:00:25 -0700 (PDT)
X-Received: by 2002:a05:620a:1250:b0:6a3:446f:96f3 with SMTP id
a16-20020a05620a125000b006a3446f96f3mr6119740qkl.330.1653120025770; Sat, 21
May 2022 01:00:25 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sat, 21 May 2022 01:00:25 -0700 (PDT)
In-Reply-To: <t69hm8$1bib$1@gioia.aioe.org>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:bcd7:ba5b:c99b:c958;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:bcd7:ba5b:c99b:c958
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<20220520164842.3d49149a@t530> <5697422a-9791-480d-a136-c56dc7a2fa28n@googlegroups.com>
<t69hm8$1bib$1@gioia.aioe.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <4efed8c0-d736-42dd-9627-0913aece17edn@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Sat, 21 May 2022 08:00:25 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Marcel Hendrix - Sat, 21 May 2022 08:00 UTC

On Saturday, May 21, 2022 at 4:10:20 AM UTC+2, dxforth wrote:
> On 21/05/2022 11:41, Marcel Hendrix wrote:
[..]
> > (*
> > * LANGUAGE : ANS Forth with extensions
> > *)
>
> "ANS Forth" ? Perhaps according to your standards :)

What is there about "with extensions" that you don't understand?

(*
* LANGUAGE : ANS Forth with extensions
* PROJECT : Forth Environments
* DESCRIPTION : Sieve of Atkin, fastest Sieve O(n)
* CATEGORY : Example
* AUTHOR : Marcel Hendrix
* LAST CHANGE : Saturday, May 21, 2022, 9:54 AM, mhx;
*)

NEEDS -miscutil

REVISION -sieveofatkin "--- Sieve of Atkin Version 0.02 ---"

PRIVATES

#1000 =: #times
#16384 VALUE limit
limit SQRT 2+ =: SQRT(limit+2) PRIVATE
limit SQRT 1+ =: SQRT(limit+1) PRIVATE
CREATE sieve PRIVATE limit 1+ ALLOT

: toggle ( ix -- ) sieve + DUP C@ NOT SWAP C! ; PRIVATE
: f1: ( I J -- ) SQR 4 * SWAP SQR + ; PRIVATE
: f2: ( I J -- ) SQR 3 * SWAP SQR + ; PRIVATE
: f3: ( I J -- ) SQR 3 * SWAP SQR - ; PRIVATE

: SieveOfAtkin ( -- u )
sieve limit 1+ ERASE
SQRT(limit+2)
1 DO SQRT(limit+2)
1 DO I J f1: >S S limit <= S #12 MOD DUP 1 = SWAP 5 = OR AND IF S toggle ENDIF -S
I J f2: >S S limit <= S #12 MOD 7 = AND IF S toggle ENDIF -S
I J f3: >S J I > S limit <= AND S #12 MOD #11 = AND IF S toggle ENDIF -S
LOOP
LOOP
SQRT(limit+1) 5 DO sieve I + C@ IF limit 2+ I SQR DO sieve I + C0! J SQR +LOOP ENDIF LOOP
2 ( 2 and 3 ) limit 1+ 5 DO sieve I + C@ 1 AND + LOOP ( sz) ;

: PRIMES CR #times DEC. ." iterations." TIMER-RESET
0 #times 0 DO DROP SieveOfAtkin LOOP
MS? SWAP CR . ." primes found, " DEC. ." ms elapsed." ;

:ABOUT CR ." Try: SieveOfAtkin . "
CR ." PRIMES " ;

NESTING @ 1 = [IF] .ABOUT -sieveofatkin [THEN]

DEPRIVE

(* End of Source *)

FORTH> in
Creating --- Sieve of Atkin Version 0.02 ---

Try: SieveOfAtkin .
PRIMES ok
FORTH> SieveOfAtkin . 1900 ok
FORTH> PRIMES
1000 iterations.
1900 primes found, 94 ms elapsed. ok

FORTH> in sieve
Creating --- SIEVE benchmark Version 1.00 ---
Redefining `#times`
Redefining `PRIMES`

Sieve (100 iterations)
Compile time Run time Primes
Par.C 38.19 8.732 1899
Inmos ICC 83.98 9.578 1899
3L C 45.25 5.955 1899
tForth (WS) 1.00 7.244 1899
tForth (main) 1.00 9.253 1899
iForth 386/33 0.3 5.767 1899
iForth 486/50 0.1 1.595 1899
iForth 486/66 0.1 1.559 1899
iForth P5/200 0.1 0.195 1899
iForth PIV/3G 0.1 0.076 1899

Enter PRIMES to run the benchmark.
ok
FORTH> PRIMES
1000 iterations.
1899 primes found, 12 ms elapsed. ok
FORTH>

Out of the box, Atkin is 94 / 12 ~ 8x slower than the standard Sieve algorithm.
The standard algorithm needs no division, so it will work for limit > 2^64, while
Atkin must be extended for that.
-marcel

Re: Sieve of Atkin

<f35676e9-bc69-4294-b3c4-be9b7736baefn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17938&group=comp.lang.forth#17938

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a37:843:0:b0:6a0:47d2:cdc5 with SMTP id 64-20020a370843000000b006a047d2cdc5mr8463799qki.689.1653123594611;
Sat, 21 May 2022 01:59:54 -0700 (PDT)
X-Received: by 2002:a05:620a:6c8:b0:69c:7adc:7370 with SMTP id
8-20020a05620a06c800b0069c7adc7370mr8366005qky.49.1653123594444; Sat, 21 May
2022 01:59:54 -0700 (PDT)
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!2.eu.feeder.erje.net!feeder.erje.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sat, 21 May 2022 01:59:54 -0700 (PDT)
In-Reply-To: <4efed8c0-d736-42dd-9627-0913aece17edn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:bcd7:ba5b:c99b:c958;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:bcd7:ba5b:c99b:c958
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<20220520164842.3d49149a@t530> <5697422a-9791-480d-a136-c56dc7a2fa28n@googlegroups.com>
<t69hm8$1bib$1@gioia.aioe.org> <4efed8c0-d736-42dd-9627-0913aece17edn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <f35676e9-bc69-4294-b3c4-be9b7736baefn@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Sat, 21 May 2022 08:59:54 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Marcel Hendrix - Sat, 21 May 2022 08:59 UTC

On Saturday, May 21, 2022 at 10:00:26 AM UTC+2, Marcel Hendrix wrote:
[..]

Probably easier to understand. Speed unchanged.

(*
* LANGUAGE : ANS Forth with extensions
* PROJECT : Forth Environments
* DESCRIPTION : Sieve of Atkin, fastest Sieve O(n)
* CATEGORY : Example
* AUTHOR : Marcel Hendrix
* LAST CHANGE : Saturday, May 21, 2022, 9:54 AM, mhx;
*)

NEEDS -miscutil

REVISION -sieveofatkin "--- Sieve of Atkin Version 0.03 ---"

PRIVATES

#1000 =: #times
#16384 VALUE limit PRIVATE
limit SQRT 2+ =: SQRT(limit+2) PRIVATE
limit SQRT 1+ =: SQRT(limit+1) PRIVATE
CREATE sieve PRIVATE limit 1+ ALLOT

: init ( -- ) sieve limit 1+ ERASE ; PRIVATE
: flip ( ix -- ) sieve + DUP C@ NOT SWAP C! ; PRIVATE
: fi1 ( I J -- ) SQR 4 * SWAP SQR + >S ; PRIVATE
: fi2 ( I J -- ) SQR 3 * SWAP SQR + >S ; PRIVATE
: fi3 ( I J -- ) SQR 3 * SWAP SQR - >S ; PRIVATE
: test1 ( -- ) S limit <= S #12 MOD DUP 1 = SWAP 5 = OR AND IF S flip ENDIF -S ; PRIVATE
: test2 ( -- ) S limit <= S #12 MOD 7 = AND IF S flip ENDIF -S ; PRIVATE
: +test3 ( ? -- ) S limit <= AND S #12 MOD #11 = AND IF S flip ENDIF -S ; PRIVATE
: no-p^2 ( -- ) SQRT(limit+1) 5 DO sieve I + C@ IF limit 2+ I SQR DO sieve I + C0! J SQR +LOOP ENDIF LOOP ; PRIVATE
: cnt ( -- u ) 2 ( 2 and 3 ) limit 1+ 5 DO sieve I + C@ 1 AND + LOOP ; PRIVATE

: SieveOfAtkin ( -- u )
init
SQRT(limit+2)
1 DO SQRT(limit+2)
1 DO I J fi1 test1
I J fi2 test2
I J fi3 J I > +test3
LOOP
LOOP
no-p^2
cnt ( sz) ;

: PRIMES CR #times DEC. ." iterations." TIMER-RESET
0 #times 0 DO DROP SieveOfAtkin LOOP
MS? SWAP CR . ." primes found, " DEC. ." ms elapsed." ;

:ABOUT CR ." Try: SieveOfAtkin . "
CR ." PRIMES " ;

NESTING @ 1 = [IF] .ABOUT -sieveofatkin [THEN]

DEPRIVE

(* End of Source *)

-marcel

Re: Sieve of Atkin

<66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17942&group=comp.lang.forth#17942

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:622a:1301:b0:2f3:af1d:aa57 with SMTP id v1-20020a05622a130100b002f3af1daa57mr11493550qtk.257.1653150533261;
Sat, 21 May 2022 09:28:53 -0700 (PDT)
X-Received: by 2002:a05:620a:1a8e:b0:6a3:2ac8:96fc with SMTP id
bl14-20020a05620a1a8e00b006a32ac896fcmr9538594qkb.272.1653150533063; Sat, 21
May 2022 09:28:53 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sat, 21 May 2022 09:28:52 -0700 (PDT)
In-Reply-To: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=80.186.1.171; posting-account=kiOBZQoAAADFsAs31ZHaefxTuQxv84Wm
NNTP-Posting-Host: 80.186.1.171
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com>
Subject: Re: Sieve of Atkin
From: jali.hei...@gmail.com (Jali Heinonen)
Injection-Date: Sat, 21 May 2022 16:28:53 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 1477
 by: Jali Heinonen - Sat, 21 May 2022 16:28 UTC

perjantai 20. toukokuuta 2022 klo 15.53.26 UTC+3 Marcel Hendrix kirjoitti:
> Apparently the fastest possible Sieve (in the limit).
> https://www.baeldung.com/cs/prime-number-algorithms .
>
> Unfortunately, the pseudo-code (?) is somewhat ambiguous.
>
> -marcel

Is it really faster than sieve implementation that is wheel factorized to the max?

Re: Sieve of Atkin

<74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17945&group=comp.lang.forth#17945

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:622a:6206:b0:2f1:d7bc:7522 with SMTP id hj6-20020a05622a620600b002f1d7bc7522mr12045299qtb.556.1653166945212;
Sat, 21 May 2022 14:02:25 -0700 (PDT)
X-Received: by 2002:a05:6214:411c:b0:45a:d240:afb9 with SMTP id
kc28-20020a056214411c00b0045ad240afb9mr12222356qvb.122.1653166945034; Sat, 21
May 2022 14:02:25 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.goja.nl.eu.org!news.freedyn.de!newsreader4.netcologne.de!news.netcologne.de!feeder1.cambriumusenet.nl!feed.tweak.nl!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sat, 21 May 2022 14:02:24 -0700 (PDT)
In-Reply-To: <66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:bcd7:ba5b:c99b:c958;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:bcd7:ba5b:c99b:c958
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com> <66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Sat, 21 May 2022 21:02:25 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Marcel Hendrix - Sat, 21 May 2022 21:02 UTC

On Saturday, May 21, 2022 at 6:28:54 PM UTC+2, Jali Heinonen wrote:
> perjantai 20. toukokuuta 2022 klo 15.53.26 UTC+3 Marcel Hendrix kirjoitti:
> > Apparently the fastest possible Sieve (in the limit).
> > https://www.baeldung.com/cs/prime-number-algorithms .
> >
> > Unfortunately, the pseudo-code (?) is somewhat ambiguous.
> >
> > -marcel
> Is it really faster than sieve implementation that is wheel factorized to the max?

Well, so much for CS.

I adapted both Atkin and the standard Sieve so that I could run them with
array sizes between 1k and 10GByte, with the following results:

Standard Sieve:
n runtime (ms) primes
1,000 0 302
10,000 0 2,261
100,000 0 17,983
1,000,000 3 148,932
10,000,000 29 1,270,606
100,000,000 962 11,078,936
1,000,000,000 12695 98,222,286
10,000,000,000 149099 882,206,715

Atkin Sieve
n runtime (ms) primes
1,000 0 168
10,000 0 1,229
100,000 0 9,592
1,000,000 4 78,498
10,000,000 60 664,579
100,000,000 1728 5,761,455
1,000,000,000 20900 50,847,534
10,000,000,000 301417 455,052,511

Atkin is about 4 times slower than the Standard Sieve (50% of the
results in twice the time). It might slowly increase for even larger
sieves, but with 20 GBytes there is not much evidence for that yet.
Maybe somebody with a TB of RAM has more luck.

The jump in runtime between 0.1GB and 1GB might have something to do
with the working-set default of a Windows program (I see no evidence
of disk-activity but ALLOCATE takes noticeably longer).

Here is the final SieveOfAtkin. I fixed a bug that had to do with Python's
logic operators apparently taking shortcuts without being told.

(*
* LANGUAGE : ANS Forth with extensions
* PROJECT : Forth Environments
* DESCRIPTION : Sieve of Atkin, fastest Sieve O(n)
* CATEGORY : Example
* AUTHOR : Marcel Hendrix
* LAST CHANGE : Saturday, May 21, 2022, 9:54 AM, mhx;
*)

NEEDS -miscutil

REVISION -sieveofatkin "--- Sieve of Atkin Version 0.04 ---"

PRIVATES

DOC
(*
n runtime (ms) primes
1,000 0 168
10,000 0 1,229
100,000 0 9,592
1,000,000 4 78,498
10,000,000 60 664,579
100,000,000 1728 5,761,455
1,000,000,000 20900 50,847,534
10,000,000,000 301417 455,052,511
*)
ENDDOC

DEPTH 0= [IF] CR .( Stack Empty) ABORT [THEN]
( #16384 ) =: limit PRIVATE
#1 =: #times PRIVATE
limit SQRT 2+ =: SQRT(limit+2) PRIVATE
limit SQRT 1+ =: SQRT(limit+1) PRIVATE
limit 1+ ALLOCATE ?ALLOCATE =: sieve PRIVATE
limit 1+ ALLOCATE ?ALLOCATE =: mods PRIVATE

: set# ( -- ) limit 2+ 0 DO I #12 MOD mods I + C! LOOP ; PRIVATE set#
: init ( -- ) sieve limit 1+ ERASE ( set# ) ; PRIVATE
: flip ( ix -- ) sieve + DUP C@ NOT SWAP C! ; PRIVATE
: fi1 ( I J -- u ) SQR 4 * SWAP SQR + ; PRIVATE
: fi2 ( I J -- u ) SQR 3 * SWAP SQR + ; PRIVATE
: fi3 ( I J -- u ) SQR 3 * SWAP SQR - ; PRIVATE
: #MOD ( s -- u ) mods + C@ ; PRIVATE
: test1 ( s -- ) DUP limit > IF DROP ELSE >S S #MOD DUP 1 = SWAP 5 = OR IF S flip ENDIF -S ENDIF ; PRIVATE
: test2 ( s -- ) DUP limit > IF DROP ELSE >S S #MOD 7 = IF S flip ENDIF -S ENDIF ; PRIVATE
: +test3 ( s ? -- ) OVER limit > OR IF DROP ELSE >S S #MOD #11 = IF S flip ENDIF -S ENDIF ; PRIVATE
: no-p^2 ( -- ) SQRT(limit+1) 5 DO sieve I + C@ IF limit 2+ I SQR DO sieve I + C0! J SQR +LOOP ENDIF LOOP ; PRIVATE
: cnt ( -- u ) 2 ( 2 and 3 ) limit 1+ 5 DO sieve I + C@ 1 AND + LOOP ; PRIVATE

: SieveOfAtkin ( -- u )
init
SQRT(limit+2)
1 DO SQRT(limit+2)
1 DO I J fi1 test1
I J fi2 test2
I J fi3 J I <= +test3
LOOP
LOOP
no-p^2
cnt ( sz) ;

: PRIMES CR #times DEC. ." iterations." TIMER-RESET
0 #times 0 DO DROP SieveOfAtkin LOOP
MS? SWAP CR . ." primes found, " DEC. ." ms elapsed." ;

:ABOUT CR ." Try: SieveOfAtkin . "
CR ." PRIMES " ;

NESTING @ 1 = [IF] .ABOUT -sieveofatkin [THEN]

DEPRIVE

(* End of Source *)

-marcel

Re: Sieve of Atkin

<nnd$4435a412$60078c44@b615e5bcc1c0105a>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17950&group=comp.lang.forth#17950

 copy link   Newsgroups: comp.lang.forth
Newsgroups: comp.lang.forth
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com> <5697422a-9791-480d-a136-c56dc7a2fa28n@googlegroups.com> <t69hm8$1bib$1@gioia.aioe.org> <4efed8c0-d736-42dd-9627-0913aece17edn@googlegroups.com>
Subject: Re: Sieve of Atkin
X-Newsreader: trn 4.0-test77 (Sep 1, 2010)
From: alb...@cherry (none)
Originator: albert@cherry.(none) (albert)
Message-ID: <nnd$4435a412$60078c44@b615e5bcc1c0105a>
Organization: KPN B.V.
Date: Sun, 22 May 2022 10:57:03 +0200
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!feeder.usenetexpress.com!tr1.eu1.usenetexpress.com!94.232.112.246.MISMATCH!abe006.abavia.com!abp003.abavia.com!news.kpn.nl!not-for-mail
Lines: 126
Injection-Date: Sun, 22 May 2022 10:57:03 +0200
Injection-Info: news.kpn.nl; mail-complaints-to="abuse@kpn.com"
 by: none - Sun, 22 May 2022 08:57 UTC

In article <4efed8c0-d736-42dd-9627-0913aece17edn@googlegroups.com>,
Marcel Hendrix <mhx@iae.nl> wrote:
>On Saturday, May 21, 2022 at 4:10:20 AM UTC+2, dxforth wrote:
>> On 21/05/2022 11:41, Marcel Hendrix wrote:
>[..]
>> > (*
>> > * LANGUAGE : ANS Forth with extensions
>> > *)
>>
>> "ANS Forth" ? Perhaps according to your standards :)
>
>What is there about "with extensions" that you don't understand?
>
>(*
> * LANGUAGE : ANS Forth with extensions
> * PROJECT : Forth Environments
> * DESCRIPTION : Sieve of Atkin, fastest Sieve O(n)
> * CATEGORY : Example
> * AUTHOR : Marcel Hendrix
> * LAST CHANGE : Saturday, May 21, 2022, 9:54 AM, mhx;
>*)
>
>
> NEEDS -miscutil
>
> REVISION -sieveofatkin "--- Sieve of Atkin Version 0.02 ---"
>
> PRIVATES
>
>#1000 =: #times
>#16384 VALUE limit
>limit SQRT 2+ =: SQRT(limit+2) PRIVATE
>limit SQRT 1+ =: SQRT(limit+1) PRIVATE
>CREATE sieve PRIVATE limit 1+ ALLOT
>
>: toggle ( ix -- ) sieve + DUP C@ NOT SWAP C! ; PRIVATE
>: f1: ( I J -- ) SQR 4 * SWAP SQR + ; PRIVATE
>: f2: ( I J -- ) SQR 3 * SWAP SQR + ; PRIVATE
>: f3: ( I J -- ) SQR 3 * SWAP SQR - ; PRIVATE
>
>: SieveOfAtkin ( -- u )
> sieve limit 1+ ERASE
> SQRT(limit+2)
> 1 DO SQRT(limit+2)
> 1 DO I J f1: >S S limit <= S #12 MOD DUP 1 = SWAP 5 = OR AND IF S
>toggle ENDIF -S
> I J f2: >S S limit <= S #12 MOD 7 = AND IF S toggle ENDIF -S
> I J f3: >S J I > S limit <= AND S #12 MOD #11 = AND IF S
>toggle ENDIF -S
> LOOP
> LOOP
> SQRT(limit+1) 5 DO sieve I + C@ IF limit 2+ I SQR DO sieve I + C0!
>J SQR +LOOP ENDIF LOOP
> 2 ( 2 and 3 ) limit 1+ 5 DO sieve I + C@ 1 AND + LOOP ( sz) ;
>
>: PRIMES CR #times DEC. ." iterations." TIMER-RESET
> 0 #times 0 DO DROP SieveOfAtkin LOOP
> MS? SWAP CR . ." primes found, " DEC. ." ms elapsed." ;
>
>:ABOUT CR ." Try: SieveOfAtkin . "
> CR ." PRIMES " ;
>
>NESTING @ 1 = [IF] .ABOUT -sieveofatkin [THEN]
>
> DEPRIVE
>
> (* End of Source *)
>
>
>FORTH> in
>Creating --- Sieve of Atkin Version 0.02 ---
>
>Try: SieveOfAtkin .
> PRIMES ok
>FORTH> SieveOfAtkin . 1900 ok
>FORTH> PRIMES
>1000 iterations.
>1900 primes found, 94 ms elapsed. ok
>
>FORTH> in sieve
>Creating --- SIEVE benchmark Version 1.00 ---
>Redefining `#times`
>Redefining `PRIMES`
>
>Sieve (100 iterations)
> Compile time Run time Primes
> Par.C 38.19 8.732 1899
> Inmos ICC 83.98 9.578 1899
> 3L C 45.25 5.955 1899
> tForth (WS) 1.00 7.244 1899
> tForth (main) 1.00 9.253 1899
> iForth 386/33 0.3 5.767 1899
> iForth 486/50 0.1 1.595 1899
> iForth 486/66 0.1 1.559 1899
> iForth P5/200 0.1 0.195 1899
> iForth PIV/3G 0.1 0.076 1899
>
>Enter PRIMES to run the benchmark.
> ok
>FORTH> PRIMES
>1000 iterations.
>1899 primes found, 12 ms elapsed. ok
>FORTH>
>
>Out of the box, Atkin is 94 / 12 ~ 8x slower than the standard Sieve algorithm.
>The standard algorithm needs no division, so it will work for limit >
>2^64, while
>Atkin must be extended for that.

This the deception for those who inspect the O(n) behaviour.
Maybe Atkin uses less operations for n to infinity, there is a
constant C in front, that can count instructions needed for
a single operation.
That may mean -- as you have demonstrated -- that over a practical
range the O(n) doesn't tell the whole story.

>
>-marcel

Groetjes Albert
--
"in our communism country Viet Nam, people are forced to be
alive and in the western country like US, people are free to
die from Covid 19 lol" duc ha
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

Re: Sieve of Atkin

<e74f58ed-4553-4772-88ff-c15d4f4ff601n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17952&group=comp.lang.forth#17952

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:622a:3c6:b0:2f3:f7d6:63e0 with SMTP id k6-20020a05622a03c600b002f3f7d663e0mr13580277qtx.530.1653225019359;
Sun, 22 May 2022 06:10:19 -0700 (PDT)
X-Received: by 2002:a05:6214:130d:b0:461:c9ee:a9e7 with SMTP id
a13-20020a056214130d00b00461c9eea9e7mr13969216qvv.58.1653225019148; Sun, 22
May 2022 06:10:19 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sun, 22 May 2022 06:10:19 -0700 (PDT)
In-Reply-To: <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=176.93.128.15; posting-account=kiOBZQoAAADFsAs31ZHaefxTuQxv84Wm
NNTP-Posting-Host: 176.93.128.15
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com> <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <e74f58ed-4553-4772-88ff-c15d4f4ff601n@googlegroups.com>
Subject: Re: Sieve of Atkin
From: jali.hei...@gmail.com (Jali Heinonen)
Injection-Date: Sun, 22 May 2022 13:10:19 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Jali Heinonen - Sun, 22 May 2022 13:10 UTC

sunnuntai 22. toukokuuta 2022 klo 0.02.26 UTC+3 Marcel Hendrix kirjoitti:
> On Saturday, May 21, 2022 at 6:28:54 PM UTC+2, Jali Heinonen wrote:
> > perjantai 20. toukokuuta 2022 klo 15.53.26 UTC+3 Marcel Hendrix kirjoitti:
> > > Apparently the fastest possible Sieve (in the limit).
> > > https://www.baeldung.com/cs/prime-number-algorithms .
> > >
> > > Unfortunately, the pseudo-code (?) is somewhat ambiguous.
> > >
> > > -marcel
> > Is it really faster than sieve implementation that is wheel factorized to the max?
> Well, so much for CS.
>
> I adapted both Atkin and the standard Sieve so that I could run them with
> array sizes between 1k and 10GByte, with the following results:
>
> Standard Sieve:
> n runtime (ms) primes
> 1,000 0 302
> 10,000 0 2,261
> 100,000 0 17,983
> 1,000,000 3 148,932
> 10,000,000 29 1,270,606
> 100,000,000 962 11,078,936
> 1,000,000,000 12695 98,222,286
> 10,000,000,000 149099 882,206,715
>
> Atkin Sieve
> n runtime (ms) primes
> 1,000 0 168
> 10,000 0 1,229
> 100,000 0 9,592
> 1,000,000 4 78,498
> 10,000,000 60 664,579
> 100,000,000 1728 5,761,455
> 1,000,000,000 20900 50,847,534
> 10,000,000,000 301417 455,052,511
>
> Atkin is about 4 times slower than the Standard Sieve (50% of the
> results in twice the time). It might slowly increase for even larger
> sieves, but with 20 GBytes there is not much evidence for that yet.
> Maybe somebody with a TB of RAM has more luck.
>
> The jump in runtime between 0.1GB and 1GB might have something to do
> with the working-set default of a Windows program (I see no evidence
> of disk-activity but ALLOCATE takes noticeably longer).
>
> Here is the final SieveOfAtkin. I fixed a bug that had to do with Python's
> logic operators apparently taking shortcuts without being told.
> (*
> * LANGUAGE : ANS Forth with extensions
> * PROJECT : Forth Environments
> * DESCRIPTION : Sieve of Atkin, fastest Sieve O(n)
> * CATEGORY : Example
> * AUTHOR : Marcel Hendrix
> * LAST CHANGE : Saturday, May 21, 2022, 9:54 AM, mhx;
> *)
>
>
> NEEDS -miscutil
> REVISION -sieveofatkin "--- Sieve of Atkin Version 0.04 ---"
>
> PRIVATES
>
> DOC
> (*
> n runtime (ms) primes
> 1,000 0 168
> 10,000 0 1,229
> 100,000 0 9,592
> 1,000,000 4 78,498
> 10,000,000 60 664,579
> 100,000,000 1728 5,761,455
> 1,000,000,000 20900 50,847,534
> 10,000,000,000 301417 455,052,511
> *)
> ENDDOC
>
> DEPTH 0= [IF] CR .( Stack Empty) ABORT [THEN]
> ( #16384 ) =: limit PRIVATE
> #1 =: #times PRIVATE
> limit SQRT 2+ =: SQRT(limit+2) PRIVATE
> limit SQRT 1+ =: SQRT(limit+1) PRIVATE
> limit 1+ ALLOCATE ?ALLOCATE =: sieve PRIVATE
> limit 1+ ALLOCATE ?ALLOCATE =: mods PRIVATE
>
> : set# ( -- ) limit 2+ 0 DO I #12 MOD mods I + C! LOOP ; PRIVATE set#
> : init ( -- ) sieve limit 1+ ERASE ( set# ) ; PRIVATE
> : flip ( ix -- ) sieve + DUP C@ NOT SWAP C! ; PRIVATE
> : fi1 ( I J -- u ) SQR 4 * SWAP SQR + ; PRIVATE
> : fi2 ( I J -- u ) SQR 3 * SWAP SQR + ; PRIVATE
> : fi3 ( I J -- u ) SQR 3 * SWAP SQR - ; PRIVATE
> : #MOD ( s -- u ) mods + C@ ; PRIVATE
> : test1 ( s -- ) DUP limit > IF DROP ELSE >S S #MOD DUP 1 = SWAP 5 = OR IF S flip ENDIF -S ENDIF ; PRIVATE
> : test2 ( s -- ) DUP limit > IF DROP ELSE >S S #MOD 7 = IF S flip ENDIF -S ENDIF ; PRIVATE
> : +test3 ( s ? -- ) OVER limit > OR IF DROP ELSE >S S #MOD #11 = IF S flip ENDIF -S ENDIF ; PRIVATE
> : no-p^2 ( -- ) SQRT(limit+1) 5 DO sieve I + C@ IF limit 2+ I SQR DO sieve I + C0! J SQR +LOOP ENDIF LOOP ; PRIVATE
> : cnt ( -- u ) 2 ( 2 and 3 ) limit 1+ 5 DO sieve I + C@ 1 AND + LOOP ; PRIVATE
>
> : SieveOfAtkin ( -- u )
> init
> SQRT(limit+2)
> 1 DO SQRT(limit+2)
> 1 DO I J fi1 test1
> I J fi2 test2
> I J fi3 J I <= +test3
> LOOP
> LOOP
> no-p^2
> cnt ( sz) ;
>
> : PRIMES CR #times DEC. ." iterations." TIMER-RESET
> 0 #times 0 DO DROP SieveOfAtkin LOOP
> MS? SWAP CR . ." primes found, " DEC. ." ms elapsed." ;
>
> :ABOUT CR ." Try: SieveOfAtkin . "
> CR ." PRIMES " ;
>
> NESTING @ 1 = [IF] .ABOUT -sieveofatkin [THEN]
>
> DEPRIVE
>
> (* End of Source *)
>
> -marcel

I adapted some code using wheel factorization for testing primes from the Inferno operating system sources for the 8th programming language.
Available here: https://www.dropbox.com/s/96c58nykffo0wuu/wheel.8th?dl=0

I have not done any timings as I currently have only RPI 4B board available for testing. Seems fast though and I would be surprised if it can't match the Sieve of Atkins.

Re: Sieve of Atkin

<fb27f4c7-1e35-4106-8079-12ebc9af8c23n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17953&group=comp.lang.forth#17953

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:622a:e:b0:2f3:d236:56dc with SMTP id x14-20020a05622a000e00b002f3d23656dcmr13822164qtw.187.1653231225271;
Sun, 22 May 2022 07:53:45 -0700 (PDT)
X-Received: by 2002:a05:622a:591:b0:2f3:d8fc:1967 with SMTP id
c17-20020a05622a059100b002f3d8fc1967mr13542787qtb.353.1653231225098; Sun, 22
May 2022 07:53:45 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sun, 22 May 2022 07:53:44 -0700 (PDT)
In-Reply-To: <e74f58ed-4553-4772-88ff-c15d4f4ff601n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:fdb3:573e:70d2:aa43;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:fdb3:573e:70d2:aa43
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com> <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>
<e74f58ed-4553-4772-88ff-c15d4f4ff601n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <fb27f4c7-1e35-4106-8079-12ebc9af8c23n@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Sun, 22 May 2022 14:53:45 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Marcel Hendrix - Sun, 22 May 2022 14:53 UTC

On Sunday, May 22, 2022 at 3:10:20 PM UTC+2, Jali Heinonen wrote:
[..]
> I adapted some code using wheel factorization for testing primes from the Inferno
> operating system sources for the 8th programming language.
> Available here: https://www.dropbox.com/s/96c58nykffo0wuu/wheel.8th?dl=0

9007199254740992 constant bigx
....
> I have not done any timings as I currently have only RPI 4B board available for testing.
> Seems fast though and I would be surprised if it can't match the Sieve of Atkins.

Well, let us know when you get to it. Generating between 10M or 100M primes
should provide some relevant timings, 10G would be better though.

-marcel

Re: Sieve of Atkin

<f02d77ba-28ee-4af8-9d7d-a17246b880b7n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17954&group=comp.lang.forth#17954

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:6214:23c9:b0:461:c9e7:9cd6 with SMTP id hr9-20020a05621423c900b00461c9e79cd6mr14050013qvb.116.1653232679751;
Sun, 22 May 2022 08:17:59 -0700 (PDT)
X-Received: by 2002:a37:5805:0:b0:69f:c640:f5e8 with SMTP id
m5-20020a375805000000b0069fc640f5e8mr11525673qkb.586.1653232679616; Sun, 22
May 2022 08:17:59 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sun, 22 May 2022 08:17:59 -0700 (PDT)
In-Reply-To: <nnd$4435a412$60078c44@b615e5bcc1c0105a>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:fdb3:573e:70d2:aa43;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:fdb3:573e:70d2:aa43
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<5697422a-9791-480d-a136-c56dc7a2fa28n@googlegroups.com> <t69hm8$1bib$1@gioia.aioe.org>
<4efed8c0-d736-42dd-9627-0913aece17edn@googlegroups.com> <nnd$4435a412$60078c44@b615e5bcc1c0105a>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <f02d77ba-28ee-4af8-9d7d-a17246b880b7n@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Sun, 22 May 2022 15:17:59 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2548
 by: Marcel Hendrix - Sun, 22 May 2022 15:17 UTC

On Sunday, May 22, 2022 at 10:57:09 AM UTC+2, none albert wrote:
[..]
> >Out of the box, Atkin is 94 / 12 ~ 8x slower than the standard Sieve algorithm.
> >The standard algorithm needs no division, so it will work for limit >
> >2^64, while
> >Atkin must be extended for that.
> This the deception for those who inspect the O(n) behaviour.
> Maybe Atkin uses less operations for n to infinity, there is a
> constant C in front, that can count instructions needed for
> a single operation.
> That may mean -- as you have demonstrated -- that over a practical
> range the O(n) doesn't tell the whole story.

It was a bit of a surprise to me that it was so slow, given that the reference
to this method came from a prime thread on the GMP mailing list.

It is not easy to see which instructions are slow, given that the operation
count is indeed minimal. The division operation is replaced by a lookup table,
(building it leads to an imperceptible delay when loading the source file)
as I assume that a fast MOD was possible. Multiplication is nowadays
1 or 2 cycles, so I guess it must there is an ugly memory access problem,
a stalled pipeline, or serious data dependencies.

-marcel

Re: Sieve of Atkin

<cdf39213-8ec5-48af-b0b6-39285582cfd6n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17955&group=comp.lang.forth#17955

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:6214:1d03:b0:462:117f:60a0 with SMTP id e3-20020a0562141d0300b00462117f60a0mr9173190qvd.93.1653239469668;
Sun, 22 May 2022 10:11:09 -0700 (PDT)
X-Received: by 2002:a37:c01:0:b0:6a3:4aaa:1e21 with SMTP id
1-20020a370c01000000b006a34aaa1e21mr7742321qkm.378.1653239469453; Sun, 22 May
2022 10:11:09 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sun, 22 May 2022 10:11:09 -0700 (PDT)
In-Reply-To: <fb27f4c7-1e35-4106-8079-12ebc9af8c23n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=176.93.128.15; posting-account=kiOBZQoAAADFsAs31ZHaefxTuQxv84Wm
NNTP-Posting-Host: 176.93.128.15
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com> <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>
<e74f58ed-4553-4772-88ff-c15d4f4ff601n@googlegroups.com> <fb27f4c7-1e35-4106-8079-12ebc9af8c23n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <cdf39213-8ec5-48af-b0b6-39285582cfd6n@googlegroups.com>
Subject: Re: Sieve of Atkin
From: jali.hei...@gmail.com (Jali Heinonen)
Injection-Date: Sun, 22 May 2022 17:11:09 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2512
 by: Jali Heinonen - Sun, 22 May 2022 17:11 UTC

sunnuntai 22. toukokuuta 2022 klo 17.53.46 UTC+3 Marcel Hendrix kirjoitti:
> On Sunday, May 22, 2022 at 3:10:20 PM UTC+2, Jali Heinonen wrote:
> [..]
> > I adapted some code using wheel factorization for testing primes from the Inferno
> > operating system sources for the 8th programming language.
> > Available here: https://www.dropbox.com/s/96c58nykffo0wuu/wheel.8th?dl=0
> 9007199254740992 constant bigx
> ...
> > I have not done any timings as I currently have only RPI 4B board available for testing.
> > Seems fast though and I would be surprised if it can't match the Sieve of Atkins.
> Well, let us know when you get to it. Generating between 10M or 100M primes
> should provide some relevant timings, 10G would be better though.
>
> -marcel

I tested with generating first million primes on my RPI 4B and redirecting output into text file. Resulting time is over eight times faster than the time mentioned in your source listing and that time includes program startup and writing primes into file:

root@DietPi:~# time /opt/8th/bin/rpi64/8th wheel.8th 0 15485863 >temp.txt

real 0m57.158s
user 0m45.213s
sys 0m11.268s

Re: Sieve of Atkin

<2022May22.190555@mips.complang.tuwien.ac.at>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17956&group=comp.lang.forth#17956

 copy link   Newsgroups: comp.lang.forth
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.lang.forth
Subject: Re: Sieve of Atkin
Date: Sun, 22 May 2022 17:05:55 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 77
Message-ID: <2022May22.190555@mips.complang.tuwien.ac.at>
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com> <5697422a-9791-480d-a136-c56dc7a2fa28n@googlegroups.com> <t69hm8$1bib$1@gioia.aioe.org> <4efed8c0-d736-42dd-9627-0913aece17edn@googlegroups.com> <nnd$4435a412$60078c44@b615e5bcc1c0105a> <f02d77ba-28ee-4af8-9d7d-a17246b880b7n@googlegroups.com>
Injection-Info: reader02.eternal-september.org; posting-host="8241a6e5816418ac47af082a8fb0d782";
logging-data="25225"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX181BkA8hg9QsxflcdX+koq8"
Cancel-Lock: sha1:O6JUiRiGlaiFsr1ZVLoE1ME4rUw=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Sun, 22 May 2022 17:05 UTC

Marcel Hendrix <mhx@iae.nl> writes:
>Multiplication is nowadays
>1 or 2 cycles

More like 4.

> so I guess it must there is an ugly memory access problem,

Numbers from a Skylake:

[~/forth:130297] perf stat -e instructions -e cycles -e L1-dcache-load-misses -e LLC-load-misses iforth "1000000000 include $HOME/forth/sieveofatkin.4th primes bye"

Try: SieveOfAtkin .
PRIMES
1 iterations.
50847534 primes found, 19671 ms elapsed.

[~/forth:130300] perf stat -e instructions -e cycles -e L1-dcache-loads -e L1-dcache-load-misses -e LLC-load-misses iforth "1000000000 include $HOME/forth/sieveofatkin.4th primes bye"

Try: SieveOfAtkin .
PRIMES
1 iterations.
50847534 primes found, 19662 ms elapsed.

Performance counter stats for 'iforth 1000000000 include /home/anton/forth/sieveofatkin.4th primes bye':

91673986439 instructions # 0.82 insn per cycle
111163950818 cycles
23659587244 L1-dcache-loads
1907344675 L1-dcache-load-misses # 8.06% of all L1-dcache accesses
1340041914 LLC-load-misses

27.797359314 seconds time elapsed

27.607640000 seconds user
0.184024000 seconds sys

So 91 instructions, 111 cycles and 1.34 main memory accesses per
number under consideration; yes, it could be all these cache misses
(actually, with this many cache misses, it could be quite a bit worse;
there seems to be some memory-level parallelism going on). Have you
considered doing it piecewise, in cache-sized pieces? That made
Erathostenes quite a bit faster.

I also notice that you apparently don't measure the time for erasing
the memory.

Let's see about scalability:

[~/forth:130301] perf stat -e instructions -e cycles -e L1-dcache-loads -e L1-dcache-load-misses -e LLC-load-misses iforth "100000000 include $HOME/forth/sieveofatkin.4th primes bye"

Try: SieveOfAtkin .
PRIMES
1 iterations.
5761455 primes found, 1900 ms elapsed.

Performance counter stats for 'iforth 100000000 include /home/anton/forth/sieveofatkin.4th primes bye':

9516883875 instructions # 0.85 insn per cycle
11136639151 cycles
2477917529 L1-dcache-loads
197185830 L1-dcache-load-misses # 7.96% of all L1-dcache accesses
119105185 LLC-load-misses

2.791729605 seconds time elapsed

2.754480000 seconds user
0.032028000 seconds sys

10 times smaller, 10 times less time, just as O(n) predicts.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2021: https://euro.theforth.net/2021

Re: Sieve of Atkin

<f51caf9b-2f56-4084-8539-377dc0ae75d3n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17957&group=comp.lang.forth#17957

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:6214:14aa:b0:461:c3eb:c3c9 with SMTP id bo10-20020a05621414aa00b00461c3ebc3c9mr14789710qvb.88.1653244751880;
Sun, 22 May 2022 11:39:11 -0700 (PDT)
X-Received: by 2002:a05:622a:591:b0:2f3:d8fc:1967 with SMTP id
c17-20020a05622a059100b002f3d8fc1967mr13997115qtb.353.1653244751768; Sun, 22
May 2022 11:39:11 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sun, 22 May 2022 11:39:11 -0700 (PDT)
In-Reply-To: <cdf39213-8ec5-48af-b0b6-39285582cfd6n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:fdb3:573e:70d2:aa43;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:fdb3:573e:70d2:aa43
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com> <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>
<e74f58ed-4553-4772-88ff-c15d4f4ff601n@googlegroups.com> <fb27f4c7-1e35-4106-8079-12ebc9af8c23n@googlegroups.com>
<cdf39213-8ec5-48af-b0b6-39285582cfd6n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <f51caf9b-2f56-4084-8539-377dc0ae75d3n@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Sun, 22 May 2022 18:39:11 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2455
 by: Marcel Hendrix - Sun, 22 May 2022 18:39 UTC

On Sunday, May 22, 2022 at 7:11:10 PM UTC+2, Jali Heinonen wrote:
> sunnuntai 22. toukokuuta 2022 klo 17.53.46 UTC+3 Marcel Hendrix kirjoitti:
> > On Sunday, May 22, 2022 at 3:10:20 PM UTC+2, Jali Heinonen wrote:
[..]
> I tested with generating first million primes on my RPI 4B and redirecting output
> into text file. Resulting time is over eight times faster than the time mentioned in
> your source listing and that time includes program startup and writing primes into file:
>
> root@DietPi:~# time /opt/8th/bin/rpi64/8th wheel.8th 0 15485863 >temp.txt
>
> real 0m57.158s
> user 0m45.213s
> sys 0m11.268s

That is 57 *seconds*, with n=15,485,863, and finds 1,000,000 primes?
Note that Forth's Atkin (above in the thread) does that in ~120 *milliseconds*,
on an AMD Ryzen 7 5800X. According to Geekbench V, single-core 64bit, the
expected difference with an RPI 4B is about 8x. Something must be wrong.

It would be better to compare to the Standard Sieve?

-marcel

Re: Sieve of Atkin

<5cd3127f-8834-41b3-ba05-d56351dd5ab4n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17958&group=comp.lang.forth#17958

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:ac8:5f83:0:b0:2f3:dc9e:bb43 with SMTP id j3-20020ac85f83000000b002f3dc9ebb43mr14383364qta.171.1653245926320;
Sun, 22 May 2022 11:58:46 -0700 (PDT)
X-Received: by 2002:a05:622a:147:b0:2f9:2ad3:1209 with SMTP id
v7-20020a05622a014700b002f92ad31209mr6024226qtw.388.1653245926192; Sun, 22
May 2022 11:58:46 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sun, 22 May 2022 11:58:45 -0700 (PDT)
In-Reply-To: <2022May22.190555@mips.complang.tuwien.ac.at>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:fdb3:573e:70d2:aa43;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:fdb3:573e:70d2:aa43
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<5697422a-9791-480d-a136-c56dc7a2fa28n@googlegroups.com> <t69hm8$1bib$1@gioia.aioe.org>
<4efed8c0-d736-42dd-9627-0913aece17edn@googlegroups.com> <nnd$4435a412$60078c44@b615e5bcc1c0105a>
<f02d77ba-28ee-4af8-9d7d-a17246b880b7n@googlegroups.com> <2022May22.190555@mips.complang.tuwien.ac.at>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <5cd3127f-8834-41b3-ba05-d56351dd5ab4n@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Sun, 22 May 2022 18:58:46 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Marcel Hendrix - Sun, 22 May 2022 18:58 UTC

On Sunday, May 22, 2022 at 7:43:01 PM UTC+2, Anton Ertl wrote:
[..]
> So 91 instructions, 111 cycles and 1.34 main memory accesses per
> number under consideration; yes, it could be all these cache misses
> (actually, with this many cache misses, it could be quite a bit worse;
> there seems to be some memory-level parallelism going on). Have you
> considered doing it piecewise, in cache-sized pieces? That made
> Erathostenes quite a bit faster.

That would be real work, I would need to sieve in batches. Maybe
I don't understand what you mean.

> I also notice that you apparently don't measure the time for erasing
> the memory.

That is included, but I don't count the time to build the MOD lookup.

> Let's see about scalability:
>
> [~/forth:130301] perf stat -e instructions -e cycles -e L1-dcache-loads -e L1-dcache-load-misses -e LLC-load-misses iforth "100000000 include $HOME/forth/sieveofatkin.4th primes bye"
>
> Try: SieveOfAtkin .
> PRIMES
> 1 iterations.
> 5761455 primes found, 1900 ms elapsed.
[..]
> 10 times smaller, 10 times less time, just as O(n) predicts.

On my AMD 5800X the interesting gap is between 10,000,000
and 100,000,000, but thanks anyway.

-marcel

Re: Sieve of Atkin

<2022May22.202124@mips.complang.tuwien.ac.at>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17959&group=comp.lang.forth#17959

 copy link   Newsgroups: comp.lang.forth
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.lang.forth
Subject: Re: Sieve of Atkin
Date: Sun, 22 May 2022 18:21:24 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 34
Message-ID: <2022May22.202124@mips.complang.tuwien.ac.at>
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com> <66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com> <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>
Injection-Info: reader02.eternal-september.org; posting-host="8241a6e5816418ac47af082a8fb0d782";
logging-data="32277"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/SR1oROPCOqWXe/griq62b"
Cancel-Lock: sha1:xAoNdeEC9jPrb0i+MG/ccTSRkKM=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Sun, 22 May 2022 18:21 UTC

Marcel Hendrix <mhx@iae.nl> writes:
>Here is the final SieveOfAtkin.

I have made it portable to Gforth, lxf, sf, vfx64, and posted the
result on
<https://www.complang.tuwien.ac.at/forth/programs/sieveofatkin.fs>.
Basically all things that I changed, except for the timing code, are
gratuitious incompatibilities.

Results on a Ryzen 5800X (LLC-dcache-load-miss not supported) for n=1e8:

cyc inst load L1 miss
gforth-fast 33,784,978,330 50,096,698,991 14,716,155,398 157,613,972
iforth 8,949,528,121 9,643,635,252 1,459,076,700 163,122,475
lxf 17,879,785,896 15,849,776,266 4,578,122,141 157,093,923
sf 22,653,189,337 20,410,579,910 6,135,891,074 158,402,472
vfx64 8,896,377,480 9,533,502,029 1,212,120,001 155,895,135

Cache misses don't seem to limit the performance, otherwise the cycle
differences between the Forth systems would be much smaller.

Command lines:
LC_NUMERIC=en_US.utf8 perf stat -e instructions -e cycles -e L1-dcache-loads -e L1-dcache-load-misses gforth-fast -e "100000000 include /nfs/unsafe/httpd/ftp/pub/forth/programs/sieveofatkin.fs primes bye"
LC_NUMERIC=en_US.utf8 perf stat -e instructions -e cycles -e L1-dcache-loads -e L1-dcache-load-misses iforth "100000000 include /nfs/unsafe/httpd/ftp/pub/forth/programs/sieveofatkin.fs primes bye"
LC_NUMERIC=en_US.utf8 perf stat -e instructions -e cycles -e L1-dcache-loads -e L1-dcache-load-misses lxf "100000000 include /nfs/unsafe/httpd/ftp/pub/forth/programs/sieveofatkin.fs primes bye"
LC_NUMERIC=en_US.utf8 perf stat -e instructions -e cycles -e L1-dcache-loads -e L1-dcache-load-misses sf "include /nfs/nfstmp/anton/SwiftForth-3.11.0/lib/options/fpmath.f 100000000 include /nfs/unsafe/httpd/ftp/pub/forth/programs/sieveofatkin.fs primes bye"
LC_NUMERIC=en_US.utf8 perf stat -e instructions -e cycles -e L1-dcache-loads -e L1-dcache-load-misses vfx64 "100000000 include /nfs/unsafe/httpd/ftp/pub/forth/programs/sieveofatkin.fs primes bye"

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2021: https://euro.theforth.net/2021

Re: Sieve of Atkin

<f6fba233-5e85-404b-95b2-0a5d68dde8fan@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17960&group=comp.lang.forth#17960

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:620a:c99:b0:6a3:3c41:2d6 with SMTP id q25-20020a05620a0c9900b006a33c4102d6mr10029978qki.744.1653247196541;
Sun, 22 May 2022 12:19:56 -0700 (PDT)
X-Received: by 2002:ad4:5dc3:0:b0:462:3a57:b787 with SMTP id
m3-20020ad45dc3000000b004623a57b787mr1974627qvh.117.1653247196306; Sun, 22
May 2022 12:19:56 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sun, 22 May 2022 12:19:56 -0700 (PDT)
In-Reply-To: <f51caf9b-2f56-4084-8539-377dc0ae75d3n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=176.93.128.15; posting-account=kiOBZQoAAADFsAs31ZHaefxTuQxv84Wm
NNTP-Posting-Host: 176.93.128.15
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com> <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>
<e74f58ed-4553-4772-88ff-c15d4f4ff601n@googlegroups.com> <fb27f4c7-1e35-4106-8079-12ebc9af8c23n@googlegroups.com>
<cdf39213-8ec5-48af-b0b6-39285582cfd6n@googlegroups.com> <f51caf9b-2f56-4084-8539-377dc0ae75d3n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <f6fba233-5e85-404b-95b2-0a5d68dde8fan@googlegroups.com>
Subject: Re: Sieve of Atkin
From: jali.hei...@gmail.com (Jali Heinonen)
Injection-Date: Sun, 22 May 2022 19:19:56 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 3012
 by: Jali Heinonen - Sun, 22 May 2022 19:19 UTC

sunnuntai 22. toukokuuta 2022 klo 21.39.12 UTC+3 Marcel Hendrix kirjoitti:
> On Sunday, May 22, 2022 at 7:11:10 PM UTC+2, Jali Heinonen wrote:
> > sunnuntai 22. toukokuuta 2022 klo 17.53.46 UTC+3 Marcel Hendrix kirjoitti:
> > > On Sunday, May 22, 2022 at 3:10:20 PM UTC+2, Jali Heinonen wrote:
> [..]
> > I tested with generating first million primes on my RPI 4B and redirecting output
> > into text file. Resulting time is over eight times faster than the time mentioned in
> > your source listing and that time includes program startup and writing primes into file:
> >
> > root@DietPi:~# time /opt/8th/bin/rpi64/8th wheel.8th 0 15485863 >temp.txt
> >
> > real 0m57.158s
> > user 0m45.213s
> > sys 0m11.268s
> That is 57 *seconds*, with n=15,485,863, and finds 1,000,000 primes?
> Note that Forth's Atkin (above in the thread) does that in ~120 *milliseconds*,
> on an AMD Ryzen 7 5800X. According to Geekbench V, single-core 64bit, the
> expected difference with an RPI 4B is about 8x. Something must be wrong.
>
> It would be better to compare to the Standard Sieve?
>
> -marcel

Can your Forth version really find all the 1,000,000 prime numbers between number range of 0 - 15,485,863, output all the prime numbers as formatted line of text and redirect output into text file in about 120 milliseconds? Interesting as running empty program on my RPI 4B takes about 177 milliseconds.

Re: Sieve of Atkin

<f450b8c4-8757-4f40-ab23-0e7898f3f24dn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17961&group=comp.lang.forth#17961

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:ac8:5d8b:0:b0:2f3:df07:d752 with SMTP id d11-20020ac85d8b000000b002f3df07d752mr14186502qtx.528.1653248802569;
Sun, 22 May 2022 12:46:42 -0700 (PDT)
X-Received: by 2002:a37:9e0f:0:b0:6a3:4918:d394 with SMTP id
h15-20020a379e0f000000b006a34918d394mr8518870qke.764.1653248802432; Sun, 22
May 2022 12:46:42 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sun, 22 May 2022 12:46:42 -0700 (PDT)
In-Reply-To: <f6fba233-5e85-404b-95b2-0a5d68dde8fan@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:fdb3:573e:70d2:aa43;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:fdb3:573e:70d2:aa43
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com> <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>
<e74f58ed-4553-4772-88ff-c15d4f4ff601n@googlegroups.com> <fb27f4c7-1e35-4106-8079-12ebc9af8c23n@googlegroups.com>
<cdf39213-8ec5-48af-b0b6-39285582cfd6n@googlegroups.com> <f51caf9b-2f56-4084-8539-377dc0ae75d3n@googlegroups.com>
<f6fba233-5e85-404b-95b2-0a5d68dde8fan@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <f450b8c4-8757-4f40-ab23-0e7898f3f24dn@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Sun, 22 May 2022 19:46:42 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2200
 by: Marcel Hendrix - Sun, 22 May 2022 19:46 UTC

On Sunday, May 22, 2022 at 9:19:57 PM UTC+2, Jali Heinonen wrote:
[..]
> Can your Forth version really find all the 1,000,000 prime numbers between number
> range of 0 - 15,485,863, output all the prime numbers as formatted line of text and
> redirect output into text file in about 120 milliseconds? Interesting as running empty
> program on my RPI 4B takes about 177 milliseconds.

I don't know about "and redirect output into text file", I would write-file to stdout if that
is an allowed scenario? Bare numbers are independently duplicated by Anton
in this thread for several Forth systems, including iForth.

-marcel

Re: Sieve of Atkin

<0adb4fe8-b948-4216-98b0-c6d91c474527n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17962&group=comp.lang.forth#17962

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:6214:ac7:b0:462:1edc:a1cf with SMTP id g7-20020a0562140ac700b004621edca1cfmr6604321qvi.82.1653250060252;
Sun, 22 May 2022 13:07:40 -0700 (PDT)
X-Received: by 2002:ac8:5cca:0:b0:2f9:ca3:f35e with SMTP id
s10-20020ac85cca000000b002f90ca3f35emr14828406qta.432.1653250060052; Sun, 22
May 2022 13:07:40 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sun, 22 May 2022 13:07:39 -0700 (PDT)
In-Reply-To: <20220520164842.3d49149a@t530>
Injection-Info: google-groups.googlegroups.com; posting-host=176.93.128.15; posting-account=kiOBZQoAAADFsAs31ZHaefxTuQxv84Wm
NNTP-Posting-Host: 176.93.128.15
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com> <20220520164842.3d49149a@t530>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <0adb4fe8-b948-4216-98b0-c6d91c474527n@googlegroups.com>
Subject: Re: Sieve of Atkin
From: jali.hei...@gmail.com (Jali Heinonen)
Injection-Date: Sun, 22 May 2022 20:07:40 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 1919
 by: Jali Heinonen - Sun, 22 May 2022 20:07 UTC

perjantai 20. toukokuuta 2022 klo 18.48.44 UTC+3 Jan Coombs kirjoitti:
> On Fri, 20 May 2022 05:53:24 -0700 (PDT)
> Marcel Hendrix <m...@iae.nl> wrote:
>
> > Apparently the fastest possible Sieve (in the limit).
> > https://www.baeldung.com/cs/prime-number-algorithms .
> >
> > Unfortunately, the pseudo-code (?) is somewhat ambiguous.
> The explanation is good, thanks. This seems to work, how's your python?
>
> This is the optimized implementation proposed by Zsolt KOVACS:
> from:
> https://stackoverflow.com/questions/21783160/sieve-of-atkin-implementation-in-python
Does this linked Python code really work? With upper limit of 229 it seems to find the following primes:

[2, 3, 5, 7, 13, 19, 29, 53, 67, 85, 103, 173, 199]

There should 50 primes, not 13 primes?

Re: Sieve of Atkin

<a26cf280-be0f-452c-9c80-2a35c230e248n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17964&group=comp.lang.forth#17964

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:620a:98a:b0:6a3:840f:96d1 with SMTP id x10-20020a05620a098a00b006a3840f96d1mr1705097qkx.286.1653251058506;
Sun, 22 May 2022 13:24:18 -0700 (PDT)
X-Received: by 2002:ad4:5967:0:b0:462:10a3:cbf6 with SMTP id
eq7-20020ad45967000000b0046210a3cbf6mr9668568qvb.127.1653251058342; Sun, 22
May 2022 13:24:18 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sun, 22 May 2022 13:24:18 -0700 (PDT)
In-Reply-To: <f6fba233-5e85-404b-95b2-0a5d68dde8fan@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:fdb3:573e:70d2:aa43;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:fdb3:573e:70d2:aa43
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com> <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>
<e74f58ed-4553-4772-88ff-c15d4f4ff601n@googlegroups.com> <fb27f4c7-1e35-4106-8079-12ebc9af8c23n@googlegroups.com>
<cdf39213-8ec5-48af-b0b6-39285582cfd6n@googlegroups.com> <f51caf9b-2f56-4084-8539-377dc0ae75d3n@googlegroups.com>
<f6fba233-5e85-404b-95b2-0a5d68dde8fan@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <a26cf280-be0f-452c-9c80-2a35c230e248n@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Sun, 22 May 2022 20:24:18 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2632
 by: Marcel Hendrix - Sun, 22 May 2022 20:24 UTC

On Sunday, May 22, 2022 at 9:19:57 PM UTC+2, Jali Heinonen wrote:
[..]
> Can your Forth version really find all the 1,000,000 prime numbers between number
> range of 0 - 15,485,863, output all the prime numbers as formatted line of text and
> redirect output into text file in about 120 milliseconds? Interesting as running empty
> program on my RPI 4B takes about 177 milliseconds.

Outputting a million primes is indeed slower than the original ~120 ms (about 25 times).
Other Forths can probably do this much faster as iForth is made to flush the output file.

FORTH> in sieveofatkin
Creating --- Sieve of Atkin Version 0.04 ---

Try: SieveOfAtkin .
PRIMES ok
FORTH> PRIMES
1 iterations.
1000000 primes found, 3204 ms elapsed. ok
FORTH>

Here's how:
: write ( -- )
S" primes.txt" R/W BIN CREATE-FILE ?FILE out-FD !
FILE-I//O SET-IODEVICE
limit 1+ 2 DO sieve I + C@ IF I . ENDIF LOOP
out-FD @ CLOSE-FILE -1 out-FD ! ?FILE
STD-I//O SET-IODEVICE ;

... where "write" is made the last word of SieveOfAtkin

-marcel

Re: Sieve of Atkin

<d1b204e1-4561-4af4-bde9-d630d97364f7n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17965&group=comp.lang.forth#17965

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:6214:e6b:b0:45b:474:1035 with SMTP id jz11-20020a0562140e6b00b0045b04741035mr15191949qvb.39.1653251572241;
Sun, 22 May 2022 13:32:52 -0700 (PDT)
X-Received: by 2002:ac8:7fc2:0:b0:2f3:d47d:487c with SMTP id
b2-20020ac87fc2000000b002f3d47d487cmr14238662qtk.157.1653251572085; Sun, 22
May 2022 13:32:52 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Sun, 22 May 2022 13:32:51 -0700 (PDT)
In-Reply-To: <0adb4fe8-b948-4216-98b0-c6d91c474527n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:fdb3:573e:70d2:aa43;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:fdb3:573e:70d2:aa43
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<20220520164842.3d49149a@t530> <0adb4fe8-b948-4216-98b0-c6d91c474527n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <d1b204e1-4561-4af4-bde9-d630d97364f7n@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Sun, 22 May 2022 20:32:52 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 1885
 by: Marcel Hendrix - Sun, 22 May 2022 20:32 UTC

On Sunday, May 22, 2022 at 10:07:41 PM UTC+2, Jali Heinonen wrote:
[..]
> > https://stackoverflow.com/questions/21783160/sieve-of-atkin-implementation-in-python
> Does this linked Python code really work? With upper limit of 229 it seems to find the following primes:
>
> [2, 3, 5, 7, 13, 19, 29, 53, 67, 85, 103, 173, 199]
>
> There should 50 primes, not 13 primes?

From primes.txt:
2 3 5 7 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 113 127 131 137 139 149 151 157 163 167
173 179 181 191 193 197 199 211 223 227 229

I guess that will up the runtime a few notches :--)

-marcel

Re: Sieve of Atkin

<2022May22.212841@mips.complang.tuwien.ac.at>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17966&group=comp.lang.forth#17966

 copy link   Newsgroups: comp.lang.forth
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.lang.forth
Subject: Re: Sieve of Atkin
Date: Sun, 22 May 2022 19:28:41 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 43
Message-ID: <2022May22.212841@mips.complang.tuwien.ac.at>
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com> <66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com> <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>
Injection-Info: reader02.eternal-september.org; posting-host="8241a6e5816418ac47af082a8fb0d782";
logging-data="32277"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19Z1U1pQ2FmiJ1N+3fOoXNA"
Cancel-Lock: sha1:yRAtKMnlVI8EO2skUk49f7ZM3kA=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Sun, 22 May 2022 19:28 UTC

Marcel Hendrix <mhx@iae.nl> writes:
>I adapted both Atkin and the standard Sieve so that I could run them with
>array sizes between 1k and 10GByte, with the following results:

I have now tried to run it with 100GB on a machine with 128GB RAM that
is not running anything significant. However, the out-of-memory
killer reaped it after a while, despite "free" showing 125GB free; ok,
100GB for the sieve and 100GB for MODS does not fit. Does MODS buy
anything?

I prepared a version without MODS
<http://www.complang.tuwien.ac.at/forth/programs/sieveofatkin-nomods.fs>,
and it is actually faster:

On the 5800X with n=1e8, using vfx64:

MODS no MODS
8,896,377,480 4,943,212,037 cycles
9,533,502,029 8,432,685,132 instructions
1,212,120,001 998,289,650 L1-dcache-loads
155,895,135 43,060,075 L1-dcache-load-misses

Ok, let's see about the 100G. Our 5800X currently has only 96GB, so I
used a Rocket Lake machine (Xeon W-1370P), where perf unfortunately
does not report loads or misses. I used vfx64, because the version of
iforth installed apparently does not like to allocate 10GB.

cycles instructions n primes
4,958,261,806 8,431,214,174 1e8 5761455
56,409,350,162 84,181,549,986 1e9 50847534
597,442,687,159 891,687,473,921 1e10 455052511
6,068,869,349,719 8,916,633,565,847 1e11 4118054813

The number of instructions is superlinear between n=1e9 and 1e10, but
linear for 1e8->1e9 and 1e10->1e11. Hmm. Cycles rise slightly
superlinearly, possibly because caches help less and less.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2021: https://euro.theforth.net/2021

Re: Sieve of Atkin

<2022May22.223945@mips.complang.tuwien.ac.at>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17967&group=comp.lang.forth#17967

 copy link   Newsgroups: comp.lang.forth
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.lang.forth
Subject: Re: Sieve of Atkin
Date: Sun, 22 May 2022 20:39:45 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 30
Message-ID: <2022May22.223945@mips.complang.tuwien.ac.at>
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com> <5697422a-9791-480d-a136-c56dc7a2fa28n@googlegroups.com> <t69hm8$1bib$1@gioia.aioe.org> <4efed8c0-d736-42dd-9627-0913aece17edn@googlegroups.com> <nnd$4435a412$60078c44@b615e5bcc1c0105a> <f02d77ba-28ee-4af8-9d7d-a17246b880b7n@googlegroups.com> <2022May22.190555@mips.complang.tuwien.ac.at> <5cd3127f-8834-41b3-ba05-d56351dd5ab4n@googlegroups.com>
Injection-Info: reader02.eternal-september.org; posting-host="8241a6e5816418ac47af082a8fb0d782";
logging-data="32277"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18lzfpJBuFjz2QjZVDCOxul"
Cancel-Lock: sha1:8WNM/Ik/N5gtwhh7Wns4nxWiZYE=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Sun, 22 May 2022 20:39 UTC

Marcel Hendrix <mhx@iae.nl> writes:
>On Sunday, May 22, 2022 at 7:43:01 PM UTC+2, Anton Ertl wrote:
>[..]
>> So 91 instructions, 111 cycles and 1.34 main memory accesses per
>> number under consideration; yes, it could be all these cache misses
>> (actually, with this many cache misses, it could be quite a bit worse;
>> there seems to be some memory-level parallelism going on). Have you
>> considered doing it piecewise, in cache-sized pieces? That made
>> Erathostenes quite a bit faster.
>
>That would be real work,

Yes, it's more work for Erathostenes, don't know how amenable Atkin is
for that.

>On my AMD 5800X the interesting gap is between 10,000,000
>and 100,000,000, but thanks anyway.

For time results you will see cache effects, and complexity theory
usually does not model that. The instruction counts are not affected
by cache misses, and I would have expected the theoretically predicted
linear behaviour there, but as reported in another posting, I saw an
anomaly.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2021: https://euro.theforth.net/2021

Re: Sieve of Atkin

<2022May23.083624@mips.complang.tuwien.ac.at>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=17971&group=comp.lang.forth#17971

 copy link   Newsgroups: comp.lang.forth
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.lang.forth
Subject: Re: Sieve of Atkin
Date: Mon, 23 May 2022 06:36:24 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 48
Message-ID: <2022May23.083624@mips.complang.tuwien.ac.at>
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com> <5697422a-9791-480d-a136-c56dc7a2fa28n@googlegroups.com> <t69hm8$1bib$1@gioia.aioe.org> <4efed8c0-d736-42dd-9627-0913aece17edn@googlegroups.com> <nnd$4435a412$60078c44@b615e5bcc1c0105a> <f02d77ba-28ee-4af8-9d7d-a17246b880b7n@googlegroups.com>
Injection-Info: reader02.eternal-september.org; posting-host="91a43f25bdbd950c7ec1ec8001f40ef0";
logging-data="16512"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18r2H02wp/LKUuyow214l8t"
Cancel-Lock: sha1:7W/yfCi2xbI9ER0Nd0lkxHpwj5Q=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Mon, 23 May 2022 06:36 UTC

Marcel Hendrix <mhx@iae.nl> writes:
>On Sunday, May 22, 2022 at 10:57:09 AM UTC+2, none albert wrote:
>[..]
>> >Out of the box, Atkin is 94 / 12 ~ 8x slower than the standard Sieve algorithm.
>> >The standard algorithm needs no division, so it will work for limit >
>> >2^64, while
>> >Atkin must be extended for that.
>> This the deception for those who inspect the O(n) behaviour.
>> Maybe Atkin uses less operations for n to infinity, there is a
>> constant C in front, that can count instructions needed for
>> a single operation.
>> That may mean -- as you have demonstrated -- that over a practical
>> range the O(n) doesn't tell the whole story.
>
>It was a bit of a surprise to me that it was so slow, given that the reference
>to this method came from a prime thread on the GMP mailing list.
>
>It is not easy to see which instructions are slow, given that the operation
>count is indeed minimal.

I looked up <https://en.wikipedia.org/wiki/Sieve_of_Atkin> and it
discusses performance relative to Erathostenes quite a bit. I won't
reproduce that here, but I note that Erathostenes is O(N log log N)
compared to O(N) for Atkin. log log N grows very slowly:

1e3 fln fln f. 1.93264473391607 ok
1e6 fln fln f. 2.62579191447601 ok
1e9 fln fln f. 3.03125702258418 ok
1e12 fln fln f. 3.31893909503596 ok
1e15 fln fln f. 3.54208264635017 ok

That can be easily compensated for practically relevant N by a better
constant factor for Erathostenes, and the page discusses various
reasons for such a better constant factors for various implementation
variations.

As for "a prime thread on the GMP mailing list", even
usually-competent people are not immune to fallacies, and giving more
weight to mathematically proven results than they actually deserve,
and interpreting things into mathematical results that they actually
don't state are common fallacies.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2021: https://euro.theforth.net/2021

Pages:12
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor