Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #118058 > unrolled thread
| Started by | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| First post | 2023-12-10 10:46 +0100 |
| Last post | 2024-02-14 15:57 +0100 |
| Articles | 20 on this page of 213 — 14 participants |
Back to article view | Back to comp.lang.c++
Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-10 10:46 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-10 21:48 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-11 04:15 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-11 17:12 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-11 18:19 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-13 15:16 +0000
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-13 15:25 +0000
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-14 15:06 +0000
Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2023-12-14 08:20 -0800
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-12-23 10:30 -0800
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-23 21:20 +0000
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-12-24 00:36 -0800
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-29 18:03 +0000
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-01-13 21:31 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-20 13:44 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-21 15:30 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-21 17:07 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-21 17:13 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-12-23 10:21 -0800
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-23 21:21 +0000
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-12-24 10:49 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-21 14:23 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-22 04:28 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-21 20:02 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-22 17:55 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-23 12:52 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-24 11:03 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-24 13:24 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-26 06:00 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-25 21:39 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-26 10:27 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-26 12:24 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-26 23:35 +0000
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-26 15:37 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-26 21:59 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-27 10:23 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-27 20:49 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-28 12:00 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-28 15:38 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-29 04:17 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-28 20:58 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-29 10:58 +0100
Re: Sieve of Erastosthenes optimized to the max David Brown <david.brown@hesbynett.no> - 2023-12-29 13:56 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-29 17:04 +0100
Re: Sieve of Erastosthenes optimized to the max David Brown <david.brown@hesbynett.no> - 2023-12-30 19:27 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-31 11:22 +0100
Re: Sieve of Erastosthenes optimized to the max scott@slp53.sl.home (Scott Lurndal) - 2023-12-31 18:49 +0000
Re: Sieve of Erastosthenes optimized to the max David Brown <david.brown@hesbynett.no> - 2024-01-01 12:46 +0100
Re: Sieve of Erastosthenes optimized to the max scott@slp53.sl.home (Scott Lurndal) - 2023-12-29 16:01 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-29 17:06 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 13:45 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 14:09 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 14:12 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-30 05:42 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 20:45 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-30 04:56 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-30 06:09 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-30 05:51 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-30 10:15 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-30 20:35 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-31 06:54 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-31 07:01 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-31 11:20 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-31 17:30 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 06:21 +0100
Re: Sieve of Erastosthenes optimized to the max scott@slp53.sl.home (Scott Lurndal) - 2023-12-31 18:44 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 06:22 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-01 08:28 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 14:11 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-01 15:36 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-30 04:51 +0000
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-30 12:00 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-29 17:29 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-30 05:45 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-30 11:58 -0800
Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2023-12-30 14:58 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-31 11:49 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-31 06:51 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-31 11:36 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 07:28 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-31 22:53 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 14:11 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-01 15:34 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-02 11:55 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-02 10:38 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-03 06:48 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-03 13:32 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-04 04:37 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-05 19:21 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-06 08:18 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-06 08:31 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-06 10:30 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-06 13:15 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-06 13:19 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-07 10:14 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-07 10:10 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-07 12:46 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-08 06:48 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-08 12:18 -0800
Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2024-01-08 17:14 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-09 07:19 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-09 23:33 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-09 02:02 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-09 15:12 +0100
OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Vir Campestris <vir.campestris@invalid.invalid> - 2024-01-29 21:31 +0000
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-16 08:06 -0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-16 18:30 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-23 05:51 -0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-24 10:45 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-25 00:48 -0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-25 15:51 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-11 10:10 -0700
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-12 10:15 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-14 12:44 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-14 07:25 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-14 17:20 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-14 17:35 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-14 17:41 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-14 19:20 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-15 16:30 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-15 11:21 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-15 19:07 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-15 12:56 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-14 19:20 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-20 08:35 -0700
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-20 18:34 +0200
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-20 18:35 +0200
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-24 12:28 -0700
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-25 06:19 +0200
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-25 14:14 -0700
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-31 11:39 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 13:52 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-27 06:06 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-22 19:34 -0700
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-23 17:54 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-23 14:04 -0700
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-24 07:30 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-24 12:52 -0700
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-24 21:00 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-24 13:05 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-05-16 17:28 +0100
Re: Sieve of Erastosthenes optimized to the max Ben Bacarisse <ben@bsb.me.uk> - 2024-05-16 21:40 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-05-21 19:06 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-05-30 12:32 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-05-30 14:17 +0200
Re: Sieve of Erastosthenes optimized to the max Paavo Helde <eesnimi@osa.pri.ee> - 2024-05-30 19:55 +0300
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-05-31 10:17 +0200
Re: Sieve of Erastosthenes optimized to the max Paavo Helde <eesnimi@osa.pri.ee> - 2024-05-31 20:52 +0300
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-05-30 22:17 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-06-01 21:07 +0100
Re: Sieve of Erastosthenes optimized to the max Richard Damon <richard@damon-family.org> - 2024-06-01 20:43 -0400
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-06-02 03:23 -0700
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-06-02 19:50 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-06-18 20:56 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-06-18 17:34 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-06-30 21:47 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-07-01 23:20 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-07-02 21:24 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-07-03 11:25 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-07-15 06:15 -0700
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-07-20 07:41 -0700
OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-07-25 12:46 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-10 07:07 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-12 15:32 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-16 07:48 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-15 17:52 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-16 08:40 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-16 19:35 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-16 19:55 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-19 21:23 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 17:21 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 17:24 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 17:43 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-20 17:55 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 18:59 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 12:08 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-27 06:09 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-09-01 21:23 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-01 20:40 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-09-02 07:08 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-09-03 17:45 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-28 03:46 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-09-28 13:49 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-10-02 11:44 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-10-02 13:10 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-10-07 08:41 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-10-20 12:44 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-11-04 03:56 -0800
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-19 21:34 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2024-08-19 21:08 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-20 21:14 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 09:35 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 08:31 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 19:20 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 19:36 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 19:39 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 20:13 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max scott@slp53.sl.home (Scott Lurndal) - 2024-08-20 20:50 +0000
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-22 17:30 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-22 18:38 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-22 21:47 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-22 21:56 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2024-08-22 17:00 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 10:59 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Andrey Tarasevich <andreytarasevich@hotmail.com> - 2024-09-28 15:21 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 12:47 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-18 19:52 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-10 17:24 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-11 00:00 -0700
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-07-23 07:34 -0700
Re: Sieve of Erastosthenes optimized to the max wij <wyniijj5@gmail.com> - 2024-02-14 00:15 +0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-13 19:08 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-14 15:57 +0100
Page 10 of 11 — ← Prev page 1 … 8 9 [10] 11 Next page →
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2024-09-03 17:45 +0100 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <vb7efc$3dfh8$1@dont-email.me> |
| In reply to | #119987 |
On 02/09/2024 04:40, Tim Rentsch wrote:
> Vir Campestris <vir.campestris@invalid.invalid> writes:
>
>> On 27/08/2024 05:09, Bonita Montero wrote:
>>
>>> Am 26.08.2024 um 21:08 schrieb Tim Rentsch:
>>>
>>>> One motivation for choosing a mod30 representation is being able to
>>>> compute more primes -- almost twice as many. Any machine with 64GB
>>>> of memory should be able to compute primes up to 1.5 trillion.
>>>
>>> You don't need to hold all primes in memory. Just calculate the primes
>>> up to the square root and then you can calculate every segment up to
>>> the maximum from that.
>
> This is a brainless statement (and incidentally illustrates why I
> was motivated not to read postings from BM). In fact no primes need
> be pre-calculated to determine whether any given number is prime.
> The point of using a sieve is the sieve method is much faster than
> not using one. For example, suppose we want to determine all primes
> less than a trillion. Taking the approach of pre-computing only
> those primes less than a million (the square root) and then testing
> numbers individually takes more than 100 times as many operations as
> using a sieve. Furthermore the operations used are more expensive
> for the non-sieve approach - simply setting a bit in the case of a
> sieve, versus computing a remainder in the non-sieve case.
>
Umm. I assumed you'd take the primes you had, then sieve them into
several blocks to exceed your memory size.
>> So you compute all the primes up to the square root of a larger number.
>>
>> I was cleaning up my odds-only code with a view to posting it, when I
>> had an idea.
>>
>> Take 101 (because I can write things more easily).
>>
>> I want to mark
>>
>> 10201,10302,10403,10504,10605,10706...
>>
>> With odds only that becomes
>> 10201,10403,10605,10807,11009,11211...
>
> Right. Marking of multiples needs to start only at p*p, not
> at p+2.
>
>> and as the loop increment is a constant it is nice and fast. With
>> mod30 it isn't a constant, and it hurts to work out the increment.
>>
>> Except...
>>
>> If I mark 10201,13231,16261,19291,22321
>> with an increment of 30*p,
>>
>> then go back to 10201, add 2p, then increment that by 30
>> 10201 13231 16261
>> and do that for the other 6 of the 8, my inner loop has a constant
>> increment, and my code is compatible with the mod30 store.
>
> Yes, reordering the loops this way might very well make things
> work better. It also has the property, I believe, that the
> bit to set is the same in each of the eight outer loops, and
> so can be computed only once for each of the eight outer loops.
> Very good!
>
It ought to be fast. Perhaps I'll have something one day. But not before
I go on holiday, so it will be a few weeks.
>> That might be quicker. I also have some thoughts over storing the
>> prime as two parts. It's 30m+r, where m is modulus and r remainder. r
>> maps one-for-one into the byte mask, and m is the index.
>
> This is what I've been saying all along!
>
Ah, sorry.
>> I'm going to waste lots more time on this I can see!
>
> I'm interested to see what you come up with.
The code that follows is *NOT* doing anything with mod30, it's just a
cleaned up, not using include files, version of my odds only program.
The code that writes the primes out is not optimised. Not even slightly.
And it's way slower than Bonita's version.
But the code that does the calculation is a lot faster:
$ time ./Bonita 100000000000 && time ./usenet 100000000000
real 1m46.452s
user 2m53.666s
sys 0m32.260s
781250001,40.4744
594,0.0709076
598,2.60332
620,2.60697
628,20.4567
620,20.4572
628,40.4744
4294967295,40.4744
real 0m40.723s
user 0m39.104s
sys 0m1.604s
Andy
--
/*
Programme to calculate primes using the Sieve or Eratosthenes
Copyright (C) 2024 the person known as Vir Campestris
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
#include <algorithm>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <list>
#include <memory>
#include <new>
#include <thread>
#include <vector>
// If these trigger you have a really odd architecture.
static_assert(sizeof(uint8_t) == 1);
static_assert(CHAR_BIT == 8);
// The type of a prime number.
// size_t isn't big enough on a 32-bit machine with 2GB memory allocated
and 16 primes per byte.
typedef uint64_t PRIME;
// This is the type of the word I operate in. The code will run OK with
uin8_t or uint32_t,
// but *on my computer* it's slower.
typedef uint64_t StoreType;
// tuneable constants
constexpr size_t tinyCount = 5;
constexpr size_t smallCount = 10;
constexpr size_t bigCache = 16384;
// this is a convenience class for timing.
class Stopwatch {
typedef std::chrono::steady_clock CLOCK;
typedef std::pair<unsigned, std::chrono::time_point<CLOCK> > LAP;
typedef std::vector<LAP> LAPS;
LAPS mLaps;
public:
typedef std::vector<std::pair<unsigned, double>> LAPTIMES;
Stopwatch() {}
// record the start of an interval
void start()
{
mLaps.clear();
mLaps.emplace_back(std::make_pair(0, CLOCK::now()));
}
void lap(unsigned label)
{
mLaps.emplace_back(std::make_pair(label, CLOCK::now()));
}
// record the end of an interval
void stop()
{
mLaps.emplace_back(std::make_pair(-1, CLOCK::now()));
}
// report the difference between the last start and stop
double delta() const
{
assert(mLaps.size() >= 2);
assert(mLaps.front().first == 0);
assert(mLaps.back().first == -1);
return
std::chrono::duration_cast<std::chrono::nanoseconds>(mLaps.back().second
- mLaps.front().second).count() / (double)1e9;
}
LAPTIMES const laps() const
{
LAPTIMES ret;
assert(mLaps.size() >= 2);
ret.reserve(mLaps.size() - 1);
auto lap = mLaps.begin();
auto start = lap->second;
for(++lap; lap != mLaps.end(); ++lap)
{
ret.emplace_back(
std::make_pair(
lap->first,
std::chrono::duration_cast<std::chrono::nanoseconds>(lap->second -
start).count() / (double)1e9));
}
return ret;
}
};
// Internal class used to store the mask data for one or more
// primes rather than all primes. This has an initial block,
// followed by a block which contains data which is repeated
// for all higher values.
// Example: StoreType== uint8_t, prime == 3, the mask should be
// 90 meaning 1,3,5,7,11,13 are prime but not 9, 15
// 24,49,92 covers odds 17-63
// 24,49,92 covers 65-111, with an identical mask
// As the mask is identical we only need to store the
// non-repeat, plus one copy of the repeated block and data to
// show where it starts and ends. Note that for big primes the
// initial block may be more than one StoreType.
// As there are no common factors between any prime and the
// number of bits in StoreType the repeat is the size of the
// prime.
// Note also that a masker for two primes will have an
// initial block which is as big as the larger of the sources,
// and a repeat which is the product of the sources.
class Masker final
{
// The length of the initial block.
size_t initSize;
// The size of the repeated part. The entire store size is the
sum of these two.
size_t repSize;
// Buffer management local class. I started using std::vector
for the store,
// but I found it was slow for large sizes as it insists on
calling the constructor
// for each item in turn. And there may be billions of them.
class Buffer final
{
StoreType* mpBuffer; // base of the data referred to
size_t mSize; // size of the buffer in
StoreType-s.
public:
// Normal constructor
Buffer(size_t size = 0) : mpBuffer(nullptr), mSize(size)
{
if (size > 0)
{
mpBuffer =
static_cast<StoreType*>(std::malloc(size * sizeof(StoreType)));
if (!mpBuffer)
throw std::bad_alloc();
}
}
Buffer(Buffer&) = delete;
// Move constructor
Buffer(Buffer&& source)
: mpBuffer(source.mpBuffer), mSize(source.mSize)
{
source.mSize = 0;
source.mpBuffer = nullptr;
};
Buffer& operator=(Buffer&) = delete;
// Move assignment
Buffer& operator=(Buffer&& source)
{
if (mpBuffer)
std::free(mpBuffer);
mpBuffer = source.mpBuffer;
mSize = source.mSize;
source.mSize = 0;
source.mpBuffer = nullptr;
return *this;
}
void resize(size_t newSize)
{
mpBuffer =
static_cast<StoreType*>(std::realloc(mpBuffer, newSize *
sizeof(StoreType)));
if (!mpBuffer)
throw std::bad_alloc();
mSize = newSize;
}
// Get the data start
inline StoreType* operator*() const
{
return mpBuffer;
}
// Get the owned size
inline size_t const & size() const
{
return mSize;
}
// clean up.
~Buffer()
{
if (mpBuffer)
std::free(mpBuffer);
}
} mBuffer;
// Raw pointer to the store for speed.
StoreType * mStorePtr;
// shift from the prime value to the index in mStore
static constexpr size_t wordshift = sizeof(StoreType) == 1 ? 4
: sizeof(StoreType) == 4 ? 6 : sizeof(StoreType) == 8 ? 7 : 0;
static_assert(wordshift);
// Mask for the bits in the store that select a prime.
static constexpr size_t wordmask = (StoreType)-1 >>
(sizeof(StoreType) * CHAR_BIT + 1 - wordshift);
// convert a prime to the index of a word in the store
static inline size_t index(PRIME const & prime)
{
return prime >> wordshift;
}
// get a mask representing the bit for a prime in a word
static inline StoreType mask(PRIME const & prime)
{
return (StoreType)1 << ((prime >> 1) & wordmask);
}
public:
// This class allows us to iterate through a Masker
indefinitely, retrieving words,
// automatically wrapping back to the beginning of the repat
part when the end is met.
class MaskIterator
{
StoreType const * index, *repStart, *repEnd;
public:
MaskIterator(Masker const * origin)
: index(origin->mStorePtr)
, repStart(index + origin->initSize)
, repEnd(repStart + origin->repSize)
{}
inline StoreType const & operator*() const
{
return *index;
}
inline StoreType next() // returns value with iterator
post-increment
{
auto & retval = *index;
if (++index >= repEnd)
index = repStart;
return retval;
}
};
// Default constructor. Makes a dummy mask for overwriting.
Masker()
: initSize(0)
, repSize(1)
, mBuffer(1)
, mStorePtr(*mBuffer)
{
*mStorePtr = 0; // nothing marked unprime
}
// Move constructor (destroys source)
Masker(Masker&& source)
: initSize(source.initSize)
, repSize(source.repSize)
, mBuffer(std::move(source.mBuffer))
, mStorePtr(*mBuffer)
{
}
// Copy constructor (preserves source)
Masker(Masker& source)
: initSize(source.initSize)
, repSize(source.repSize)
, mBuffer(initSize + repSize)
, mStorePtr(*mBuffer)
{
memcpy(*mBuffer, *source.mBuffer, mBuffer.size() *
sizeof(StoreType));
}
// move assignment (destroys source)
Masker& operator=(Masker&& source)
{
initSize = source.initSize;
repSize = source.repSize;
mStorePtr = source.mStorePtr;
mBuffer = std::move(source.mBuffer);
return *this;
}
// Construct for a single prime
Masker(PRIME prime)
: initSize(this->index(prime)+1)
, repSize(prime)
, mBuffer(initSize + prime)
, mStorePtr(*mBuffer)
{
// Pre-zero the buffer, because for bigger primes we
don't write every word.
// This is fast enough not to care about excess writes.
memset(mStorePtr, 0, mBuffer.size() * sizeof(StoreType));
// The max prime we'll actually store.
// *2 because we don't store evens.
PRIME const maxPrime = (initSize + repSize) * CHAR_BIT
* sizeof(StoreType) * 2;
// Filter all the bits. Note that although we
// don't strictly need to filter from prime*3,
// but only from prime**2, doing from *3 makes
// the init block smaller.
PRIME const prime2 = prime * 2;
for (PRIME value = prime * 3; value < maxPrime; value
+= prime2)
{
mStorePtr[this->index(value)] |= this->mask(value);
}
}
// Construct from two others, making a mask that excludes all
numbers
// marked not prime in either of them. The output init block
// will be the largest from either of the inputs; the repeat
block size will be the
// product of the input repeat sizes.
// The output could get quite large - 3.7E12 for all primes up
to 37
Masker(const Masker& left, const Masker& right, size_t
storeLimit = 0)
: initSize(std::max(left.initSize, right.initSize))
, repSize (left.repSize * right.repSize)
, mBuffer()
{
if (storeLimit)
repSize = std::min(initSize + repSize,
storeLimit) - initSize;
auto storeSize = initSize + repSize;
// Actually construct the store with the desired size
mBuffer = storeSize;
mStorePtr = *mBuffer;
// get iterators to the two inputs. These automatically
wrap
// when their repsize is reached.
auto li = left.begin();
auto ri = right.begin();
for (size_t word = 0; word < storeSize; ++word)
{
mStorePtr[word] = li.next() | ri.next();
}
}
// Construct from several others, making a mask that excludes
all numbers
// marked not prime in any of them. The output init block
// will be the largest from any of the inputs; the repeat size
will be the
// product of all the input repeat sizes.
// The output could get quite large - 3.7E12 for all primes up
to 37
// the type iterator should be an iterator into a collection of
Masker-s.
template <typename iterator> Masker(const iterator& begin,
const iterator& end, size_t storeLimit = 0)
: initSize(0)
, repSize(1)
, mBuffer() // empty for now
{
// Iterate over the inputs. We will
// * Determine the maximum init size
// * Determine the product of all the repeat sizes.
// * Record the number of primes we represent.
size_t nInputs = std::distance(begin, end);
std::vector<MaskIterator> iterators;
iterators.reserve(nInputs);
for (auto i = begin; i != end; ++i)
{
initSize = std::max(initSize, i->initSize);
repSize *= i->repSize;
iterators.push_back(i->begin());
}
if (storeLimit)
repSize = std::min(initSize + repSize,
storeLimit) - initSize;
auto storeSize = initSize + repSize;
// Actually construct the store with the desired size
mBuffer = storeSize;
mStorePtr = *mBuffer;
// take the last one off (most efficient to remove)
// and use it as the initial mask value
auto last = iterators.back();
iterators.pop_back();
for (auto word = 0; word < storeSize; ++word)
{
StoreType mask = last.next();
for(auto &i: iterators)
{
mask |= i.next();
}
mStorePtr[word] = mask;
}
}
template <typename iterator> Masker& andequals(size_t
cachesize, iterator begin, iterator end)
{
static constexpr size_t wordshift = sizeof(StoreType)
== 1 ? 4 : sizeof(StoreType) == 4 ? 6 : sizeof(StoreType) == 8 ? 7 : 0;
static constexpr size_t wordmask = (StoreType)-1 >>
(sizeof(StoreType) * CHAR_BIT + 1 - wordshift);
struct value
{
PRIME step; // this is the
prime. The step should be 2P, but only half the bits are stored
PRIME halfMultiple; // this is the
current multiple, _without_ the last bit
value(PRIME prime): step(prime),
halfMultiple((prime*prime) >> 1) {}
bool operator<(PRIME halfLimit) const
{
return halfMultiple < halfLimit;
}
void next(StoreType * store)
{
static constexpr size_t wsm1 =
wordshift - 1;
auto index = halfMultiple >> wsm1;
auto mask = (StoreType)1 <<
(halfMultiple & wordmask);
*(store + index) |= mask;
halfMultiple += step;
}
};
std::vector<value> values;
values.reserve(std::distance(begin, end));
for (auto prime = begin; prime != end; ++prime)
{
auto p = *prime;
values.emplace_back(p);
}
size_t limit = 0;
do
{
limit = std::min(limit + cachesize, initSize +
repSize + 1);
PRIME halfMaxPrime = (limit * 16 *
sizeof(StoreType)) / 2 + 1;
for (auto & value: values)
{
while (value < halfMaxPrime)
value.next(mStorePtr);
}
}
while (limit < initSize + repSize);
return *this;
}
// duplicates the data up to the amount needed for a prime newSize
void resize(PRIME newSize)
{
size_t sizeWords = this->index(newSize) + 1;
assert(sizeWords > (initSize + repSize)); // not
allowed to shrink!
mBuffer.resize(sizeWords);
mStorePtr = *mBuffer;
auto copySource = mStorePtr + initSize;
do
{
auto copySize = std::min(sizeWords - repSize -
initSize, repSize);
auto dest = copySource + repSize;
memcpy(dest, copySource, copySize *
sizeof(StoreType));
repSize += copySize;
} while ((initSize + repSize) < sizeWords);
}
// returns true if this mask thinks value is prime.
bool get(PRIME value) const
{
assert(value < sizeof(StoreType) * CHAR_BIT * 2 *
mBuffer.size());
auto ret =
(value <= 3)
|| ((value & 1) &&
(mStorePtr[this->index(value)] &
this->mask(value)) == 0);
return ret;
}
// Get the beginning of the bitmap.
// Incrementing this iterator can continue indefinitely,
regardless of the bitmap size.
MaskIterator begin() const
{
return MaskIterator(this);
}
size_t repsize() const
{
return repSize;
}
size_t size() const
{
return initSize + repSize;
}
// prints a collection to stderr
void dump(size_t limit = 0) const
{
std::cerr << std::dec << repSize;
std::cerr << std::hex;
if (limit == 0) limit = initSize + repSize;
auto iter = begin();
for (auto i = 0; i < limit; ++i)
{
// cast prevents attempting to print uint8_t as
a char
std::cerr << ',' << std::setfill('0') <<
std::setw(sizeof(StoreType) * 2) << uint64_t(mStorePtr[i]);
}
std::cerr << std::endl;
std::cerr << std::dec << repSize;
for (auto p = 1; p < limit * 16 * sizeof(StoreType); ++p)
{
if (get(p))
{
std::cerr << ',' << p;
}
}
std::cerr << std::endl;
}
};
int main(int argc, char**argv)
{
// find out if the user asked for a different number of primes
PRIME PrimeCount = 1e9;
if (argc >= 2)
{
std::istringstream arg1(argv[1]);
std::string crud;
arg1 >> PrimeCount >> crud;
if (!crud.empty() || PrimeCount < 3)
{
double isitfloat;
arg1.seekg(0, arg1.beg);
crud.clear();
arg1 >> isitfloat >> crud;
if (!crud.empty() || isitfloat < 3)
{
std::cerr << "Invalid first argument
\"" << argv[1] << "\" Should be decimal number of primes required\n";
exit(42);
}
else PrimeCount = isitfloat;
}
}
std::string outName;
if (argc >= 3)
{
outName = argv[2];
}
Stopwatch s; s.start();
Masker primes;
PRIME nextPrime;
{
nextPrime = 3;
Masker tiny(nextPrime);
std::vector<Masker> smallMasks;
smallMasks.emplace_back(tiny);
// Make a mask for the really small primes, 3 5 7 11
size_t count = 1; // allows for the 3
for ( ; count < tinyCount; ++count)
{
do
{
nextPrime += 2;
} while (!tiny.get(nextPrime));
tiny = Masker(tiny, nextPrime);
}
// that masker for three will be correct up until 5
squared,
// the first non-prime whose smallest root is not 2 or 3
assert (nextPrime < 25 && "If this triggers tinyCount
is too big and the code will give wrong results");
// this limit is too small, but is easy to calculate
and big enough
auto limit = nextPrime*nextPrime;
smallMasks.clear();
for (; count < smallCount; ++count)
{
do
{
nextPrime += 2;
} while (!tiny.get(nextPrime));
smallMasks.emplace_back(nextPrime);
}
assert(nextPrime <= limit && "If this triggers
smallCount is too big and the code will give wrong results");
// Make a single masker for all the small primes. Don't
make it bigger than needed.
auto small = Masker(smallMasks.begin(),
smallMasks.end(), PrimeCount / (2 * CHAR_BIT * sizeof(StoreType)) + 1);
s.lap(__LINE__);
// This is the first step that takes an appreciable
time. 2.5s for primes up to 1e11 on my machine.
primes = Masker(tiny, small, PrimeCount / (2 * CHAR_BIT
* sizeof(StoreType)) + 1);
s.lap(__LINE__);
}
// if the buffer isn't big enough yet expand it by duplicating
early entries.
if (primes.size() < PrimeCount / (2 * CHAR_BIT *
sizeof(StoreType)) + 1)
{
primes.resize(PrimeCount);
s.lap(__LINE__);
}
do
{
std::vector<PRIME> quickies;
PRIME quickMaxPrime = std::min(nextPrime*nextPrime,
PRIME(sqrt(PrimeCount) + 1));
do
{
do
{
nextPrime += 2;
} while (!primes.get(nextPrime));
quickies.emplace_back(nextPrime);
} while (nextPrime < quickMaxPrime);
s.lap(__LINE__);
// this function adds all the quickies into the mask,
but does all of them in
// one area of memory before moving onto the next. The
area of memory,
// and the list of primes, both fit into the L1 cache.
// You may need to adjust bigCache for best performance.
// This step takes a while - two lots of 20s for qe11
primes.
primes.andequals(bigCache, quickies.begin(),
quickies.end());
s.lap(__LINE__);
} while (nextPrime*nextPrime < PrimeCount);
s.stop();
std::cerr << primes.size() << "," << s.laps().back().second <<
std::endl;
for (auto l: s.laps()) std::cerr << l.first << "," << l.second
<< std::endl;
if (outName.length())
{
std::ofstream outfile(outName);
outfile << "2\n";
for (PRIME prime = 3; prime < PrimeCount; prime += 2)
{
if (primes.get(prime))
{
outfile << prime << '\n';
}
}
}
return 0;
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-09-28 03:46 -0700 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <86wmiw3vk2.fsf@linuxsc.com> |
| In reply to | #119990 |
Vir Campestris <vir.campestris@invalid.invalid> writes: [...] I tried to post a short followup, but I must have done something wrong because nothing went out. Long story short, I've been pulled away from looking at this further due to other tasks demanding my attention, and also because the Sieve of Aiken looks more promising (having been reminded recently of primegen by Daniel Bernstein). In any case, thank you for the back and forth, it's been fun.
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2024-09-28 13:49 -0700 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <871q13sdv3.fsf@nosuchdomain.example.com> |
| In reply to | #120429 |
Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> Vir Campestris <vir.campestris@invalid.invalid> writes:
>
> [...]
>
> I tried to post a short followup, but I must have done something
> wrong because nothing went out. Long story short, I've been
> pulled away from looking at this further due to other tasks
> demanding my attention, and also because the Sieve of Aiken
> looks more promising (having been reminded recently of
> primegen by Daniel Bernstein).
Typo: Sieve of Atkin.
https://en.wikipedia.org/wiki/Sieve_of_Atkin
> In any case, thank you for the back and forth, it's been fun.
--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2024-10-02 11:44 +0100 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <vdj872$36t95$1@dont-email.me> |
| In reply to | #120439 |
On 28/09/2024 21:49, Keith Thompson wrote: > Tim Rentsch <tr.17687@z991.linuxsc.com> writes: >> Vir Campestris <vir.campestris@invalid.invalid> writes: >> >> [...] >> >> I tried to post a short followup, but I must have done something >> wrong because nothing went out. Long story short, I've been >> pulled away from looking at this further due to other tasks >> demanding my attention, and also because the Sieve of Aiken >> looks more promising (having been reminded recently of >> primegen by Daniel Bernstein). > > Typo: Sieve of Atkin. > > https://en.wikipedia.org/wiki/Sieve_of_Atkin > >> In any case, thank you for the back and forth, it's been fun. > Well, the holiday was fun (the Zeppelin museum on the Bodensee was especially interesting for geeks) but my wife picked up what we think was COVID in one of the hotels so she was a bit **** towards the end. Then she gave it to me :( However... I now have a working version storing all primes as (prime/30 mask(prime%30) and tuned up. The disappointing thing is that it's not until you get to seriously big numbers - something in the 1e9 range - that this is faster than the code I posted before. And even then it's not _much_ faster. About 20% at 1e11. Over in comp.lang.c this came up too, and there's a link there to the Sieve of Atkin <https://en.wikipedia.org/wiki/Sieve_of_Atkin> and to a program <http://cr.yp.to/primegen.html> which implements it. I'm pleased to be able to report that that program, written for a 1998 CPU, is slower than mine on my modern CPU. Andy
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-10-02 13:10 +0200 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <vdj9n0$37b8a$1@raubtier-asyl.eternal-september.org> |
| In reply to | #120544 |
Whatever ... No one will beat my code in terms of speed. And it doesn't give wrong numers as someone claimed here.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-10-07 08:41 -0700 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <86msjfzzry.fsf@linuxsc.com> |
| In reply to | #120544 |
Vir Campestris <vir.campestris@invalid.invalid> writes:
> On 28/09/2024 21:49, Keith Thompson wrote:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> Vir Campestris <vir.campestris@invalid.invalid> writes:
>>>
>>> [...]
>>>
>>> I tried to post a short followup, but I must have done something
>>> wrong because nothing went out. Long story short, I've been
>>> pulled away from looking at this further due to other tasks
>>> demanding my attention, and also because the Sieve of Aiken
>>> looks more promising (having been reminded recently of
>>> primegen by Daniel Bernstein).
>>
>> Typo: Sieve of Atkin.
>>
>> https://en.wikipedia.org/wiki/Sieve_of_Atkin
>>
>>> In any case, thank you for the back and forth, it's been fun.
>
> [...]
>
> I now have a working version storing all primes as (prime/30
> mask(prime%30) and tuned up.
>
> The disappointing thing is that it's not until you get to seriously
> big numbers - something in the 1e9 range - that this is faster than
> the code I posted before. And even then it's not _much_ faster. About
> 20% at 1e11.
This reaction, more broadly, has been rather surprising. The whole
point of using a sieve is that it is asymptotically faster. Who
cares about how fast primes under a billion, or ten billion, or
fifty billion, can be computed? It's much more interesting to ask
how high a limit can be searched in a day or a week of computing.
(I don't mean just your comment, but comments from other folks
bragging about how fast they can find all 32-bit primes.) I ran
my earlier programs up to limits of 3 trillion or so.
> Over in comp.lang.c this came up too, and there's a link there to the
> Sieve of Atkin
>
> <https://en.wikipedia.org/wiki/Sieve_of_Atkin>
>
> and to a program
>
> <http://cr.yp.to/primegen.html>
>
> which implements it.
I saw this link but didn't play around with the program.
> I'm pleased to be able to report that that program, written for a 1998
> CPU, is slower than mine on my modern CPU.
What has been interesting is that these days prime-finding programs
really need to be tailored to the hardware they will be run on.
Somehow that seems like a step backwards. Fifty years ago programmers
always thought about low-level hardware characteristics when writing
programs. Over time the fraction of time spent worrying about such
things has gotten smaller and smaller, to the point now where it is
almost never important. But wanting to write a fast prime-finding
program has taken us back to the glory days of yesteryear. ;)
Incidentally, I found a program primesieve that's available under
Ubuntu Linux. On a whim I had it find primes less than 2**49,
which took slightly more than 12 hours elapsed time (running on 12
cores). If computing primes up to N, a nice ratio to compute is
(number of primes less than N) * log N / N
which converges to 1, but very slowly. For primes less than 2**49
I got 1.03135087927594382.
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2024-10-20 12:44 +0100 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <vf2qel$cko5$3@dont-email.me> |
| In reply to | #120619 |
On 07/10/2024 16:41, Tim Rentsch wrote: > This reaction, more broadly, has been rather surprising. The whole > point of using a sieve is that it is asymptotically faster. Who > cares about how fast primes under a billion, or ten billion, or > fifty billion, can be computed? It's much more interesting to ask > how high a limit can be searched in a day or a week of computing. > (I don't mean just your comment, but comments from other folks > bragging about how fast they can find all 32-bit primes.) I ran > my earlier programs up to limits of 3 trillion or so. My programs all require the sieved prime map to fit in RAM. Which in my system limits me to about 10^11 primes. It has occurred to me to extend it for much larger numbers, by paging out to disc files. But I've wasted far too much time on this already! Andy
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-11-04 03:56 -0800 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <86h68ntdoz.fsf@linuxsc.com> |
| In reply to | #120742 |
Vir Campestris <vir.campestris@invalid.invalid> writes: > On 07/10/2024 16:41, Tim Rentsch wrote: > >> This reaction, more broadly, has been rather surprising. The whole >> point of using a sieve is that it is asymptotically faster. Who >> cares about how fast primes under a billion, or ten billion, or >> fifty billion, can be computed? It's much more interesting to ask >> how high a limit can be searched in a day or a week of computing. >> (I don't mean just your comment, but comments from other folks >> bragging about how fast they can find all 32-bit primes.) I ran >> my earlier programs up to limits of 3 trillion or so. > > My programs all require the sieved prime map to fit in RAM. Which in > my system limits me to about 10^11 primes. > > It has occurred to me to extend it for much larger numbers, by paging > out to disc files. But I've wasted far too much time on this already! I propose a new challenge: compute all primes up to a large number (e.g., 10e12) with a program that has a small memory footprint (and no storing intermediate values on disk, etc). I wrote a small program in C, with a memory footprint well under one megabyte, and found all primes under 10240000000000 (all it did was count them, which I checked using primesieve). About 150 lines of fairly routine C code. If you want a sanity check there are 354080024725 primes less than 10240000000000.
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2024-08-19 21:34 +0100 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <va0a8b$30cvv$2@dont-email.me> |
| In reply to | #119817 |
On 16/08/2024 18:35, Bonita Montero wrote: > But basically I don't think it is a good idea to skip numbers exept > multiples of two. With the three you save a sixth of memory, with > the five you save a 15-th and at the end you get about 20% less > storage (1 / (2 * 3) + 1 / (2 * 3 * 5) + 1 / (2 * 3 * 5 * 7) ...) > for a lot of computation. That's the point where I dropped this > idea and I think this extra computation is higher than the time > for the saved memory loads. BTW I was just checking outputs. 66049 67591 69133 69647 71189 72217 72731 75301 78899 79927 80441 81469 85067 86609 89179 89693 90721 92263 94319 95861 97403 98431 99973 all show in the output for your program, but not mine. I think you'll find they are products of 257 and the next few primes. Andy
[toc] | [prev] | [next] | [standalone]
| From | red floyd <no.spam.here@its.invalid> |
|---|---|
| Date | 2024-08-19 21:08 -0700 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <va14rc$387ss$1@redfloyd.dont-email.me> |
| In reply to | #119825 |
So I'm a little late, but here's my effort to use the modulo 30 trick.
Using g++ 12.4.0, Cygwin under Windows 11 22631, Ryzen 5 5600x, 64GB RAM
g++ -O3 -std=c++17
5761455 primess less than 100 million in 0.182269s
50847534 primes less than 1 billion in 2.841167s
455052511 primes less than 10billion in 53.009133s
-- CUT HERE ---
#include <iostream>
#include <chrono>
#include <stdint.h>
#include <vector>
#include <tuple>
#include <string>
#include <iomanip>
using inttype_t = uint64_t;
using settype_t = unsigned char;
class Sieve {
static constexpr inttype_t MOD_VALUE { 30ull };
// 1, 7, 11, 13, 17, 19, 23, 29
static constexpr settype_t masks[] = {
0x00, 0x01, 0x00, 0x00, 0x00, 0x00, // 1
0x00, 0x02, 0x00, 0x00, 0x00, 0x04, // 7, 11
0x00, 0x08, 0x00, 0x00, 0x00, 0x10, // 13, 17
0x00, 0x20, 0x00, 0x00, 0x00, 0x40, // 19, 23
0x00, 0x00, 0x00, 0x00, 0x00, 0x80 // 29
};
inttype_t max_val;
std::vector<settype_t> sieve;
inttype_t nprimes;
using lookup_t = std::tuple<inttype_t, settype_t>;
inline lookup_t lookup(inttype_t val)
{
return std::make_tuple(val / MOD_VALUE, masks[val % MOD_VALUE]);
}
public:
inline bool is_prime(inttype_t val)
{
const auto [index, mask] = lookup(val);
return static_cast<bool>(sieve[index] & mask);
}
inline void mark_prime(inttype_t val)
{
++nprimes;
const inttype_t incr = val + val;
for (inttype_t j = val + incr; j <= max_val; j += incr)
{
const auto [index, mask] = lookup(j);
sieve[index] &= ~mask;
}
}
inttype_t get_prime_count() { return nprimes; }
Sieve(inttype_t max_)
: max_val(max_)
, sieve((max_ / MOD_VALUE) + 1, ~settype_t())
, nprimes(3)
{
}
};
int main(int argc, char *argv[])
{
std::vector<std::string> args(argv, argv+argc);
constexpr inttype_t default_max = 100ull;
inttype_t max_val = default_max;
if (argc > 1)
{
max_val = std::stoull(args[1]);
if (max_val == 0)
max_val = default_max;
}
Sieve sieve(max_val);
const auto start = std::chrono::steady_clock::now();
for (inttype_t j = 7 ; j <= max_val ; j += 2)
{
if (sieve.is_prime(j))
{
sieve.mark_prime(j);
}
}
const auto finish = std::chrono::steady_clock::now();
const auto diff =
std::chrono::duration_cast<std::chrono::microseconds>(finish -
start);
constexpr uint64_t us_per_sec = 1'000'000;
auto us = diff.count();
std::cout << sieve.get_prime_count()
<< " primes found less than "
<< max_val
<< " in "
<< (us / us_per_sec)
<< "."
<< std::setw(6)
<< std::setfill('0')
<< (us % us_per_sec)
<< "s\n";
return 0;
}
-- CUT HERE ---
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2024-08-20 21:14 +0100 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <va2tf8$3gpbu$1@dont-email.me> |
| In reply to | #119827 |
On 20/08/2024 05:08, red floyd wrote: > So I'm a little late, but here's my effort to use the modulo 30 trick. > > Using g++ 12.4.0, Cygwin under Windows 11 22631, Ryzen 5 5600x, 64GB RAM > > g++ -O3 -std=c++17 > 5761455 primess less than 100 million in 0.182269s > 50847534 primes less than 1 billion in 2.841167s > 455052511 primes less than 10billion in 53.009133s It's slow. Looking quickly at the (remarkably small) code I see line 30: return std::make_tuple(val / MOD_VALUE, masks[val % MOD_VALUE]); That mod and div are being called for every single time you mark a prime in the bitmap. Andy
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-08-26 09:35 -0700 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <864j775jis.fsf@linuxsc.com> |
| In reply to | #119847 |
Vir Campestris <vir.campestris@invalid.invalid> writes: > On 20/08/2024 05:08, red floyd wrote: > >> So I'm a little late, but here's my effort to use the modulo >> 30 trick. >> >> Using g++ 12.4.0, Cygwin under Windows 11 22631, Ryzen 5 >> 5600x, 64GB RAM >> >> g++ -O3 -std=c++17 >> 5761455 primess less than 100 million in 0.182269s >> 50847534 primes less than 1 billion in 2.841167s >> 455052511 primes less than 10billion in 53.009133s > > It's slow. > > Looking quickly at the (remarkably small) code I see line 30: > > return std::make_tuple(val / MOD_VALUE, masks[val % MOD_VALUE]); > > That mod and div are being called for every single time you > mark a prime in the bitmap. That is a cost but I'm pretty sure it's not the most important aspect.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-08-26 08:31 -0700 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <86bk1f5mi4.fsf@linuxsc.com> |
| In reply to | #119827 |
red floyd <no.spam.here@its.invalid> writes:
> So I'm a little late, but here's my effort to use the modulo 30
> trick.
>
> Using g++ 12.4.0, Cygwin under Windows 11 22631, Ryzen 5 5600x,
> 64GB RAM
>
> g++ -O3 -std=c++17
> 5761455 primess less than 100 million in 0.182269s
> 50847534 primes less than 1 billion in 2.841167s
> 455052511 primes less than 10billion in 53.009133s
I appreciate both the effort and your posting of results.
> [..program..]
There are several ways that the program is doing noticeably more
work than it needs to. I haven't done any measurements but I
believe this extra work accounts for the biggest part of its
relative slowness. Here is a short simple program to illustrate
some ways that your program could be sped up.
(The short simple program is the rest of this posting.)
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long long Index, Count, Bits, NN, N235;
static const unsigned char mods[8] = { 1, 7, 11, 13, 17, 19, 23, 29, };
static unsigned char bytes[ 1ULL * 50 * 1000 * 1000 * 1000 ];
static void mod30_sieve( NN );
static NN product_NN( N235, N235 );
static _Bool is_marked_composite( N235 );
static void mark_composite( NN );
static Count unmarked_less_than( NN );
int
main( int argc, char *argv[] ){
NN ceiling = argc > 1 ? strtoull( argv[1], 0, 10 ) : 1000000000;
setbuf( stdout, 0 );
if( ceiling >= 30 * sizeof bytes ){
printf( " urk.. limit must be less than %zu\n", 30 * sizeof bytes );
exit( 0 );
}
printf( " determining primes less than %llu ...\n", ceiling );
mod30_sieve( ceiling );
printf( " ... found %llu primes.\n", unmarked_less_than( ceiling ) );
return 0;
}
void
mod30_sieve( NN ceiling ){
N235 i, j;
NN ijNN;
for( bytes[0] = 1, i = 0; product_NN( i, i ) < ceiling; i++ ){
if( is_marked_composite( i ) ) continue;
for( j = i; ijNN = product_NN( i, j ), ijNN < ceiling; j++ ){
mark_composite( ijNN );
}
}
}
NN
product_NN( N235 x, N235 y ){
NN xnn = (x>>3)*30 + mods[x&7];
NN ynn = (y>>3)*30 + mods[y&7];
return xnn * ynn;
}
_Bool
is_marked_composite( N235 t ){
return bytes[t>>3] & 1<<(t&7);
}
void
mark_composite( NN nn ){
static const unsigned char masks[] = {
[1]= 1, [7]= 2, [11]= 4, [13]= 8, [17]= 16, [19]= 32, [23]=64, [29]=128,
};
bytes[ nn/30 ] |= masks[ nn%30 ];
}
Count
unmarked_less_than( NN ceiling ){
Index i = ceiling/30;
NN extra = ceiling - i*30;
Count r = (ceiling > 2) + (ceiling > 3) + (ceiling > 5);
for( Index j = 0; j < 8 && mods[j] < extra; j++ ){
r += bytes[i]>>j &1 ^1;
}
while( i && i-- ){
for( Bits b = bytes[i] ^0xFF; b; b >>= 1 ) r += b&1;
}
return r;
}
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-08-20 19:20 +0200 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <va2j8m$3f9u2$1@raubtier-asyl.eternal-september.org> |
| In reply to | #119825 |
Am 19.08.2024 um 22:34 schrieb Vir Campestris: > On 16/08/2024 18:35, Bonita Montero wrote: >> But basically I don't think it is a good idea to skip numbers exept >> multiples of two. With the three you save a sixth of memory, with >> the five you save a 15-th and at the end you get about 20% less >> storage (1 / (2 * 3) + 1 / (2 * 3 * 5) + 1 / (2 * 3 * 5 * 7) ...) >> for a lot of computation. That's the point where I dropped this >> idea and I think this extra computation is higher than the time >> for the saved memory loads. > > BTW I was just checking outputs. > > 66049 > 67591 > 69133 > 69647 > 71189 > 72217 > 72731 > 75301 > 78899 > 79927 > 80441 > 81469 > 85067 > 86609 > 89179 > 89693 > 90721 > 92263 > 94319 > 95861 > 97403 > 98431 > 99973 > > all show in the output for your program, but not mine. I think you'll > find they are products of 257 and the next few primes. I simply printed primes up to a billion and chose the last numer and looked in the internet if this is really the n-th prime according to my count function (second parameter is "*").
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-08-20 19:36 +0200 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <va2k64$3fete$1@raubtier-asyl.eternal-september.org> |
| In reply to | #119837 |
Am 20.08.2024 um 19:20 schrieb Bonita Montero: > Am 19.08.2024 um 22:34 schrieb Vir Campestris: >> On 16/08/2024 18:35, Bonita Montero wrote: >>> But basically I don't think it is a good idea to skip numbers exept >>> multiples of two. With the three you save a sixth of memory, with >>> the five you save a 15-th and at the end you get about 20% less >>> storage (1 / (2 * 3) + 1 / (2 * 3 * 5) + 1 / (2 * 3 * 5 * 7) ...) >>> for a lot of computation. That's the point where I dropped this >>> idea and I think this extra computation is higher than the time >>> for the saved memory loads. >> >> BTW I was just checking outputs. >> >> 66049 >> 67591 >> 69133 >> 69647 >> 71189 >> 72217 >> 72731 >> 75301 >> 78899 >> 79927 >> 80441 >> 81469 >> 85067 >> 86609 >> 89179 >> 89693 >> 90721 >> 92263 >> 94319 >> 95861 >> 97403 >> 98431 >> 99973 >> >> all show in the output for your program, but not mine. I think you'll >> find they are products of 257 and the next few primes. > > I simply printed primes up to a billion and chose the last numer and > looked in the internet if this is really the n-th prime according to > my count function (second parameter is "*"). > If I call my program with "1000000000 primes.txt" the prime 999999937 really comes on line 50847534, which matches the following page: https://prime-numbers.fandom.com/wiki/999,999,937
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-08-20 19:39 +0200 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <va2kca$3ffl5$1@raubtier-asyl.eternal-september.org> |
| In reply to | #119837 |
Am 20.08.2024 um 19:20 schrieb Bonita Montero: > Am 19.08.2024 um 22:34 schrieb Vir Campestris: >> On 16/08/2024 18:35, Bonita Montero wrote: >>> But basically I don't think it is a good idea to skip numbers exept >>> multiples of two. With the three you save a sixth of memory, with >>> the five you save a 15-th and at the end you get about 20% less >>> storage (1 / (2 * 3) + 1 / (2 * 3 * 5) + 1 / (2 * 3 * 5 * 7) ...) >>> for a lot of computation. That's the point where I dropped this >>> idea and I think this extra computation is higher than the time >>> for the saved memory loads. >> >> BTW I was just checking outputs. >> >> 66049 >> 67591 >> 69133 >> 69647 >> 71189 >> 72217 >> 72731 >> 75301 >> 78899 >> 79927 >> 80441 >> 81469 >> 85067 >> 86609 >> 89179 >> 89693 >> 90721 >> 92263 >> 94319 >> 95861 >> 97403 >> 98431 >> 99973 I checked some numbers from this table and I can find none of them in my output.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-08-20 20:13 +0200 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <va2mbf$3fnmk$1@raubtier-asyl.eternal-september.org> |
| In reply to | #119825 |
Am 19.08.2024 um 22:34 schrieb Vir Campestris:
> On 16/08/2024 18:35, Bonita Montero wrote:
>> But basically I don't think it is a good idea to skip numbers exept
>> multiples of two. With the three you save a sixth of memory, with
>> the five you save a 15-th and at the end you get about 20% less
>> storage (1 / (2 * 3) + 1 / (2 * 3 * 5) + 1 / (2 * 3 * 5 * 7) ...)
>> for a lot of computation. That's the point where I dropped this
>> idea and I think this extra computation is higher than the time
>> for the saved memory loads.
>
> BTW I was just checking outputs.
>
> 66049
> 67591
> 69133
> 69647
> 71189
> 72217
> 72731
> 75301
> 78899
> 79927
> 80441
> 81469
> 85067
> 86609
> 89179
> 89693
> 90721
> 92263
> 94319
> 95861
> 97403
> 98431
> 99973
>
> all show in the output for your program, but not mine. I think you'll
> find they are products of 257 and the next few primes.
>
> Andy
I wrote a small program to look if the above numbers are included in my
output:
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
int main( int argc, char **argv )
{
if( argc < 3 )
return EXIT_FAILURE;
auto read = []( char const *file, vector<size_t> &vec )
{
ifstream ifs( file );
while( !ifs.eof() )
{
size_t number;
ifs >> number;
vec.emplace_back( number );
}
sort( vec.begin(), vec.end() );
};
vector<size_t> large, small;
read( argv[1], large );
read( argv[2], small );
for( size_t lookup : small )
{
auto where = lower_bound( large.begin (), large.end(), lookup );
if( where == large.end() || *where != lookup )
continue;
cout << lookup << endl;
}
}
None of the numbers are my output.
[toc] | [prev] | [next] | [standalone]
| From | scott@slp53.sl.home (Scott Lurndal) |
|---|---|
| Date | 2024-08-20 20:50 +0000 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <Nk7xO.586512$qO%5.457110@fx16.iad> |
| In reply to | #119840 |
Bonita Montero <Bonita.Montero@gmail.com> writes: >Am 19.08.2024 um 22:34 schrieb Vir Campestris: > >I wrote a small program Most people would use the standard command line tools to do this (e.g. sort, uniq and diff).
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2024-08-22 17:30 +0100 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <va7p3h$g9lc$1@dont-email.me> |
| In reply to | #119848 |
On 20/08/2024 21:50, Scott Lurndal wrote: > Bonita Montero <Bonita.Montero@gmail.com> writes: >> Am 19.08.2024 um 22:34 schrieb Vir Campestris: > >> >> I wrote a small program > > Most people would use the standard command line > tools to do this (e.g. sort, uniq and diff). She's on Windows :P I just tried again to check my sanity. And decided neither of us are crazy. It's sensitive to the number of primes you ask for. $ ./Bonita 100 Bonita.txt && grep -w 66049 Bonita.txt $ ./Bonita 1000 Bonita.txt && grep -w 66049 Bonita.txt $ ./Bonita 10000 Bonita.txt && grep -w 66049 Bonita.txt $ ./Bonita 100000 Bonita.txt && grep -w 66049 Bonita.txt $ ./Bonita 1000000 Bonita.txt && grep -w 66049 Bonita.txt $ ./Bonita 10000000 Bonita.txt && grep -w 66049 Bonita.txt $ ./Bonita 100000000 Bonita.txt && grep -w 66049 Bonita.txt $ ./Bonita 1000000000 Bonita.txt && grep -w 66049 Bonita.txt $ ./Bonita 10000000000 Bonita.txt && grep -w 66049 Bonita.txt 66049 $ ./Bonita 100000000000 Bonita.txt && grep -w 66049 Bonita.txt 66049 $ Andy
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-08-22 18:38 +0200 |
| Subject | Re: OT: Re: Sieve of Erastosthenes optimized to the max |
| Message-ID | <va7pih$gi91$1@raubtier-asyl.eternal-september.org> |
| In reply to | #119880 |
Am 22.08.2024 um 18:30 schrieb Vir Campestris: > On 20/08/2024 21:50, Scott Lurndal wrote: >> Bonita Montero <Bonita.Montero@gmail.com> writes: >>> Am 19.08.2024 um 22:34 schrieb Vir Campestris: >> >>> >>> I wrote a small program >> >> Most people would use the standard command line >> tools to do this (e.g. sort, uniq and diff). > > She's on Windows :P > > I just tried again to check my sanity. And decided neither of us are > crazy. It's sensitive to the number of primes you ask for. > > $ ./Bonita 100 Bonita.txt && grep -w 66049 Bonita.txt > $ ./Bonita 1000 Bonita.txt && grep -w 66049 Bonita.txt > $ ./Bonita 10000 Bonita.txt && grep -w 66049 Bonita.txt > $ ./Bonita 100000 Bonita.txt && grep -w 66049 Bonita.txt > $ ./Bonita 1000000 Bonita.txt && grep -w 66049 Bonita.txt > $ ./Bonita 10000000 Bonita.txt && grep -w 66049 Bonita.txt > $ ./Bonita 100000000 Bonita.txt && grep -w 66049 Bonita.txt > $ ./Bonita 1000000000 Bonita.txt && grep -w 66049 Bonita.txt > $ ./Bonita 10000000000 Bonita.txt && grep -w 66049 Bonita.txt > 66049 I did "findstr /x "66049" primes.txt" on my output and it didn't find that number with 1E10 as its maximum. > $ ./Bonita 100000000000 Bonita.txt && grep -w 66049 Bonita.txt > 66049 > $ > > > Andy
[toc] | [prev] | [next] | [standalone]
Page 10 of 11 — ← Prev page 1 … 8 9 [10] 11 Next page →
Back to top | Article view | comp.lang.c++
csiph-web