Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

The only thing cheaper than hardware is talk.


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
Re: Sieve of Atkin

<7e8f9167-56fa-439d-ad4c-459f4e59f92an@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a37:66d0:0:b0:6a3:6e94:7794 with SMTP id a199-20020a3766d0000000b006a36e947794mr4922399qkc.526.1653293482566;
Mon, 23 May 2022 01:11:22 -0700 (PDT)
X-Received: by 2002:a05:6214:1d0a:b0:462:2155:95ef with SMTP id
e10-20020a0562141d0a00b00462215595efmr6868421qvd.83.1653293482443; Mon, 23
May 2022 01:11:22 -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: Mon, 23 May 2022 01:11:22 -0700 (PDT)
In-Reply-To: <2022May23.083624@mips.complang.tuwien.ac.at>
Injection-Info: google-groups.googlegroups.com; posting-host=176.74.235.101; posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 176.74.235.101
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> <2022May23.083624@mips.complang.tuwien.ac.at>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <7e8f9167-56fa-439d-ad4c-459f4e59f92an@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Mon, 23 May 2022 08:11:22 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Marcel Hendrix - Mon, 23 May 2022 08:11 UTC

On Monday, May 23, 2022 at 9:02:11 AM UTC+2, Anton Ertl wrote:
> 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

I learned a lot more from your level-headed experiment than from the
Wikipedia page...

Next, and probably last, step will be to limit memory use.
The MOD hack should obviously go (as you've shown) and I can
make sieve a bit array. That will indicate if is advantageous to compress
more aggressively.

-marcel

Re: Sieve of Atkin

<9ab765c1-7ad1-4ae0-87f4-2e4497bfaf25n@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:6214:14aa:b0:461:c3eb:c3c9 with SMTP id bo10-20020a05621414aa00b00461c3ebc3c9mr16271862qvb.88.1653298333457;
Mon, 23 May 2022 02:32:13 -0700 (PDT)
X-Received: by 2002:a37:5805:0:b0:69f:c640:f5e8 with SMTP id
m5-20020a375805000000b0069fc640f5e8mr13047824qkb.586.1653298333275; Mon, 23
May 2022 02:32:13 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.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: Mon, 23 May 2022 02:32:13 -0700 (PDT)
In-Reply-To: <a26cf280-be0f-452c-9c80-2a35c230e248n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:999:41:bdf0:c9b4:8242:aa38:2431;
posting-account=kiOBZQoAAADFsAs31ZHaefxTuQxv84Wm
NNTP-Posting-Host: 2001:999:41:bdf0:c9b4:8242:aa38:2431
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> <a26cf280-be0f-452c-9c80-2a35c230e248n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <9ab765c1-7ad1-4ae0-87f4-2e4497bfaf25n@googlegroups.com>
Subject: Re: Sieve of Atkin
From: jali.hei...@gmail.com (Jali Heinonen)
Injection-Date: Mon, 23 May 2022 09:32:13 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 3331
 by: Jali Heinonen - Mon, 23 May 2022 09:32 UTC

sunnuntai 22. toukokuuta 2022 klo 23.24.19 UTC+3 Marcel Hendrix kirjoitti:
> 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

Thanks, does your SieveOfAtkin use one huge buffer for primes? Version I posted uses currently just 1000 element array and needs a shit loads of iterations to find and output millions of primes. It also needs to zero out the primes array on every iteration. I should probably increase the buffer size to eliminate the overhead. Up side is that it uses currently very little memory.

Re: Sieve of Atkin

<nnd$3dc353fa$21dce105@da1b4f9c9c5a7174>

 copy mid

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

 copy link   Newsgroups: comp.lang.forth
Newsgroups: comp.lang.forth
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com> <66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com> <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@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$3dc353fa$21dce105@da1b4f9c9c5a7174>
Organization: KPN B.V.
Date: Mon, 23 May 2022 12:08:46 +0200
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!news-out.netnews.com!news.alt.net!fdc2.netnews.com!peer02.ams1!peer.ams1.xlned.com!news.xlned.com!peer03.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!feed.abavia.com!abe004.abavia.com!abp002.abavia.com!news.kpn.nl!not-for-mail
Lines: 26
Injection-Date: Mon, 23 May 2022 12:08:46 +0200
Injection-Info: news.kpn.nl; mail-complaints-to="abuse@kpn.com"
X-Received-Bytes: 1647
 by: none - Mon, 23 May 2022 10:08 UTC

In article <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>,
Marcel Hendrix <mhx@iae.nl> wrote:
<SNIP>
>Here is the final SieveOfAtkin. I fixed a bug that had to do with Python's
>logic operators apparently taking shortcuts without being told.

If you mean this:
https://docs.python.org/3/library/stdtypes.html#boolean-operations-and-or-not
Short circuit operation in Python is a feature, not a bug.

This is actually widespread e.g. this is c-idiom:
if ( pc || *pc ) { ... }
Short circuit evaluation prevents accessing address NULL if pc
has not been filled in.

<SNIP>

>-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

<nnd$73da03b1$222e286a@6e5070a1f8d96c61>

 copy mid

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

 copy link   Newsgroups: comp.lang.forth
Newsgroups: comp.lang.forth
Subject: Re: Sieve of Atkin
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com> <66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com> <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com> <2022May22.212841@mips.complang.tuwien.ac.at>
X-Newsreader: trn 4.0-test77 (Sep 1, 2010)
From: alb...@cherry (none)
Originator: albert@cherry.(none) (albert)
Message-ID: <nnd$73da03b1$222e286a@6e5070a1f8d96c61>
Organization: KPN B.V.
Date: Mon, 23 May 2022 12:23:59 +0200
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!news.uzoreto.com!news-out.netnews.com!news.alt.net!fdc2.netnews.com!feeder1.feed.usenet.farm!feed.usenet.farm!peer03.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!abe006.abavia.com!abp002.abavia.com!news.kpn.nl!not-for-mail
Lines: 65
Injection-Date: Mon, 23 May 2022 12:23:59 +0200
Injection-Info: news.kpn.nl; mail-complaints-to="abuse@kpn.com"
X-Received-Bytes: 3410
 by: none - Mon, 23 May 2022 10:23 UTC

In article <2022May22.212841@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>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.

I've seen code in this thread that made the sieve of Atkin a
test of the speed of printing code.
Long ago the original byte benchmark turned into measuring the
speed of `` 1899 . '' instead of the speed of sieving.

The difference between quicksort N.logN and bubble sort N^2
should wave a red flag. That is a big difference.

However logN missing or adding here or there -- O(n) versus O(N.logn) --
doesn't mask if the algorithm needs a MOD versus pure addition,
or the effects or accessing main memory.

The wikipedia Atking page needs a caveat of this sort,
who are going to add it?

>
>- anton

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

<20220523115459.0dc06fb3@t530>

 copy mid

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

 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: Mon, 23 May 2022 11:54:59 +0100
Organization: A noiseless patient Spider
Lines: 33
Message-ID: <20220523115459.0dc06fb3@t530>
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<20220520164842.3d49149a@t530>
<0adb4fe8-b948-4216-98b0-c6d91c474527n@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="ea579e755bee46ea4d66bee0449c3717";
logging-data="8822"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/w4m5UiqrSWv7V+DbYtDCDoqpwYeQU/Zo="
Cancel-Lock: sha1:zZECqV5f6h72HWLKCrUc7OXo1js=
In-Reply-To: <0adb4fe8-b948-4216-98b0-c6d91c474527n@googlegroups.com>
X-Newsreader: Claws Mail 3.17.3 (GTK+ 2.24.32; x86_64-pc-linux-gnu)
 by: Jan Coombs - Mon, 23 May 2022 10:54 UTC

On Sun, 22 May 2022 13:07:39 -0700 (PDT)
Jali Heinonen <jali.heinonen@gmail.com> wrote:

> 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?

jan@mypc:$ python SieveOfAtkin.py 229
[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]

Email me for source, it was beyond my ability/patience to change it.

Jan Coombs
--

Re: Sieve of Atkin

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

 copy mid

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

 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 11:44:39 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 84
Message-ID: <2022May23.134439@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> <2022May22.212841@mips.complang.tuwien.ac.at> <nnd$73da03b1$222e286a@6e5070a1f8d96c61>
Injection-Info: reader02.eternal-september.org; posting-host="91a43f25bdbd950c7ec1ec8001f40ef0";
logging-data="13075"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/DUKmlvtk1Zsw2tdYEG20e"
Cancel-Lock: sha1:Ke/hO2e/80fn9gCJvlzU6ReY9/4=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Mon, 23 May 2022 11:44 UTC

albert@cherry.(none) (albert) writes:
>In article <2022May22.212841@mips.complang.tuwien.ac.at>,
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>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.
>
>I've seen code in this thread that made the sieve of Atkin a
>test of the speed of printing code.

So?

>Long ago the original byte benchmark turned into measuring the
>speed of `` 1899 . '' instead of the speed of sieving.

Let's test it on a Ryzen 5800X:

perf stat -e cycles gforth-fast ../gforth/siev.fs -e ": foo 1000 0 do 1899 . loop ; ..."

cycles ...
31203365 bye
300973318 main bye
35385551 foo bye

MAIN runs the sieve (made slightly faster than the Byte version) 1000
times, without printing the number of primes.

FOO prints 1899 1000 times.

As you can see, the printing is a lot faster.

>However logN missing or adding here or there

ld N is 20 for N=1e6, so it's a lot less than N, but not negligible.

>-- O(n) versus O(N.logn) --

It's about O(N) vs. O(N log log N), though.

>The wikipedia Atking page needs a caveat of this sort,
>who are going to add it?

It states repeatedly that Erathostenes is faster and discusses the
reasons. What makes you think that it needs an additional caveat?

- 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

<dc867cfa-c876-4ca5-978e-224337a6f63cn@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:6214:d4d:b0:462:4986:f9bd with SMTP id 13-20020a0562140d4d00b004624986f9bdmr2329871qvr.70.1653329118995;
Mon, 23 May 2022 11:05:18 -0700 (PDT)
X-Received: by 2002:a05:622a:1793:b0:2f9:1765:7064 with SMTP id
s19-20020a05622a179300b002f917657064mr13997410qtk.266.1653329118854; Mon, 23
May 2022 11:05:18 -0700 (PDT)
Path: i2pn2.org!i2pn.org!news.swapon.de!news.uzoreto.com!news-out.netnews.com!news.alt.net!fdc2.netnews.com!peer02.ams1!peer.ams1.xlned.com!news.xlned.com!peer02.ams4!peer.am4.highwinds-media.com!peer03.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: Mon, 23 May 2022 11:05:18 -0700 (PDT)
In-Reply-To: <7e8f9167-56fa-439d-ad4c-459f4e59f92an@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:d923:35fa:5b2d:d8ac;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:d923:35fa:5b2d:d8ac
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> <2022May23.083624@mips.complang.tuwien.ac.at>
<7e8f9167-56fa-439d-ad4c-459f4e59f92an@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <dc867cfa-c876-4ca5-978e-224337a6f63cn@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Mon, 23 May 2022 18:05:18 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 3258
 by: Marcel Hendrix - Mon, 23 May 2022 18:05 UTC

On Monday, May 23, 2022 at 10:11:23 AM UTC+2, Marcel Hendrix wrote:
> On Monday, May 23, 2022 at 9:02:11 AM UTC+2, Anton Ertl wrote:
[..]
> Next, and probably last, step will be to limit memory use.
> The MOD hack should obviously go (as you've shown) and I can
> make sieve a bit array. That will indicate if is advantageous to compress
> more aggressively.

Using a bit array uncovered a likely reason for the discontinuity in the
speed results.

The bit results start off slower than the ones using bytes. The Intel bit
manipulation instructions are not very fast -- extracting the bits
'by hand' might be faster -- but iForth has the words, so why not.

Contrary to the byte results, from n = 1e3 to 1e8 the runtime increases
linearly with n, and for n =1e8 the result with bits is 1237/738 = 1.7 times
faster than with bytes. Definitely a worthwhile improvement.

Note that the AMD 5800X has 512KB L2 cache per core and 32MEG
L3 in total. It could be that for n > 0.1Gbytes or 12.5Mbits it runs out
of L3 cache and loses 100 - 300% performance that way. The faster
but much smaller L1 and L2 caches won't help here.

n runtime (ms) primes runtime (ms) (bits iso bytes)
1,000 0 168 0
10,000 0 1,229 0
100,000 0 9,592 0
1,000,000 4 78,498 6
10,000,000 44 664,579 72
100,000,000 1237 5,761,455 738
1,000,000,000 16044 50,847,534 16902
10,000,000,000 206919 455,052,511 215561

-marcel

Re: Sieve of Atkin

<efe4b7c7-4856-4589-a6d9-4f15193d1fbfn@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:622a:10c:b0:2f9:31a8:5014 with SMTP id u12-20020a05622a010c00b002f931a85014mr7082292qtw.597.1653335316064;
Mon, 23 May 2022 12:48:36 -0700 (PDT)
X-Received: by 2002:a05:620a:258f:b0:680:f657:d3d0 with SMTP id
x15-20020a05620a258f00b00680f657d3d0mr15403271qko.707.1653335314938; Mon, 23
May 2022 12:48:34 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.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: Mon, 23 May 2022 12:48:34 -0700 (PDT)
In-Reply-To: <20220523115459.0dc06fb3@t530>
Injection-Info: google-groups.googlegroups.com; posting-host=87.95.89.60; posting-account=kiOBZQoAAADFsAs31ZHaefxTuQxv84Wm
NNTP-Posting-Host: 87.95.89.60
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<20220520164842.3d49149a@t530> <0adb4fe8-b948-4216-98b0-c6d91c474527n@googlegroups.com>
<20220523115459.0dc06fb3@t530>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <efe4b7c7-4856-4589-a6d9-4f15193d1fbfn@googlegroups.com>
Subject: Re: Sieve of Atkin
From: jali.hei...@gmail.com (Jali Heinonen)
Injection-Date: Mon, 23 May 2022 19:48:36 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 3393
 by: Jali Heinonen - Mon, 23 May 2022 19:48 UTC

maanantai 23. toukokuuta 2022 klo 13.55.03 UTC+3 Jan Coombs kirjoitti:
> On Sun, 22 May 2022 13:07:39 -0700 (PDT)
> Jali Heinonen <jali.h...@gmail.com> wrote:
>
> > 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?
> jan@mypc:$ python SieveOfAtkin.py 229
> [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]
>
> Email me for source, it was beyond my ability/patience to change it.
>
> Jan Coombs
> --

Thanks, I found a working Python implementation. Seems to be faster than my wheel sieve conversion for the 8th but luckily I can easily beat it's performance by parallelizing my code. It's easy as wheel sieve allows finding primes between specific number range, so I can for an example find primes between 10000000000 and 10000011050. It takes just a few milliseconds to find that first prime is 10000000019, last prime is 10000011037 and there are 455 primes. I think Sieve of Atkin can't do that? This makes parallelizing easy as each thread can be given different number range to handle and no locking is necessary.

Re: Sieve of Atkin

<6d538bac-adbb-44b3-bc99-ab2271d65f5dn@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a05:620a:27cd:b0:6a3:756f:8267 with SMTP id i13-20020a05620a27cd00b006a3756f8267mr11208449qkp.374.1653480949438;
Wed, 25 May 2022 05:15:49 -0700 (PDT)
X-Received: by 2002:a05:622a:cc:b0:2f9:e34:ead7 with SMTP id
p12-20020a05622a00cc00b002f90e34ead7mr24304664qtw.581.1653480949206; Wed, 25
May 2022 05:15:49 -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: Wed, 25 May 2022 05:15:48 -0700 (PDT)
In-Reply-To: <2022May22.212841@mips.complang.tuwien.ac.at>
Injection-Info: google-groups.googlegroups.com; posting-host=77.174.47.232; posting-account=Ebqe4AoAAABfjCRL4ZqOHWv4jv5ZU4Cs
NNTP-Posting-Host: 77.174.47.232
References: <5bbae8b0-0cc3-4793-a77d-84dca2a00489n@googlegroups.com>
<66906be0-3ef6-48be-b657-da8bef2edf5an@googlegroups.com> <74043ddb-6fd4-4389-8af1-778e71f1dd1bn@googlegroups.com>
<2022May22.212841@mips.complang.tuwien.ac.at>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <6d538bac-adbb-44b3-bc99-ab2271d65f5dn@googlegroups.com>
Subject: Re: Sieve of Atkin
From: the.beez...@gmail.com (Hans Bezemer)
Injection-Date: Wed, 25 May 2022 12:15:49 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 1589
 by: Hans Bezemer - Wed, 25 May 2022 12:15 UTC

On Sunday, May 22, 2022 at 10:38:37 PM UTC+2, Anton Ertl wrote:
> I prepared a version without MODS
> <http://www.complang.tuwien.ac.at/forth/programs/sieveofatkin-nomods.fs>,
> and it is actually faster:
BTW, clean code - getting it to run under 4tH was a breeze! Thanks for publishing this!

Hans Bezemer

Re: Sieve of Atkin

<4724c8fb-3cb4-468a-947c-21cb56de0b9bn@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.lang.forth
X-Received: by 2002:a37:9e8b:0:b0:6a6:a4ba:5444 with SMTP id h133-20020a379e8b000000b006a6a4ba5444mr6893079qke.527.1654431908014;
Sun, 05 Jun 2022 05:25:08 -0700 (PDT)
X-Received: by 2002:a05:622a:1805:b0:2fc:ca5e:7b8c with SMTP id
t5-20020a05622a180500b002fcca5e7b8cmr14884845qtc.429.1654431907897; Sun, 05
Jun 2022 05:25:07 -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, 5 Jun 2022 05:25:07 -0700 (PDT)
In-Reply-To: <dc867cfa-c876-4ca5-978e-224337a6f63cn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f14:600:910b:d35d:8dec:baf6;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f14:600:910b:d35d:8dec:baf6
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> <2022May23.083624@mips.complang.tuwien.ac.at>
<7e8f9167-56fa-439d-ad4c-459f4e59f92an@googlegroups.com> <dc867cfa-c876-4ca5-978e-224337a6f63cn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <4724c8fb-3cb4-468a-947c-21cb56de0b9bn@googlegroups.com>
Subject: Re: Sieve of Atkin
From: mhx...@iae.nl (Marcel Hendrix)
Injection-Date: Sun, 05 Jun 2022 12:25:08 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Marcel Hendrix - Sun, 5 Jun 2022 12:25 UTC

On Monday, May 23, 2022 at 8:05:20 PM UTC+2, Marcel Hendrix wrote:
[..]
> n runtime (ms) primes runtime (ms) (bits iso bytes)
> 1,000 0 168 0
> 10,000 0 1,229 0
> 100,000 0 9,592 0
> 1,000,000 4 78,498 6
> 10,000,000 44 664,579 72
> 100,000,000 1237 5,761,455 738
> 1,000,000,000 16044 50,847,534 16902
> 10,000,000,000 206919 455,052,511 215561

Slight update: I had a look in the BIOS and saw that the memory timing
was not according to the XMP profile. Adjusting that increased the
run-speed of the Sieve of Atkin by 121%.

n runtime (ms) primes runtime (ms) (bits) (bits+mem timing)
1,000 0 168 0 0
10,000 0 1,229 0 0
100,000 0 9,592 0 0
1,000,000 4 78,498 6 6
10,000,000 44 664,579 72 65
100,000,000 1237 5,761,455 738 729
1,000,000,000 16044 50,847,534 16902 13920 ( -121%)
10,000,000,000 206919 455,052,511 215561 177643 ( -121%)

BTW, I learned that the segmented sieve of Atkin exists but I have no idea
if it is faster or not. The Sieve guys love to throw numbers around and bicker about them.

-marcel

Pages:12
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor